题目描述
给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| void gen(int numRows, vector<vector<int>>& vec)
{
if (numRows == 1)
{
vec.push_back({ 1 });
return;
}
else
{
gen(numRows - 1, vec);
vector<int> t = { 1 };
vector<int> p = vec.back();
for (int i = 1; i < numRows - 1; i++)
t.push_back(p[i] + p[i - 1]);
t.push_back(1);
vec.push_back(t);
return;
}
}
vector<vector<int>> generate(int numRows) {
vector<vector<int>> res;
if (!numRows)return res;
gen(numRows, res);
return res;
}
|
题目描述
给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。
进阶：
你可以优化你的算法到 O(k) 空间复杂度吗？
题解
O(k)？观察一下下面的规律就好写了，类似于，优化空间的动态规划的方法。
1
2
3
4
5
| [1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| vector<int> getRow(int rowIndex) {
if (rowIndex == 0)return { 1 };
vector<int> p;
vector<int> res = { 1 };
for (int i = 0; i < rowIndex; i++)
res.push_back(0);
p = res;
for (int j = 2; j < rowIndex+2; j++)
{
for (int i = 1; i < j; i++)
{
res[i] = p[i - 1] + p[i];
}
p = res;
}
return res;
}
|
执行用时 :0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗 :6.5 MB, 在所有 C++ 提交中击败了100.00%的用户
666