题目描述

题目链接：119. Pascal’s Triangle II

Given a non-negative index k where k ≤ 33, return the kth index row of the Pascal’s triangle.

Note that the row index starts from 0.

In Pascal’s triangle, each number is the sum of the two numbers directly above it.

例子

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

Follow Up

Could you optimize your algorithm to use only O(k) extra space?

解题思路

这道题的思路也比较简单，只需要找到每一行和上一行的之间的关系：除了首尾元素是 1，其他位置 i 都满足 currentRow[i] = lastRow[i - 1] + lastRow[i]，然后用循环模拟即可：

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> row;
        for (int i = 0; i <= rowIndex; i++) {
            vector<int> nextRow(i + 1, 1);
            for (int j = 1; j < nextRow.size() - 1; j++) {
                nextRow[j] = row[j - 1] + row[j];
            }
            row = nextRow;
        }

        return row;
    }
};

• 时间复杂度: O(k^2)
• 空间复杂度: O(k)