杨辉三角问题描述

杨辉三角是一个经典的数学问题，其形式如下：

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
...

每一行的首尾元素为 1，其余元素为上一行相邻两个元素之和。

Java 顺序表实现思路

使用 List<List<Integer>> 存储杨辉三角的每一行。外层列表存储所有行，内层列表存储每一行的元素。

实现步骤

初始化结果列表 创建一个 List<List<Integer>> 对象存储结果，并初始化第一行为 [1]。

生成每一行 从第二行开始，每一行的生成基于上一行的元素：

• 每一行的第一个元素为 1。
• 中间元素为上一行的第 j-1 个和第 j 个元素之和。
• 每一行的最后一个元素为 1。

添加行到结果列表 将生成的每一行添加到结果列表中，直到生成所需行数。

完整代码实现

import java.util.ArrayList;
import java.util.List;

public class PascalTriangle {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> triangle = new ArrayList<>();
        if (numRows <= 0) {
            return triangle;
        }
        
        // 初始化第一行
        List<Integer> firstRow = new ArrayList<>();
        firstRow.add(1);
        triangle.add(firstRow);
        
        // 生成后续行
        for (int i = 1; i < numRows; i++) {
            List<Integer> prevRow = triangle.get(i - 1);
            List<Integer> currentRow = new ArrayList<>();
            
            // 每一行的第一个元素为1
            currentRow.add(1);
            
            // 中间元素为上一行相邻元素之和
            for (int j = 1; j < i; j++) {
                currentRow.add(prevRow.get(j - 1) + prevRow.get(j));
            }
            
            // 每一行的最后一个元素为1
            currentRow.add(1);
            
            triangle.add(currentRow);
        }
        
        return triangle;
    }
}

代码解析

初始化第一行

List<Integer> firstRow = new ArrayList<>();
firstRow.add(1);
triangle.add(firstRow);

• 创建第一行 [1] 并添加到结果列表中。

生成后续行

for (int i = 1; i < numRows; i++) {
    List<Integer> prevRow = triangle.get(i - 1);
    List<Integer> currentRow = new ArrayList<>();
    currentRow.add(1);
    
    for (int j = 1; j < i; j++) {
        currentRow.add(prevRow.get(j - 1) + prevRow.get(j));
    }
    
    currentRow.add(1);
    triangle.add(currentRow);
}

• 外层循环从第二行开始生成。
• 内层循环计算中间元素的值，即上一行相邻元素之和。
• 每一行的首尾元素固定为 1。

时间复杂度分析

• 生成每一行的时间复杂度为 O(n)，其中 n 为行数。
• 总体时间复杂度为 O(n²)，因为需要生成 n 行，每行的生成时间为 O(n)。

空间复杂度分析

• 存储结果的空间复杂度为 O(n²)，因为需要存储所有行的元素。

示例运行

输入

PascalTriangle solution = new PascalTriangle();
List<List<Integer>> result = solution.generate(5);
System.out.println(result);

输出

[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]

边界情况处理

• 如果 numRows 为 0，直接返回空列表。
• 如果 numRows 为 1，返回只包含第一行的列表。

总结

通过顺序表逐行生成杨辉三角，逻辑清晰且易于实现。代码通过动态规划的思想，利用上一行的结果生成当前行，保证了高效性和正确性。