【数据结构基础

原题链接：Leetcode 119. Pascal’s Triangle II

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:

Example 1:

Input: rowIndex = 3
Output: [1,3,3,1]

Example 2:

Input: rowIndex = 0
Output: [1]

Example 3:

Input: rowIndex = 1
Output: [1,1]

Constraints:

• 0 <= rowIndex <= 33

Follow up:
Could you optimize your algorithm to use only O(rowIndex) extra space?

构造完整的杨辉三角，然后输入第n行即可

class Solution {
public:
    vector getRow(int rowIndex) {
        vector> ans(rowIndex + 1);

        for(int i = 0; i <= rowIndex; 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];
    }
};

• 时间复杂度：O(rowIndex²)，总共计算1 + 2 + …… + rowIndex
• 空间复杂度：O(1)，返回值不算入复杂度

原先在二维数组中存了1~n行，最终只输出了第n行，可以对空间复杂度进行优化
采用 更新数组 的思想，但每次更新时从后往前更新，这样不影响后面的数

class Solution {
public:
    vector getRow(int rowIndex) {
        vector ans(rowIndex + 1);
        ans[0] = 1;

        for (int i = 1; i <= rowIndex; i++ ) {

            // 从后往前更新
            for (int j = i; j > 0; --j) {
                ans[j] = ans[j] + ans[j - 1];
            }
        }
        return ans;
    }
};

• 时间复杂度：O(rowIndex²)，时间复杂度不变
• 空间复杂度：O(1)，只用了一个一维数组，并且输出不算入复杂度