Easy

题目描述

给定一个非负整数 rowIndex，返回杨辉三角的第 rowIndex 行（下标从 0 开始）。

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

示例 1:

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

示例 2:

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

示例 3:

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

提示:

  • 0 <= rowIndex <= 33

进阶: 你可以优化你的算法到 O(rowIndex) 空间复杂度吗？

解题思路

解题思路

本题要求返回杨辉三角的第 rowIndex 行，有以下几种解法：

方法一：直接构造（推荐）

利用杨辉三角的性质，每一行都可以基于上一行计算得出。为了满足 O(rowIndex) 空间复杂度的要求，我们可以使用一个数组不断更新，从后往前计算，避免覆盖还未使用的值。

方法二：组合数公式

杨辉三角第 n 行第 k 个数字等于组合数 C(n,k)。可以直接用组合数公式计算：C(n,k) = n! / (k! * (n-k)!)。但需要注意溢出问题和优化计算过程。

方法三：递推优化

利用组合数的递推关系：C(n,k) = C(n,k-1) * (n-k+1) / k，这样可以避免大数计算。

方法一最直观且空间复杂度最优，是最推荐的解法。核心思想是从第0行开始，逐行计算到第 rowIndex 行，每次更新时从右往左遍历，确保不会覆盖还需要使用的值。

代码实现

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

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

public class Solution {
    public IList<int> GetRow(int rowIndex) {
        int[] row = new int[rowIndex + 1];
        Array.Fill(row, 1);
        
        for (int i = 1; i <= rowIndex; i++) {
            for (int j = i - 1; j >= 1; j--) {
                row[j] = row[j] + row[j - 1];
            }
        }
        
        return row.ToList();
    }
}

var getRow = function(rowIndex) {
    const row = new Array(rowIndex + 1).fill(1);
    
    for (let i = 1; i <= rowIndex; i++) {
        for (let j = i - 1; j >= 1; j--) {
            row[j] = row[j] + row[j - 1];
        }
    }
    
    return row;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(rowIndex²)
空间复杂度O(rowIndex)

说明:

  • 时间复杂度：需要计算从第1行到第rowIndex行，每行的计算量为O(i)，总计算量为1+2+…+rowIndex = O(rowIndex²)
  • 空间复杂度：只使用了一个长度为rowIndex+1的数组来存储结果，满足题目进阶要求

相关题目