Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Sign up
Appearance settings

Commit ba6b338

Browse files
添加 118、119
1 parent fe3f78f commit ba6b338

File tree

4 files changed

+302
-0
lines changed

4 files changed

+302
-0
lines changed

‎Readme.md

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -33,6 +33,8 @@
3333
| 102 | [二叉树的层序遍历](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第102号问题:二叉树的层序遍历.md) |
3434
| 103 | [二叉树的锯齿形层次遍历](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第103号问题:二叉树的锯齿形层次遍历.md) |
3535
| 107 | [二叉树的层次遍历 II](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第107号问题:二叉树的层次遍历II.md) |
36+
| 118 | [杨辉三角](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第118号问题:杨辉三角.md) |
37+
| 119 | [杨辉三角II](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第119号问题:杨辉三角II.md) |
3638
| 110 | [平衡二叉树](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第110号问题:平衡二叉树.md) |
3739
| 121 | [买卖股票的最佳时机](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第121号问题:买卖股票的最佳时机.md) |
3840
| 122 | [买卖股票的最佳时机II](https://github.com/MisterBooo/LeetCodeAnimation/tree/master/notes/LeetCode第122号问题:买卖股票的最佳时机II.md) |
Lines changed: 146 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,146 @@
1+
2+
3+
# 杨辉三角
4+
5+
![](https://bucket-1257126549.cos.ap-guangzhou.myqcloud.com/20190507201419.png)
6+
7+
> 本文首发于公众号「五分钟学算法」,是[图解 LeetCode](https://github.com/MisterBooo/LeetCodeAnimation) 系列文章之一。
8+
>
9+
> 个人网站:[https://www.cxyxiaowu.com](https://www.cxyxiaowu.com)
10+
>
11+
12+
13+
杨辉三角应该是大家很早就接触到的一个数学知识,它有很多有趣的性质:
14+
15+
- 每个数字等于上一行的左右两个数字之和,即 *C(n+1,i) = C(n,i) + C(n,i-1)*
16+
- 每行数字左右对称,由 1 开始逐渐变大
17+
- 第 n 行的数字有 n 项
18+
- 第 n 行的第 m 个数和第 n - m + 1 个数相等 ,为[组合数](https://baike.baidu.com/item/%E7%BB%84%E5%90%88%E6%95%B0)性质之一
19+
- ( a + b )<sup>n</sup>的展开式中的各项[系数](https://baike.baidu.com/item/%E7%B3%BB%E6%95%B0)依次对应杨辉三角的第 ( n + 1 ) 行中的每一项
20+
- 。。。
21+
22+
23+
24+
## 杨辉三角
25+
26+
题目来源于 LeetCode 上第 118 号问题:杨辉三角。题目难度为 Easy,目前通过率为 61.8% 。
27+
28+
### 题目描述
29+
30+
给定一个非负整数 *numRows,*生成杨辉三角的前 *numRows* 行。
31+
32+
![img](https://upload.wikimedia.org/wikipedia/commons/0/0d/PascalTriangleAnimated2.gif)
33+
34+
在杨辉三角中,每个数是它左上方和右上方的数的和。
35+
36+
**示例:**
37+
38+
```
39+
输入: 5
40+
输出:
41+
[
42+
[1],
43+
[1,1],
44+
[1,2,1],
45+
[1,3,3,1],
46+
[1,4,6,4,1]
47+
]
48+
```
49+
50+
### 题目解析
51+
52+
> 这道题目在各大高校的习题中经常出现。
53+
54+
对于本题而言,利用性质 1 :每一行的首个和结尾一个数字都是 1,从第三行开始,中间的每个数字都是上一行的左右两个数字之和。
55+
56+
### 代码实现
57+
58+
```java
59+
class Solution {
60+
public List<List<Integer>> generate(int numRows) {
61+
62+
List<List<Integer>> result = new ArrayList<>();
63+
if (numRows < 1) return result;
64+
65+
for (int i = 0; i < numRows; ++i) {
66+
//扩容
67+
List<Integer> list = Arrays.asList(new Integer[i+1]);
68+
list.set(0, 1); list.set(i, 1);
69+
for (int j = 1; j < i; ++j) {
70+
//等于上一行的左右两个数字之和
71+
list.set(j, result.get(i-1).get(j-1) + result.get(i-1).get(j));
72+
}
73+
result.add(list);
74+
}
75+
return result;
76+
77+
}
78+
}
79+
80+
```
81+
82+
83+
84+
## 杨辉三角II
85+
86+
题目来源于 LeetCode 上第 119 号问题:杨辉三角II。题目难度为 Easy,目前通过率为 55.5% 。
87+
88+
### 题目描述
89+
90+
给定一个非负索引 *k*,其中 *k* ≤ 33,返回杨辉三角的第 *k* 行。
91+
92+
![img](https://upload.wikimedia.org/wikipedia/commons/0/0d/PascalTriangleAnimated2.gif)
93+
94+
在杨辉三角中,每个数是它左上方和右上方的数的和。
95+
96+
**示例:**
97+
98+
```
99+
输入: 3
100+
输出: [1,3,3,1]
101+
```
102+
103+
**进阶:**
104+
105+
你可以优化你的算法到 *O*(*k*) 空间复杂度吗?
106+
107+
### 题目解析
108+
109+
这道题目的难点与思考点在于题目有额外限制条件,程序只能使用 O(k) 的额外空间,因此无法通过累加的方式将每一行都输出打印。
110+
111+
这里依旧使用杨辉三角的规律,很隐藏的规律:对于杨辉三角的同一行,第 ( i + 1) 项是第 i 项的` ( k - i ) /( i + 1 )` 倍。
112+
113+
比如:
114+
115+
- 第 k 索引行的第 0 项:1
116+
- 第 k 索引行的第 1 项:1 * k
117+
- 第 k 索引行的第 2 项:1 * k * ( k - 1) / 2
118+
- 第 k 索引行的第 3 项:[1 * k * ( k - 1) / 2 ] * ( k - 2 ) / 3
119+
120+
121+
122+
### 代码实现
123+
124+
```java
125+
class Solution {
126+
public List<Integer> getRow(int rowIndex) {
127+
List<Integer> res = new ArrayList<>(rowIndex + 1);
128+
long index = 1;
129+
for (int i = 0; i <= rowIndex; i++) {
130+
res.add((int) index);
131+
index = index * ( rowIndex - i ) / ( i + 1 );
132+
}
133+
return res;
134+
}
135+
}
136+
```
137+
138+
139+
140+
## 一个有趣的结论
141+
142+
感兴趣小伙伴的可以搜索一下李永乐讲得抽奖概率相关的视频,里面提及到了很多杨辉三角的神奇特点。
143+
![](https://bucket-1257126549.cos.ap-guangzhou.myqcloud.com/20190509165331.gif)
144+
145+
146+
![](https://bucket-1257126549.cos.ap-guangzhou.myqcloud.com/blog/fz0rq.png)
Lines changed: 146 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,146 @@
1+
2+
3+
# 杨辉三角
4+
5+
![](https://bucket-1257126549.cos.ap-guangzhou.myqcloud.com/20190507201419.png)
6+
7+
> 本文首发于公众号「五分钟学算法」,是[图解 LeetCode](https://github.com/MisterBooo/LeetCodeAnimation) 系列文章之一。
8+
>
9+
> 个人网站:[https://www.cxyxiaowu.com](https://www.cxyxiaowu.com)
10+
>
11+
12+
13+
杨辉三角应该是大家很早就接触到的一个数学知识,它有很多有趣的性质:
14+
15+
- 每个数字等于上一行的左右两个数字之和,即 *C(n+1,i) = C(n,i) + C(n,i-1)*
16+
- 每行数字左右对称,由 1 开始逐渐变大
17+
- 第 n 行的数字有 n 项
18+
- 第 n 行的第 m 个数和第 n - m + 1 个数相等 ,为[组合数](https://baike.baidu.com/item/%E7%BB%84%E5%90%88%E6%95%B0)性质之一
19+
- ( a + b )<sup>n</sup>的展开式中的各项[系数](https://baike.baidu.com/item/%E7%B3%BB%E6%95%B0)依次对应杨辉三角的第 ( n + 1 ) 行中的每一项
20+
- 。。。
21+
22+
23+
24+
## 杨辉三角
25+
26+
题目来源于 LeetCode 上第 118 号问题:杨辉三角。题目难度为 Easy,目前通过率为 61.8% 。
27+
28+
### 题目描述
29+
30+
给定一个非负整数 *numRows,*生成杨辉三角的前 *numRows* 行。
31+
32+
![img](https://upload.wikimedia.org/wikipedia/commons/0/0d/PascalTriangleAnimated2.gif)
33+
34+
在杨辉三角中,每个数是它左上方和右上方的数的和。
35+
36+
**示例:**
37+
38+
```
39+
输入: 5
40+
输出:
41+
[
42+
[1],
43+
[1,1],
44+
[1,2,1],
45+
[1,3,3,1],
46+
[1,4,6,4,1]
47+
]
48+
```
49+
50+
### 题目解析
51+
52+
> 这道题目在各大高校的习题中经常出现。
53+
54+
对于本题而言,利用性质 1 :每一行的首个和结尾一个数字都是 1,从第三行开始,中间的每个数字都是上一行的左右两个数字之和。
55+
56+
### 代码实现
57+
58+
```java
59+
class Solution {
60+
public List<List<Integer>> generate(int numRows) {
61+
62+
List<List<Integer>> result = new ArrayList<>();
63+
if (numRows < 1) return result;
64+
65+
for (int i = 0; i < numRows; ++i) {
66+
//扩容
67+
List<Integer> list = Arrays.asList(new Integer[i+1]);
68+
list.set(0, 1); list.set(i, 1);
69+
for (int j = 1; j < i; ++j) {
70+
//等于上一行的左右两个数字之和
71+
list.set(j, result.get(i-1).get(j-1) + result.get(i-1).get(j));
72+
}
73+
result.add(list);
74+
}
75+
return result;
76+
77+
}
78+
}
79+
80+
```
81+
82+
83+
84+
## 杨辉三角II
85+
86+
题目来源于 LeetCode 上第 119 号问题:杨辉三角II。题目难度为 Easy,目前通过率为 55.5% 。
87+
88+
### 题目描述
89+
90+
给定一个非负索引 *k*,其中 *k* ≤ 33,返回杨辉三角的第 *k* 行。
91+
92+
![img](https://upload.wikimedia.org/wikipedia/commons/0/0d/PascalTriangleAnimated2.gif)
93+
94+
在杨辉三角中,每个数是它左上方和右上方的数的和。
95+
96+
**示例:**
97+
98+
```
99+
输入: 3
100+
输出: [1,3,3,1]
101+
```
102+
103+
**进阶:**
104+
105+
你可以优化你的算法到 *O*(*k*) 空间复杂度吗?
106+
107+
### 题目解析
108+
109+
这道题目的难点与思考点在于题目有额外限制条件,程序只能使用 O(k) 的额外空间,因此无法通过累加的方式将每一行都输出打印。
110+
111+
这里依旧使用杨辉三角的规律,很隐藏的规律:对于杨辉三角的同一行,第 ( i + 1) 项是第 i 项的` ( k - i ) /( i + 1 )` 倍。
112+
113+
比如:
114+
115+
- 第 k 索引行的第 0 项:1
116+
- 第 k 索引行的第 1 项:1 * k
117+
- 第 k 索引行的第 2 项:1 * k * ( k - 1) / 2
118+
- 第 k 索引行的第 3 项:[1 * k * ( k - 1) / 2 ] * ( k - 2 ) / 3
119+
120+
121+
122+
### 代码实现
123+
124+
```java
125+
class Solution {
126+
public List<Integer> getRow(int rowIndex) {
127+
List<Integer> res = new ArrayList<>(rowIndex + 1);
128+
long index = 1;
129+
for (int i = 0; i <= rowIndex; i++) {
130+
res.add((int) index);
131+
index = index * ( rowIndex - i ) / ( i + 1 );
132+
}
133+
return res;
134+
}
135+
}
136+
```
137+
138+
139+
140+
## 一个有趣的结论
141+
142+
感兴趣小伙伴的可以搜索一下李永乐讲得抽奖概率相关的视频,里面提及到了很多杨辉三角的神奇特点。
143+
![](https://bucket-1257126549.cos.ap-guangzhou.myqcloud.com/20190509165331.gif)
144+
145+
146+
![](https://bucket-1257126549.cos.ap-guangzhou.myqcloud.com/blog/fz0rq.png)

‎notes/LeetCode第2号问题:两数相加.md

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -35,6 +35,14 @@
3535
```
3636
/// 时间复杂度: O(n)
3737
/// 空间复杂度: O(n)
38+
/**
39+
* Definition for singly-linked list.
40+
* public class ListNode {
41+
* int val;
42+
* ListNode next;
43+
* ListNode(int x) { val = x; }
44+
* }
45+
*/
3846
class Solution {
3947
public:
4048
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {

0 commit comments

Comments
(0)

AltStyle によって変換されたページ (->オリジナル) /