Skip to content

Commit 99fba31

Browse files
yanglbmeyanglbme
committed
feat: update solutions to lc problem: No.0119. Pascals Triangle II
1 parent 0844084 commit 99fba31

File tree

7 files changed

+85
-80
lines changed

7 files changed

+85
-80
lines changed

‎README.md

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -183,6 +183,8 @@
183183
- [解码方法](./solution/0000-0099/0091.Decode%20Ways/README.md)
184184
- [不同的二叉搜索树](./solution/0000-0099/0096.Unique%20Binary%20Search%20Trees/README.md)
185185
- [丑数 II](./solution/0200-0299/0264.Ugly%20Number%20II/README.md)
186+
- [杨辉三角](./solution/0100-0199/0118.Pascal%27s%20Triangle/README.md)
187+
- [杨辉三角 II](./solution/0100-0199/0119.Pascal%27s%20Triangle%20II/README.md)
186188
- [礼物的最大价值](./lcof/面试题47.%20礼物的最大价值/README.md)
187189
- [最小路径和](./solution/0000-0099/0064.Minimum%20Path%20Sum/README.md)
188190
- [最长上升子序列](./solution/0300-0399/0300.Longest%20Increasing%20Subsequence/README.md)

‎README_EN.md

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -177,6 +177,8 @@ Complete solutions to [LeetCode](https://leetcode.com/problemset/all/), [LCOF](h
177177
- [Decode Ways](./solution/0000-0099/0091.Decode%20Ways/README_EN.md)
178178
- [Unique Binary Search Trees](./solution/0000-0099/0096.Unique%20Binary%20Search%20Trees/README_EN.md)
179179
- [Ugly Number II](./solution/0200-0299/0264.Ugly%20Number%20II/README_EN.md)
180+
- [Pascal's Triangle](./solution/0100-0199/0118.Pascal%27s%20Triangle/README_EN.md)
181+
- [Pascal's Triangle II](./solution/0100-0199/0119.Pascal%27s%20Triangle%20II/README_EN.md)
180182
- [Minimum Path Sum](./solution/0000-0099/0064.Minimum%20Path%20Sum/README_EN.md)
181183
- [Longest Increasing Subsequence](./solution/0300-0399/0300.Longest%20Increasing%20Subsequence/README_EN.md)
182184
- [Russian Doll Envelopes](./solution/0300-0399/0354.Russian%20Doll%20Envelopes/README_EN.md)

‎solution/0100-0199/0119.Pascal's Triangle II/README.md

Lines changed: 31 additions & 24 deletions
Original file line numberDiff line numberDiff line change
@@ -36,24 +36,11 @@
3636
```python
3737
class Solution:
3838
def getRow(self, rowIndex: int) -> List[int]:
39-
def makePascal(prevArr):
40-
if len(prevArr) == 0:
41-
return [1]
42-
elif len(prevArr) == 1:
43-
return [1, 1]
44-
else:
45-
NewArr = [0] * (len(prevArr) + 1)
46-
NewArr[0], NewArr[-1] = 1, 1
47-
for i in range(len(prevArr) - 1):
48-
NewArr[i + 1] = prevArr[i] + prevArr[i + 1]
49-
return NewArr
50-
51-
temp = []
52-
Pascal = []
53-
for i in range(rowIndex + 1):
54-
temp = makePascal(temp)
55-
Pascal.append(temp)
56-
return Pascal[rowIndex]
39+
row = [1] * (rowIndex + 1)
40+
for i in range(2, rowIndex + 1):
41+
for j in range(i - 1, 0, -1):
42+
row[j] += row[j - 1]
43+
return row
5744
```
5845

5946
### **Java**
@@ -63,17 +50,37 @@ class Solution:
6350
```java
6451
class Solution {
6552
public List<Integer> getRow(int rowIndex) {
66-
List<Integer> ret = new LinkedList<>();
67-
long nk = 1;
68-
for (int i = 0; i <= rowIndex; i++) {
69-
ret.add((int) nk);
70-
nk = nk * (rowIndex - i) / (i + 1);
53+
List<Integer> row = new ArrayList<>();
54+
for (int i = 0; i < rowIndex + 1; ++i) {
55+
row.add(1);
7156
}
72-
return ret;
57+
for (int i = 2; i < rowIndex + 1; ++i) {
58+
for (int j = i - 1; j > 0; --j) {
59+
row.set(j, row.get(j) + row.get(j - 1));
60+
}
61+
}
62+
return row;
7363
}
7464
}
7565
```
7666

67+
### **C++**
68+
69+
```cpp
70+
class Solution {
71+
public:
72+
vector<int> getRow(int rowIndex) {
73+
vector<int> row(rowIndex + 1, 1);
74+
for (int i = 2; i < rowIndex + 1; ++i) {
75+
for (int j = i - 1; j > 0; --j) {
76+
row[j] += row[j - 1];
77+
}
78+
}
79+
return row;
80+
}
81+
};
82+
```
83+
7784
### **Go**
7885
7986
```go

‎solution/0100-0199/0119.Pascal's Triangle II/README_EN.md

Lines changed: 31 additions & 24 deletions
Original file line numberDiff line numberDiff line change
@@ -39,42 +39,49 @@
3939
```python
4040
class Solution:
4141
def getRow(self, rowIndex: int) -> List[int]:
42-
def makePascal(prevArr):
43-
if len(prevArr) == 0:
44-
return [1]
45-
elif len(prevArr) == 1:
46-
return [1, 1]
47-
else:
48-
NewArr = [0] * (len(prevArr) + 1)
49-
NewArr[0], NewArr[-1] = 1, 1
50-
for i in range(len(prevArr) - 1):
51-
NewArr[i + 1] = prevArr[i] + prevArr[i + 1]
52-
return NewArr
53-
54-
temp = []
55-
Pascal = []
56-
for i in range(rowIndex + 1):
57-
temp = makePascal(temp)
58-
Pascal.append(temp)
59-
return Pascal[rowIndex]
42+
row = [1] * (rowIndex + 1)
43+
for i in range(2, rowIndex + 1):
44+
for j in range(i - 1, 0, -1):
45+
row[j] += row[j - 1]
46+
return row
6047
```
6148

6249
### **Java**
6350

6451
```java
6552
class Solution {
6653
public List<Integer> getRow(int rowIndex) {
67-
List<Integer> ret = new LinkedList<>();
68-
long nk = 1;
69-
for (int i = 0; i <= rowIndex; i++) {
70-
ret.add((int) nk);
71-
nk = nk * (rowIndex - i) / (i + 1);
54+
List<Integer> row = new ArrayList<>();
55+
for (int i = 0; i < rowIndex + 1; ++i) {
56+
row.add(1);
7257
}
73-
return ret;
58+
for (int i = 2; i < rowIndex + 1; ++i) {
59+
for (int j = i - 1; j > 0; --j) {
60+
row.set(j, row.get(j) + row.get(j - 1));
61+
}
62+
}
63+
return row;
7464
}
7565
}
7666
```
7767

68+
### **C++**
69+
70+
```cpp
71+
class Solution {
72+
public:
73+
vector<int> getRow(int rowIndex) {
74+
vector<int> row(rowIndex + 1, 1);
75+
for (int i = 2; i < rowIndex + 1; ++i) {
76+
for (int j = i - 1; j > 0; --j) {
77+
row[j] += row[j - 1];
78+
}
79+
}
80+
return row;
81+
}
82+
};
83+
```
84+
7885
### **Go**
7986
8087
```go

‎solution/0100-0199/0119.Pascal's Triangle II/Solution.cpp

Lines changed: 5 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -1,15 +1,12 @@
11
class Solution {
22
public:
33
vector<int> getRow(int rowIndex) {
4-
vector<int> ans;
5-
6-
for(int i = 0;i <= rowIndex;i++){
7-
for(int j = i-1;j > 0;j--){
8-
ans[j] = ans[j-1] + ans[j];
4+
vector<int> row(rowIndex + 1, 1);
5+
for (int i = 2; i < rowIndex + 1; ++i) {
6+
for (int j = i - 1; j > 0; --j) {
7+
row[j] += row[j - 1];
98
}
10-
ans.push_back(1);
119
}
12-
return ans;
13-
10+
return row;
1411
}
1512
};

‎solution/0100-0199/0119.Pascal's Triangle II/Solution.java

Lines changed: 9 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -1,11 +1,14 @@
11
class Solution {
22
public List<Integer> getRow(int rowIndex) {
3-
List<Integer> ret = new LinkedList<>();
4-
long nk = 1;
5-
for (int i = 0; i <= rowIndex; i++) {
6-
ret.add((int) nk);
7-
nk = nk * (rowIndex - i) / (i + 1);
3+
List<Integer> row = new ArrayList<>();
4+
for (int i = 0; i < rowIndex + 1; ++i) {
5+
row.add(1);
86
}
9-
return ret;
7+
for (int i = 2; i < rowIndex + 1; ++i) {
8+
for (int j = i - 1; j > 0; --j) {
9+
row.set(j, row.get(j) + row.get(j - 1));
10+
}
11+
}
12+
return row;
1013
}
1114
}

‎solution/0100-0199/0119.Pascal's Triangle II/Solution.py

Lines changed: 5 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -1,20 +1,7 @@
11
class Solution:
22
def getRow(self, rowIndex: int) -> List[int]:
3-
def makePascal(prevArr):
4-
if len(prevArr) == 0:
5-
return [1]
6-
elif len(prevArr) == 1:
7-
return [1, 1]
8-
else:
9-
NewArr = [0] * (len(prevArr) + 1)
10-
NewArr[0], NewArr[-1] = 1, 1
11-
for i in range(len(prevArr) - 1):
12-
NewArr[i + 1] = prevArr[i] + prevArr[i + 1]
13-
return NewArr
14-
15-
temp = []
16-
Pascal = []
17-
for i in range(rowIndex + 1):
18-
temp = makePascal(temp)
19-
Pascal.append(temp)
20-
return Pascal[rowIndex]
3+
row = [1] * (rowIndex + 1)
4+
for i in range(2, rowIndex + 1):
5+
for j in range(i - 1, 0, -1):
6+
row[j] += row[j - 1]
7+
return row

0 commit comments

Comments
 (0)