[LeetCode]PASCAL Triangle系列

今天的练习题是triangle三件套：Triangle, PASCAL Triangle, PASCAL Triangle II. 

PASCAL Triangle就是小学奥数中的“杨辉三角”, 存在如下关系

triangle[i+1][j+1] = triangle[i][j]+triangle[i][j+1]

即第i+1行第j+1个元素为第i行第j个元素与第j+1个元素之和

PASCAL Triangle的题目要求：输出PASCAL Triangle的前numRows行

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]
]

根据生成规则，一个vector指向当前行，一个vector指向上一行，注意边界位置的下标不要越界

class Solution {
public:
    vector<vector<int> > generate(int numRows) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        
        vector<vector<int>> triangle;
        if(numRows<1)
            return triangle;
        
        vector<int> prev(1, 1); // [1]
        vector<int> cur;
        triangle.push_back(prev);
        
        for(int i=1; i<numRows; ++i)
        {
            for(int j=0; j<i+1; ++j)
            {
                int left = j>0?prev[j-1]:0; //注意下标为0的位置
                int right = j<i?prev[j]:0; //注意下标为i的位置
                cur.push_back(left+right);
            }
            triangle.push_back(cur);
            prev = cur;
            cur.clear();
        }
        
        return triangle;
    }
};

----------------------------------------------------

PASCAL Triangle II

与上一题类似，输出第rowIndex行PASCAL Triangle. 

N行的三角形，注意rowIndex的取值范围为[0, N-1]

原题

Given an index k, return the kth row of the Pascal's triangle.

For example, given k = 3,
Return [1,3,3,1].

代码

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        vector<int> prev(1, 1);
        
        if(rowIndex<1)
            return prev;
        
        vector<int> row;
        for(int i=1; i<rowIndex+1; ++i)
        {
            for(int j=0; j<i+1; ++j)
            {
                int left = j>0?prev[j-1]:0;
                int right = j<i?prev[j]:0;
                row.push_back(left+right);
            }
            prev = row;
            row.clear();
        }
        
        return prev;
    }
};