Java 顺序表实现杨辉三角思路与代码

Java 顺序表实现杨辉三角思路与代码

杨辉三角作为经典的数学与编程结合案例，是理解二维数组和动态列表操作的绝佳素材。我们将从逻辑拆解、问题分析等角度进行解析，彻底掌握其实现精髓。

一、思路分析

杨辉三角的核心规律在于：每一行的数字都是上一行两个相邻数字之和。第一列和最后一列固定为 1。

在实现时，我们可以创建一个二维列表 List<List<Integer>> 来存储整个三角结构。外层循环控制行数 i（从 0 到 numRows），内层循环处理列数 j（小于 i）。

具体逻辑如下：

• 每一行的第一个元素和最后一个元素直接赋值为 1。
• 中间的元素通过上一行相邻的两个元素相加得到，即 preRow.get(j) + preRow.get(j - 1)。

二、代码实现

这里使用 Java 的 ArrayList 来实现动态列表。注意导入必要的包，并确保类结构完整。

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;
    }
}

三、总结

杨辉三角虽然逻辑简单，但蕴含了丰富的数学规律和编程技巧。通过本文，我们掌握了利用二维列表生成杨辉三角的基本原理，理解了空间复杂度与迭代逻辑的结合。在实际开发中，这种递推思想常用于动态规划问题的初步建模。