一、题干
🔗力扣：118. 杨辉三角
二、题解
1. 思路
我们知道杨辉三角的规律是：
- 每一行的第一列和它的最后一列上的数均为1.
- 除此之外，每个数是它的左上方与右上方的数之和。如果用 i 代表行， j 代表列，则有：
[ i ][ j ] 等于 [ i-1 ][ j-1 ] + [ i-1 ][ j ]
本题的关键在于对ArrayList集合类的理解。在力扣上，该题的默认代码模板是这样的：
class Solution { public List<List<Integer>> generate(int numRows) { ... } }
因此，要完成这道题，我们需要先理清该函数的返回值 List<List<Integer>> 代表什么含义。
- 从外层的List可以看出，有一个List集合类容器，且容器中的每个元素的数据类型仍是List。本文中我们采用ArrayList集合类实现，因此有以下示意图：
- 而里层List中的元素类型是Integer，则有如下示意图：
由此可以看出，List<List<Integer>> 所代表的正是一个二维数组。用 i 表示横坐标（行），j 表示纵坐标（列），我们可以通过ArrayList中的get()方法获取二维数组 [i][j] 位置处的元素值。我们将步骤分解，得到具体操作如下：
首先，我们需要创建出外层（即上图中左侧）的ArrayList，用ret表示：
List<List<Integer>> ret = new ArrayList<>();
ret中的每一个元素也是ArrayList类型。我们接下来要做的，就是依照规律逐行将杨辉三角中的数值放入“二维数组”中。第一行的1没有前一行或前一列，它是特殊的，需要单独先把1放进去：
1.//创建第一行 List<Integer> firstRow = new ArrayList<>(); //将第一行的元素1放入第一行的第一个 firstRow.add(1); //将第一行作为ret的首元素加入ret中 ret.add(firstRow);
然后再插入剩下的数值。用for循环控制每行要完成的事，i 代表行数，由于第一行已经提前单独插入过数值，因此 i 从第二行开始，也就是下标为1处开始。
每一行，都创建一个ArrayList顺序表，用curRow表示。每一行的第一个元素和最后一个元素一定是1，直接通过curRow.add(1)插入即可。两个1中间部分的元素通过插入上方元素之和计算。可以新创建一个变量prevRow表示curRow的前一行：
List<Integer> prevRow = ret.get(i-1); //获取元素并将结果插入curRow curRow.add(prevRow.get(j-1) + prevRow.get(j));
也可以不用prevRow，直接插入：
curRow.add(ret.get(i-1).get(j-1) + ret.get(i-1).get(j));
for循环的最后，还需要把当前行插入ret中。
ret.add(curRow);
示意图及合并代码如下：
for (int i = 1; i < numRows; i++) { List<Integer> curRow = new ArrayList<>(); curRow.add(1); for (int j = 1; j < i; j++) { curRow.add(ret.get(i-1).get(j-1) + ret.get(i-1).get(j)); } curRow.add(1); ret.add(curRow); }
2. 完整代码
class Solution { public List<List<Integer>> generate(int numRows) { List<List<Integer>> ret = new ArrayList<>(); List<Integer> firstRow = new ArrayList<>(); firstRow.add(1); ret.add(firstRow); for (int i = 1; i < numRows; i++) { List<Integer> curRow = new ArrayList<>(); curRow.add(1); for (int j = 1; j < i; j++) { curRow.add(ret.get(i-1).get(j-1) + ret.get(i-1).get(j)); } curRow.add(1); ret.add(curRow); } return ret; } }
三、总结
- 杨辉三角的数值规律。
- Link<Link<Integer>>可以看作是一个二维数组，且该“二维数组”中的每个元素类型是Integer。分解来看即是一个ArrayList中的每个元素类型仍是一个ArrayList，且后者中的元素类型是Integer。
- 通过集合类的get方法获取元素。ret.get(i)指获取ret中第i个元素（ret中的元素类型仍是ArrayList，所以也就是获取第i行），ret.get(i).get(j)指获取行中第j个的元素。
- 关键的插入方法是，每一行都创建新的ArrayList对象curRow，先add顺序表curRow中的内容，最后再将该行作为ret的一个元素add到顺序表ret中。通过：
curRow.add(...);
ret.add(curRow);
即可搞定向该“二维数组”中插入元素。
