【LeetCode】118.杨辉三角

题目

要求：给定非负整数numRows，生成杨辉三角的前numRows行；
每个数等于它左上方和右上方的数之和。
示例：numRows=5输出[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]。

思路：按行迭代

• 先创建二维列表pascalTriangle用来存所有行。
• 手动初始化第 1 行：新建row0=[1]，加入pascalTriangle。
• 从第 2 行开始用for (i=1; i<numRows; i++)逐行生成（i是行下标）：
  • 首：手动add(1)
  • 中间：上一行第j个元素 + 上一行第(j-1)个元素
  • 尾：手动add(1)

补充：这份写法默认numRows>=1，否则会先加第一行导致结果不符合题意。需要在开头加if (numRows==0) return new ArrayList<>();。

https://leetcode.cn/problems/pascals-triangle/description/

code

classSolution{publicList<List<Integer>>generate(intnumRows){// 用来存放最终结果：杨辉三角的每一行都是一个 List<Integer>List<List<Integer>>pascalTriangle=newArrayList<>();// 第 1 行（下标 0）：固定为 [1]List<Integer>row0=newArrayList<>();row0.add(1);pascalTriangle.add(row0);// 从第 2 行开始生成（i 表示行下标：1 -> 第2行，2 -> 第3行 ...）for(inti=1;i<numRows;i++){List<Integer>tmpRow=newArrayList<>();// 每一行的第 1 个元素固定是 1tmpRow.add(1);// 取出上一行，用来计算当前行的中间元素List<Integer>preRow=pascalTriangle.get(i-1);// 计算中间元素：// 当前行第 j 个元素 = 上一行第 j 个元素 + 上一行第 (j-1) 个元素// j 从 1 到 i-1（不包含两侧的 1）for(intj=1;j<i;j++){tmpRow.add(preRow.get(j)+preRow.get(j-1));}// 每一行的最后 1 个元素固定是 1tmpRow.add(1);// 把当前行加入结果pascalTriangle.add(tmpRow);}// 返回完整的杨辉三角returnpascalTriangle;}}

补充：这段代码默认numRows >= 1；如果可能传入0，需要在开头加判断直接返回空列表。