0%

leetcode 118 Pascal's Triangle || 119 Pascal's Triangle II

本次题解包括

  • 118. Pascal's Triangle
  • 119. Pascal's Triangle II

118. Pascal's Triangle

Given numRows, generate the first numRows of Pascal's triangle.

For example, given numRows = 5, Return

1
2
3
4
5
6
7
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]

题目地址:leetcode Pascal's Triangle

题目大意:给定n返回前n行杨辉三角

思路:看代码吧

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> ans;
if(numRows < 1) return ans;
ans.push_back(vector<int>{1});
for(int i = 1; i < numRows; ++i){
vector<int> cur(i + 1, 0);
for(int j = 0; j <= i; ++j)
cur[j] = (j != i? ans[i - 1][j]:0) + (j > 0? ans[i - 1][j - 1]: 0);
ans.push_back(cur);
}
return ans;
}
};

Python

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
def generate(self, numRows):
"""
:type numRows: int
:rtype: List[List[int]]
"""
ans=[[1], [1,1]]
for i in range(1, numRows + 1):
temp = [1]+ [ans[-1][t] + ans[-1][t + 1] for t in range(len(ans[-1]) - 1)] + [1]
ans.append(temp)
return ans[:numRows]

 


119. Pascal's Triangle II

Given an index k, return the _k_th row of the Pascal's triangle.

For example, given k = 3, Return [1,3,3,1].

Note: Could you optimize your algorithm to use only O(k) extra space?

题目地址:leetcode Pascal's Triangle II

题目大意:给定n返回第n行杨辉三角(下标从0开始)

思路:看代码

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
vector<int> getRow(int k) {
vector<int> cur(k + 1, 0);
cur[0] = 1;
for(int i = 1; i <= k; ++i){
vector<int> next(i + 1, 1);
for(int j = 1; j < i; ++j)
next[j] = cur[j - 1] + cur[j];
cur = next;
}
return cur;
}
};

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
def getRow(self, rowIndex):
"""
:type rowIndex: int
:rtype: List[int]
"""
ans = [[1], [1, 1]]
if rowIndex < 2: return ans[rowIndex]
pre = ans[-1]
for i in range(1, rowIndex):
temp = [1] + [pre[t] + pre[t + 1] for t in range(len(pre) - 1)] + [1]
pre = temp
return pre

本文是leetcode如下的题解

  • 118. Pascal's Triangle
  • 119. Pascal's Triangle II

更多题解可以查看: https://www.hrwhisper.me/leetcode-algorithm-solution/

请我喝杯咖啡吧~