Leetcode No.119 Pascal's Triangle II(c++实现）

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