LeetCode: 119. Pascal’s Triangle II

题目描述

Given an index k, return the kth row of the Pascal’s triangle.

For example, given k = 3,
Return [1,3,3,1].

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

题目大意: 输出杨辉三角的第 k 行(从第 0 行开始算起)，要求空间复杂度为 O(n)。

解题思路 —— 递归求解

解题思路同 LeetCode: 118. Pascal’s Triangle 题解，先求到第 k-1 行的数据，再根据第 k-1 行的数据算出第 k 行。需要注意的是，这一题是从第 0 行开始算起的。

AC 代码

class Solution {
public:
    vector<int> getRow(int rowIndex) {

         // 结束条件
        if(rowIndex == 0) return {{1}};

        // 获取上一行的序列
        vector<int> lastRow = getRow(rowIndex - 1);

        // 根据第 numRows - 1 行，求出 numRows 行
        vector<int> curRow;
        curRow.push_back(1);
        for(size_t i = 1; i < lastRow.size(); ++i)
        {
            curRow.push_back(lastRow[i-1] + lastRow[i]);
        }
        curRow.push_back(1);

        return curRow;
    }
};