Java 动态列表实现杨辉三角算法解析

杨辉三角是数据结构里的经典题目，考察二维数组和动态列表的操作。今天咱们聊聊怎么用 Java 把它搞定。

思路分析

拿到这个题，先别急着写代码，看看规律：

1. 每一行的第一个和最后一个数字都是 1。
2. 中间的每个数字等于它上方两数之和。

用 List<List<Integer>> 来存储整个三角最方便，外层循环控制行数，内层循环处理列数。每一行首尾补 1，中间元素通过上一行相邻索引相加得到。

代码实现

这里直接上核心逻辑，注意导入必要的集合类包。

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

public class Test {
    public List<List<Integer>> generate(int numRows) {
        // 定义最终返回的嵌套列表
        List<List<Integer>> ret = new ArrayList<>();
        
        // 第 0 行特殊处理，直接放入 [1]
        if (numRows == 0) return ret;
        
        List<Integer> list0 = new ArrayList<>();
        list0.add(1);
        ret.add(list0);
        
        // 从第 1 行开始计算
        for (int i = 1; i < numRows; i++) {
            List<Integer> curRow = new ArrayList<>();
            
            // 每一行第一个数固定为 1
            curRow.add(1);
            
            // 获取上一行数据用于计算当前中间值
            List<Integer> preRow = ret.get(i - 1);
            
            // 处理中间元素：当前值 = 上一行同索引 + 上一行前一个索引
            for (int j = 1; j < i; j++) {
                int x = preRow.get(j) + preRow.get(j - 1);
                curRow.add(x);
            }
            
            // 每一行最后补 1
            curRow.add(1);
            
            // 将当前行加入结果集
            ret.add(curRow);
        }
        
        return ret;
    }
}

实际运行时会发现，随着行数增加，列表会自动扩容，无需手动管理内存，这正是 Java 集合框架的优势所在。

总结

杨辉三角虽然看起来简单，但它蕴含的数学规律和编程技巧值得我们学习。通过这篇文章，掌握了杨辉三角的基本原理和生成方法，以及二维列表和空间复杂度的基本应用。