118.Pascal's Triangle

Tags: Easy Array

Links: https://leetcode.com/problems/pascals-triangle/

---

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

---

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> res;
        if (numRows == 0) return res; //输入为非负数，可能为零

        res.push_back({1});
        for (int i = 1; i < numRows; ++i) {
            if (i == 1) res.push_back({1, 1});
            else {
                vector<int> tmp;
                tmp.push_back(1);
                for (int j = 0, k = 1; k < res[i - 1].size(); ++j, ++k) {
                    tmp.push_back(res[i - 1][j] + res[i - 1][k]);
                }
                tmp.push_back(1);
                res.push_back(tmp);
            }
        }

        return res;
    }
};

纯模拟的做法，其实还可以让代码更精简一些。

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> res(numRows, vector<int>());
        for (int i = 0; i < numRows; ++i) {
            res[i].resize(i + 1, 1);
            for (int j = 1; j < i; ++j) {
                res[i][j] = res[i - 1][j - 1] + res[i - 1][j];
            }
        }

        return res;
    }
};