Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

[LeetCode]Pascal's Triangle [& II]-2014.01.06

Posted on 2014-01-11 02:46 Uriel 阅读(113) 评论(0)  编辑 收藏 引用 所属分类: LeetCode
两题杨辉三角形的题

Pascal's Triangle:求前n行

 1 class Solution {
 2 public:
 3     vector<vector<int> > generate(int numRows) {
 4         int dp[2][10010];
 5         vector<vector<int> > res;
 6         for(int i = 1; i <= numRows; ++i) {
 7             vector<int> tp;
 8             for(int j = 1; j <= i; ++j) {
 9                 if(j == 1 || j == i) dp[i & 1][j] = 1;
10                 else
11                     dp[i & 1][j] = dp[(i - 1) & 1][j - 1] + dp[(i - 1) & 1][j];
12                 tp.push_back(dp[i & 1][j]);
13             }
14             res.push_back(tp);
15         }
16         return res;
17     }
18 };

Pascal's Triangle II:求第k行

 1 class Solution {
 2 public:
 3     vector<int> getRow(int rowIndex) {
 4         int dp[2][10010];
 5         vector<int> res;
 6         for(int i = 1; i <= rowIndex + 1; ++i) {
 7             for(int j = 1; j <= i; ++j) {
 8                 if(j == 1 || j == i) dp[i & 1][j] = 1;
 9                 else
10                     dp[i & 1][j] = dp[(i - 1) & 1][j - 1] + dp[(i - 1) & 1][j];
11                 if(i == rowIndex + 1) res.push_back(dp[i & 1][j]);
12             }
13         }
14         return res;
15     }
16 };

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