118 杨辉三角

一、题目

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

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

二、题解

思路： 逐行构造。第 i 行有 i + 1 个元素，每行两端固定为 1；中间的每个数等于上一行相邻两数之和，即 ans[i][j] = ans[i-1][j-1] + ans[i-1][j]。从上往下递推即可生成整个三角形。

class Solution {
    public List<List<Integer>> generate(int numRows) {

        // 【初始化最终的结果容器】
        // ans 用于存放整个杨辉三角，它是一个“列表的列表”（你可以理解为一个不规则的二维数组）。
        List<List<Integer>> ans = new ArrayList<List<Integer>>();

        // 【外层循环：逐行生成】
        // i 代表当前正在生成的“行号”（从 0 开始计数，第 0 行即金字塔最顶端的那一行）。
        for(int i = 0; i < numRows; i++) {

            // 每次来到新的一行，都创建一个新的空列表 row，用于存放这一行的数字
            List<Integer> row = new ArrayList<Integer>();

            // 【内层循环：生成当前行的每一个元素】
            // j 代表当前行中的“位置索引”。
            // 注意循环条件是 j <= i：因为杨辉三角的特性是，第 i 行恰好有 i + 1 个元素。
            // （例如：第 0 行有 1 个元素，第 2 行有 3 个元素）
            for(int j = 0; j <= i; j++) {

                // 逻辑分支 1：处理两端的边界元素
                // 每行的最左侧 (j == 0) 和最右侧 (j == i)，数字永远都是 1。
                if(j == 0 || j == i) {
                    row.add(1);
                }

                // 逻辑分支 2：处理中间的元素（核心递推逻辑）
                // 规律：当前数字 = 上一行左前方的数字 + 上一行右前方的数字
                else {
                    // ans.get(i-1) 获取的是“上一行”的完整列表。
                    // .get(j-1) 获取的是上一行对应左上角的元素。
                    // .get(j)   获取的是上一行对应右上角的元素。
                    row.add(ans.get(i-1).get(j-1) + ans.get(i-1).get(j));
                }
            }

            // 【组装结果】
            // 当内层循环结束，说明当前这一行的所有数字都已经计算完毕。
            // 将拼装好的当前行 row，整体加入到最终的结果 ans 中。
            ans.add(row);
        }

        // 所有行都生成完毕，返回完整的杨辉三角
        return ans;
    }
}

时间复杂度：O(numRows2)O(numRows^2)

空间复杂度：O(1)O(1)

评论