文章

[LeetCode] 每日一题 119. 杨辉三角 II

题目链接

https://leetcode.cn/problems/pascals-triangle-ii

题目描述

给定一个非负索引 rowIndex,返回「杨辉三角」的第 rowIndex 行。

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

示例输入

示例 1

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

示例 2

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

示例 3

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

提示

  • 0 <= rowIndex <= 33

解题思路

题目要求返回杨辉三角的第 rowIndex 行。杨辉三角的特点是:每个位置的数字是其左上方和右上方两个数字之和。对于第 rowIndex 行的数字,可以通过 组合数公式 来计算

  • 组合数公式的定义:第 rowIndex 行的第 m 个元素等于 C(rowIndex, m)

  • 初始值 C(rowIndex, 0) = 1,接着根据公式依次计算每个元素

这样我们可以在 O(rowIndex) 时间内计算出所有的元素,并避免使用额外空间

代码实现

class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> row = new ArrayList<Integer>();
        row.add(1);
        for (int i = 1; i <= rowIndex; ++i) {
            row.add(0);
            for (int j = i; j > 0; --j) {
                row.set(j, row.get(j) + row.get(j - 1));
            }
        }
        return row;
    }
}

复杂度分析

  • 时间复杂度:O(rowIndex)

    • 线性遍历从 0 到 rowIndex,每一步计算组合数所需时间为常数,因此时间复杂度为 O(rowIndex)

  • 空间复杂度:O(rowIndex)

    • 结果列表 row 占用的空间为 O(rowIndex)

总结

本题通过 线性递推 的方式,利用组合数公式高效地求解杨辉三角的第 rowIndex 行。代码简单且易于理解。与其他构造整个杨辉三角的解法相比,这种方法显著减少了时间和空间开销,非常适合只需要返回单行结果的场景

希望这篇分享能为你带来启发!如果你有任何问题或建议,欢迎在评论区留言,与我共同交流探讨。

License:  CC BY 4.0