118. Pascal's Triangle
118. Pascal's Triangle
难度：Easy
内容
题目链接：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]
]
思路
该题比较简单，杨辉三角形，从第三行开始，除了首尾，中间元素的值可通过如下公式计算：cur[i] = prev[i] + prev[i-1]
计算当前行实现要点如下：
- 拷贝上一行，并在末尾添加元素1
- 倒着开始计算，除了首尾，
cur[i] += cur[i-1]
代码
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> res;
for (auto i = 0; i < numRows; ++i) {
vector<int> row;
if (!res.empty())
row.assign(res.at(i-1).begin(), res.at(i-1).end());
row.emplace_back(1);
for (auto j = i - 1; j > 0; --j)
row[j] += row[j-1];
res.emplace_back(row);
}
return res;
}
};
来源：https://github.com/xiaqunfeng/leetcode
