Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
输出有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 };

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理