本次题解包括
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/