[每日 LeetCode] 118. Pascal's Triangle

Description:

Given a non-negative integer numRows, generate the first numRows of Pascal's triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it.

Example:

Input: 5
Output:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]
​

思路：本题要求输出 Pascal 三角形，注意三角形每行和上一行的关系。考虑使用 for 循环，根据层数不同，依次向多维数组中加入个数为层数的一维数组。

C++ 代码

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ret;
        for (int i=0; i<numRows; i++){
            vector<int> temp(i+1);
            temp[0] = temp[i] = 1;
            for (int j=1; j<i;j++){
                temp[j] = ret[i-1][j] + ret[i-1][j-1];
            }
             ret.push_back(temp);
        }
        return ret;
    }
};
​

运行时间：4ms

运行内存：8.8M