forked from MisterBooo/LeetCodeAnimation
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathLeetCode第118号问题：杨辉三角.md
146 lines (93 loc) · 3.96 KB
/
LeetCode第118号问题：杨辉三角.md
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
# 杨辉三角
> 本文首发于公众号「五分钟学算法」，是[图解 LeetCode](https://github.com/MisterBooo/LeetCodeAnimation) 系列文章之一。
>
> 个人网站：[https://www.cxyxiaowu.com](https://www.cxyxiaowu.com)
>
杨辉三角应该是大家很早就接触到的一个数学知识，它有很多有趣的性质：
- 每个数字等于上一行的左右两个数字之和，即 *C(n+1,i) = C(n,i) + C(n,i-1)*
- 每行数字左右对称，由 1 开始逐渐变大
- 第 n 行的数字有 n 项
- 第 n 行的第 m 个数和第 n - m + 1 个数相等 ，为[组合数](https://baike.baidu.com/item/%E7%BB%84%E5%90%88%E6%95%B0)性质之一
- ( a + b )<sup>n</sup>的展开式中的各项[系数](https://baike.baidu.com/item/%E7%B3%BB%E6%95%B0)依次对应杨辉三角的第 ( n + 1 ) 行中的每一项
- 。。。
## 杨辉三角
题目来源于 LeetCode 上第 118 号问题：杨辉三角。题目难度为 Easy，目前通过率为 61.8% 。
### 题目描述
给定一个非负整数 *numRows，*生成杨辉三角的前 *numRows* 行。
在杨辉三角中，每个数是它左上方和右上方的数的和。
**示例:**
```
输入: 5
输出:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
```
### 题目解析
> 这道题目在各大高校的习题中经常出现。
对于本题而言，利用性质 1 ：每一行的首个和结尾一个数字都是 1，从第三行开始，中间的每个数字都是上一行的左右两个数字之和。
### 代码实现
```java
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* 行。
在杨辉三角中，每个数是它左上方和右上方的数的和。
**示例:**
```
输入: 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
### 代码实现
```java
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;
}
}
```
## 一个有趣的结论
感兴趣小伙伴的可以搜索一下李永乐讲得抽奖概率相关的视频，里面提及到了很多杨辉三角的神奇特点。
