LeetCode Problem: Pascal’s Triangle

By | 2013 年 1 月 17 日

The problem is simple, each element in the triangle is the sum of two numbers above it.
这个题目简单,三角形中每一个元素的值是其上面两个值的和。

So, just build the rows one by one according the row above it. And the first row is {1}.
根据当前行的上面一层数字,就可以逐行生成整个三角形了。初值是第一行:{1}



Pascal’s Triangle Oct 28 ’12
Given numRows, generate the first numRows of Pascal’s triangle.
For example, given numRows = 5,
Return

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



Code, 12ms pass large test set

class Solution {
public:
    vector > generate(int numRows) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector >ret;
        if(numRows == 0) return ret;
        //first row
        ret.push_back(vector(1,1));
        //rest rows;
        for(int nr = 2; nr <= numRows; ++nr) {
            vector thisrow(nr,1);
            vector &lastrow = ret[nr-2];
            for(int ic = 1; ic < nr - 1; ++ic) {
                thisrow[ic] = lastrow[ic-1] + lastrow[ic];
            }
            ret.push_back(thisrow);
        }
        return ret;
    }
};

One thought on “LeetCode Problem: Pascal’s Triangle

  1. Pingback: LeetCode Problem: Pascal’s Triangle II - uniEagle

发表评论

电子邮件地址不会被公开。 必填项已用*标注