Posted on 2023-09-08 14:12
Uriel 閱讀(53)
評論(0) 編輯 收藏 引用 所屬分類:
閑來無事重切Leet Code 、
大水題
輸出有numRows行的帕斯卡三角形，大水題
python版
1 #118
2 #Runtime: 7 ms (Beats 99.45%)
3 #Memory: 13.3 MB (Beats 21.94%)
4
5 class Solution(object):
6 def generate(self, numRows):
7 """
8 :type numRows: int
9 :rtype: List[List[int]]
10 """
11 ans = [[1]]
12 for i in range(1, numRows):
13 t = [1]
14 for j in range(len(ans[i - 1]) - 1):
15 t.append(ans[i - 1][j] + ans[i - 1][j + 1])
16 t.append(1)
17 ans.append(t)
18 return ans
C++版
1 //118
2 //Runtime: 12 ms (Beats 11.67%)
3
4
5 class Solution {
6 public:
7 vector<vector<int> > generate(int numRows) {
8 int dp[2][10010];
9 vector<vector<int> > res;
10 for(int i = 1; i <= numRows; ++i) {
11 vector<int> tp;
12 for(int j = 1; j <= i; ++j) {
13 if(j == 1 || j == i) dp[i & 1][j] = 1;
14 else
15 dp[i & 1][j] = dp[(i - 1) & 1][j - 1] + dp[(i - 1) & 1][j];
16 tp.push_back(dp[i & 1][j]);
17 }
18 res.push_back(tp);
19 }
20 return res;
21 }
22 };