三分钟看完两道套数学公式的算法题

Myth丶恋晨 2022-02-03 13:21 202阅读 0赞

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

杨辉三角应该是大家很早就接触到的一个数学知识，它有很多有趣的性质：

*  每个数字等于上一行的左右两个数字之和，即 *C(n+1,i) = C(n,i) + C(n,i-1)*
 *  每行数字左右对称，由 1 开始逐渐变大
 *  第 n 行的数字有 n 项
 *  第 n 行的第 m 个数和第 n - m + 1 个数相等 ，为组合数性质之一
 *  ( a + b )n的展开式中的各项系数依次对应杨辉三角的第 ( n + 1 ) 行中的每一项
 *  。。。

## 杨辉三角 ##

题目来源于 LeetCode 上第 118 号问题：杨辉三角。题目难度为 Easy，目前通过率为 61.8% 。

### 题目描述 ###

给定一个非负整数 *numRows，*生成杨辉三角的前 *numRows* 行。

![640?wx\_fmt=gif][640_wx_fmt_gif]

在杨辉三角中，每个数是它左上方和右上方的数的和。

**示例:**

输入: 5  
输出:  
\[  
\[1\],  
\[1,1\],  
\[1,2,1\],  
\[1,3,3,1\],  
\[1,4,6,4,1\]  
\]

### 题目解析 ###

> 这道题目在各大高校的习题中经常出现。

对于本题而言，利用性质 1 ：每一行的首个和结尾一个数字都是 1，从第三行开始，中间的每个数字都是上一行的左右两个数字之和。

### 代码实现 ###

class Solution\{  
public List<List<Integer>> generate(int numRows) \{  
  
List<List<Integer>> result = new ArrayList<>();  
if (numRows < 1) return result;  
  
for (int i = 0; i < numRows; ++i) \{  
//扩容  
List<Integer> list = Arrays.asList(new Integer\[i+1\]);  
list.set(0, 1); list.set(i, 1);  
for (int j = 1; j < i; ++j) \{  
//等于上一行的左右两个数字之和  
list.set(j, result.get(i-1).get(j-1) + result.get(i-1).get(j));  
\}  
result.add(list);  
\}  
return result;  
  
\}  
\}

## 杨辉三角II ##

题目来源于 LeetCode 上第 119 号问题：杨辉三角II。题目难度为 Easy，目前通过率为 55.5% 。

### 题目描述 ###

给定一个非负索引 *k*，其中 *k* ≤ 33，返回杨辉三角的第 *k* 行。

![640?wx\_fmt=gif][640_wx_fmt_gif]

在杨辉三角中，每个数是它左上方和右上方的数的和。

**示例:**

输入: 3  
输出: \[1,3,3,1\]

**进阶：**

你可以优化你的算法到 *O*(*k*) 空间复杂度吗？

### 题目解析 ###

这道题目的难点与思考点在于题目有额外限制条件，程序只能使用 O(k) 的额外空间，因此无法通过累加的方式将每一行都输出打印。

这里依旧使用杨辉三角的规律，很隐藏的规律：对于杨辉三角的同一行，第 ( i + 1) 项是第 i 项的`( k - i ) /( i + 1 )` 倍。

比如：

*  第 k 索引行的第 0 项：1
 *  第 k 索引行的第 1 项：1 \* k
 *  第 k 索引行的第 2 项：1 \* k \* ( k - 1) / 2
 *  第 k 索引行的第 3 项：\[1 \* k \* ( k - 1) / 2 \] \* ( k - 2 ) / 3

### 代码实现 ###

class Solution\{  
public List<Integer> getRow(int rowIndex)\{  
List<Integer> res = new ArrayList<>(rowIndex + 1);  
long index = 1;  
for (int i = 0; i <= rowIndex; i++) \{  
res.add((int) index);  
index = index \* ( rowIndex - i ) / ( i + 1 );  
\}  
return res;  
\}  
\}

## 杨辉三角中的概率 ##

感兴趣小伙伴的可以搜索一下李永乐讲得抽奖概率相关的视频，里面提及到了很多杨辉三角的神奇特点。

![640?wx\_fmt=gif][640_wx_fmt_gif 1]

**推荐阅读**

[拜托，面试官别问我「布隆」了][Link 1]

[有点难度，几道和「滑动窗口」有关的算法面试题][Link 2]

[数据结构与算法：三十张图弄懂「图的两种遍历方式」][Link 3]

[昨天，终于拿到了腾讯 offer][offer]

[几道和「二叉树」有关的算法面试题][Link 4]

[几道和散列（哈希）表有关的面试题][Link 5]

[一道看完答案你会觉得很沙雕的「动态规划算法题」][Link 6]

[几道和「堆栈、队列」有关的面试算法题][Link 7]

[链表算法面试问题？看我就够了！][Link 8]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 1]

来和程序员小吴一起学算法~

我就知道你在看！

[640_wx_fmt_jpeg]: /images/20220203/fdaa4a8c8322424bac51da5772169f79.png
[640_wx_fmt_gif]: /images/20220203/de76bb2a155a4fa4a49d292de637eaf7.png
[640_wx_fmt_gif 1]: /images/20220203/3a07550190c844a3915118e566dae26b.png
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485011&idx=1&sn=a3031a3d3ad033e44439d42d72753e16&chksm=fa0e69d2cd79e0c45b1eb017c65b60662890f67ec70ef44e92ef7f5cddfc313ea6ab353952f4&scene=21#wechat_redirect
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485197&idx=1&sn=1bbd40d49adb09875fd324664bd5bc8b&chksm=fa0e688ccd79e19a36599b53e4a8acf9a725ace3f6df28925075ff25778238471a283f0f8e1f&scene=21#wechat_redirect
[Link 3]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485076&idx=1&sn=ba747d1efd4c009da83681a6bb4ff549&chksm=fa0e6915cd79e003249e9ee045d09a174b0e5aff2a6ecd807e10fd01bfbc1a37da688eb51637&scene=21#wechat_redirect
[offer]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485001&idx=1&sn=cdcebef70aaabcafa3403c2dd51bdfb7&chksm=fa0e69c8cd79e0de12ece3a9e48430099c429aff816cc3a9e40035192dc07a864864888d1078&scene=21#wechat_redirect
[Link 4]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484985&idx=1&sn=93343d355abf36c77a361c9931cbe2d1&chksm=fa0e69b8cd79e0ae1e6b57665a456da5f421cc92fe6934337f1eb1e18c3fd6a3c1adc8ca88c2&scene=21#wechat_redirect
[Link 5]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484977&idx=1&sn=f4a6148480555e3cca83231ac1df8d02&chksm=fa0e69b0cd79e0a686e31c547fc783eb9663d9fe19cc95ecd524e9f8f7e0d4a168945f8755e5&scene=21#wechat_redirect
[Link 6]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484875&idx=1&sn=72cf66da1c970ba345e8b1ab3586c10d&chksm=fa0e6a4acd79e35c32c9201e99cc93a71d0f2a331319addf5303c76ac05738b312ab238a8304&scene=21#wechat_redirect
[Link 7]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484846&idx=2&sn=e508da06e9f7a0b3d00db5415d7ce622&chksm=fa0e6a2fcd79e3397fe8083f9493ae639f47c9448ac2a0026026494d098c47ecc6e08f1f8e28&scene=21#wechat_redirect
[Link 8]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484830&idx=1&sn=9d24fc787da4b49b82ac01c7f8de257b&chksm=fa0e6a1fcd79e309a2e7f3e09ec9913a55f1c077287c907f13528578b7785831a2effb3104e0&scene=21#wechat_redirect
[640_wx_fmt_jpeg 1]: /images/20220203/6625e098d84a4326bc5e6a285b3703f3.png