Leetcode No.119 Pascal's Triangle II(c++实现)
程序员文章站
2022-06-19 12:16:54
1. 题目 1.1 英文题目 Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal's triangle. In Pascal's triangle, each number is the sum ......
1. 题目
1.1 英文题目
given an integer rowindex, return the rowindexth (0-indexed) row of the pascal's triangle.
in pascal's triangle, each number is the sum of the two numbers directly above it as shown:
1.2 中文题目
输出杨辉三角形的指定行
1.3输入输出
输入 | 输出 |
---|---|
rowindex = 3 | [1,3,3,1] |
rowindex = 0 | [1] |
rowindex = 1 | [1,1] |
1.4 约束条件
0 <= rowindex <= 33
2. 实验平台
ide:vs2019
ide版本:16.10.1
语言:c++11
3. 分析
这一题最简单粗暴的方法就是先求出到指定行的杨辉三角形,之后再取最后一行作为结果,代码为:
class solution { public: vector<int> getrow(int rowindex) { vector<vector<int>> ans(rowindex + 1); for(int i = 0; i < rowindex + 1; i++) { ans[i].resize(i + 1); ans[i][0] = ans[i][i] = 1; for(int j = 1; j < i; j++) { ans[i][j] = ans[i - 1][j - 1] + ans[i - 1][j]; } } return ans[rowindex]; } };
这样做也固然没问题,但是算法很冗杂,不够优化,我们可以适当优化下,不需要把所有行的结果都存储起来,只需要保存最后一行。新代码如下:
class solution { public: vector<int> getrow(int rowindex) { vector<int> ans; for(int i = 0; i < rowindex + 1; i++) { vector<int> temp(i + 1); temp[0] = temp[i] = 1; for(int j = 1; j < i; j++) { temp[j] = ans[j - 1] + ans[j]; } ans = temp; } return ans; } };
但是我们提交后发现算法时间和空间复杂度都没变,于是我在想还有没有优化空间,我发现每行计算时都需要重新定义temp,并为其开辟内存空间,有待优化,故可以将其提前定义,并在每行计算时重定义temp大小,代码如下:
class solution { public: vector<int> getrow(int rowindex) { vector<int> ans; vector<int> temp; for(int i = 0; i < rowindex + 1; i++) { temp.resize(i + 1); temp[0] = temp[i] = 1; for(int j = 1; j < i; j++) { temp[j] = ans[j - 1] + ans[j]; } ans = temp; } return ans; } };
这次性能不错。但是我觉得有个temp,还是很繁琐,那么能不能去掉temp呢,但是如果去掉temp,递推那一步就会涉及混乱,考虑到递推关系式是j-1和j,于是我们可以在递推时进行反向递推,代码如下:
class solution { public: vector<int> getrow(int rowindex) { vector<int> ans; for(int i = 0; i < rowindex + 1; i++) { ans.resize(i + 1); ans[0] = ans[i] = 1; for(int j = i - 1; j > 0; j--) ans[j] += ans[j - 1]; } return ans; } };
这次算法空间复杂度又提高了,另外,每次都要重新定义ans的尺寸,能不能不这么做呢?我想到每次循环只是比之前尺寸多1,因此可以不重新定义尺寸,而是尺寸加1,即使用push_back();具体代码如下:
class solution { public: vector<int> getrow(int rowindex) { vector<int> ans; for(int i = 0; i < rowindex + 1; i++) { ans.push_back(1); for(int j = i - 1; j > 0; j--) ans[j] += ans[j - 1]; } return ans; } };
推荐阅读
-
Leetcode No.119 Pascal's Triangle II(c++实现)
-
LeetCode-119. Pascal's Triangle II
-
leetcode -- 119. Pascal's Triangle II
-
2018.05.03 leetcode #119. Pascal's Triangle II
-
【leetcode】119. Pascal's Triangle II
-
LeetCode 119. Pascal's Triangle II
-
[LeetCode]119. Pascal's Triangle II
-
LeetCode119 Pascal's Triangle II Pascal三角形II
-
Leetcode No.119 Pascal's Triangle II(c++实现)
-
leetcode 119. Pascal's Triangle II 帕斯卡三角形(杨辉三角)(Python)