LeetCode 119 杨辉三角 II 解题方法详解

LeetCode 119 杨辉三角 II 解题方法详解

引用

CSDN

1.

https://m.blog.csdn.net/weixin_45979582/article/details/138077963

一、问题描述

给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。在「杨辉三角」中，每个数是它左上方和右上方的数的和。

自我注解：实际上rowIndex是从0开始的

二、示例及约束

示例 1：

输入：rowIndex = 3
输出：[1,3,3,1]

示例 2：

输入：rowIndex = 0
输出：[1]

示例 3：

输入：rowIndex = 1
输出：[1,1]

提示：

• 1 <= numRows <= 33

三、代码

方法一：递推

class Solution {
public:
    vector<vector<int>> generate(int rowIndex) {
        vector<vector<int>> ret(rowIndex + 1);
        for (int i = 0; i <= rowIndex; i++) {
            ret[i].resize(i + 1);
            ret[i][0] = ret[i][i] = 1;
            for (int j = 1; j <= i / 2; j++) {
                ret[i][j] = ret[i - 1][j -1] + ret[i - 1][j];
                if (i - j != j) {
                    ret[i][i - j] = ret[i][j];
                }
            }
        }
        return ret[rowIndex];
    }
};

// 优化版本
class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> pre, cur;
        for (int i = 0; i <= rowIndex; ++i) {
            cur.resize(i + 1);
            cur[0] = cur[i] = 1;
            for (int j = 1; j < i; ++j) {
                cur[j] = pre[j - 1] + pre[j];
            }
            pre = cur;
        }
        return pre;
    }
};

// 进一步优化
class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> row(rowIndex + 1);
        row[0] = 1;
        for (int i = 1; i <= rowIndex; ++i) {
            for (int j = i; j > 0; --j) {
                row[j] += row[j - 1];
            }
        }
        return row;
    }
};

方法二：线性递推

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> row(rowIndex + 1);
        row[0] = 1;
        for (int i = 1; i <= rowIndex; ++i) {
            row[i] = 1LL * row[i - 1] * (rowIndex - i + 1) / i;
        }
        return row;
    }
};

四、总结

• 时间复杂度：

• 方法一：$O(rowIndex^2)$

• 方法二：$O(rowIndex)$

• 空间复杂度：

• 方法一：$O(1)$（不考虑返回的数组空间）

• 方法二：$O(1)$（不考虑返回的数组空间）