Easy

题目描述

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

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

示例 1:

输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例 2:

输入: numRows = 1
输出: [[1]]

提示:

  • 1 <= numRows <= 30

解题思路

解题思路

杨辉三角是一个经典的数学结构，每一行的数字都是由上一行相邻两个数字相加得到的。

核心观察：

  1. 每行的第一个和最后一个元素都是 1
  2. 中间的元素等于上一行对应位置和前一个位置的元素之和
  3. 第 i 行有 i+1 个元素（从第0行开始计算）

算法步骤：

  1. 创建结果数组，第一行固定为 [1]
  2. 从第二行开始，逐行构建：
    • 每行开头和结尾都是 1
    • 中间元素通过 triangle[i-1][j-1] + triangle[i-1][j] 计算
  3. 将每一行添加到结果中

优化思路：

  • 可以考虑原地构建每一行，减少额外空间使用
  • 也可以利用组合数学公式直接计算，但实现复杂度较高

这道题主要考查对二维数组操作和动态规划思想的理解。时间复杂度为 O(numRows²)，空间复杂度为 O(1)（不计算返回结果的空间）。

代码实现

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> triangle;
        
        for (int i = 0; i < numRows; i++) {
            vector<int> row(i + 1, 1);
            
            for (int j = 1; j < i; j++) {
                row[j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
            }
            
            triangle.push_back(row);
        }
        
        return triangle;
    }
};

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        triangle = []
        
        for i in range(numRows):
            row = [1] * (i + 1)
            
            for j in range(1, i):
                row[j] = triangle[i - 1][j - 1] + triangle[i - 1][j]
            
            triangle.append(row)
        
        return triangle

public class Solution {
    public IList<IList<int>> Generate(int numRows) {
        IList<IList<int>> triangle = new List<IList<int>>();
        
        for (int i = 0; i < numRows; i++) {
            IList<int> row = new List<int>();
            
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i) {
                    row.Add(1);
                } else {
                    row.Add(triangle[i - 1][j - 1] + triangle[i - 1][j]);
                }
            }
            
            triangle.Add(row);
        }
        
        return triangle;
    }
}

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

复杂度分析

复杂度类型值说明
时间复杂度O(numRows²)需要生成 numRows 行，每行平均有 numRows/2 个元素需要计算
空间复杂度O(1)除了返回结果外，只使用了常数级别的额外空间

相关题目