119. 杨辉三角 II

难度：简单

题目

给定一个非负索引\(k\)，其中\(k\leq33\)，返回杨辉三角的第\(k\) 行。

在杨辉三角中，每个数是它左上方和右上方的数的和。

示例：

输入: 3
输出: [1,3,3,1]

进阶：

你可以优化你的算法到\(O(k)\)空间复杂度吗？

Reference

题解

基本思路： 当前行的结果仅依赖于上一行的结果，因此可以使用动态规划。

代码如下：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
void recur(int rowIndex, int *Filling)
{
    if (rowIndex <= 1)
        return;
    recur(rowIndex - 1, Filling);
    for (int i = rowIndex - 1; i > 0; i--)
        Filling[i] += Filling[i - 1];
}

int* getRow(int rowIndex, int* returnSize){
    *returnSize = rowIndex + 1;
    int *ret = (int *)memset(malloc(sizeof(int) * *returnSize), 0, sizeof(int) * *returnSize);
    ret[0] = 1;
    recur(*returnSize, ret);
    return ret;
}

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        row = [0] * (rowIndex + 1)
        row[0] = 1
        for currentRow in range(1, rowIndex + 1):
            for idx in range(currentRow, 0, -1):
                row[idx] = row[idx - 1] + row[idx]
        return row

评论