LC118 杨辉三角

题目

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。

例 1:

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

示例 2:

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

示例3：
输入: numRows = 5
输出:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,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<>();

        for (int i = 0; i < numRows; i++) {
            List<Integer> row = new ArrayList<>();

            // 每一行的第一个元素都是 1
            row.add(1);

            // 如果不是第一行，且不是最后一行
            if (i > 0) {
                List<Integer> prevRow = triangle.get(i - 1);
                for (int j = 1; j < i; j++) {
                    // 当前行的每个元素是上一行相邻两个元素之和
                    row.add(prevRow.get(j - 1) + prevRow.get(j));
                }

                // 每一行的最后一个元素也是 1
                row.add(1);
            }

            triangle.add(row);
        }

        return triangle;
    }

    public static void main(String[] args) {
        PascalTriangle solution = new PascalTriangle();
        List<List<Integer>> result = solution.generate(5);
        System.out.println(result);
    }
}

注释和讲解

1. 我们首先导入了需要使用的类，包括 ArrayList 和 List。
2. 在 PascalTriangle 类中，我们定义了一个 generate 方法，接受一个整数参数 numRows，表示要生成的杨辉三角的行数。
3. 我们创建了一个名为 triangle 的二维列表，用于存储生成的杨辉三角。
4. 使用一个循环从 0 到 numRows - 1，每一次循环表示生成杨辉三角的一行。
5. 在每一行的生成过程中，我们创建一个名为 row 的一维列表，用于存储当前行的元素。
6. 每一行的第一个元素都是 1，所以我们将 1 添加到 row 列表中。
7. 如果不是第一行，且不是最后一行，我们就需要计算当前行的中间元素。这里我们使用了上一行的信息，即 triangle.get(i - 1) 得到上一行的列表。
8. 在内部循环中，我们遍历从 1 到 i - 1 的范围，这是因为每一行中间的元素个数为行数减 2。
9. 当前行的每个元素是上一行相邻两个元素之和，所以我们将上一行中索引为 j - 1 和 j 的两个元素相加，并将结果添加到当前行 row 中。
10. 每一行的最后一个元素也是 1，所以我们将 1 添加到 row 列表中。
11. 完成了当前行的生成后，我们将 row 列表添加到 triangle 列表中。
12. 最终，返回完整的 triangle 列表，即为所求的杨辉三角。