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输入输出

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();具体代码如下：

需要了解更多c/c++开发分享Leetcode No.119 Pascal's Triangle II(c++实现），都可以关注C/C++技术分享栏目—计算机技术网(www.ctvol.com)!

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;     } };