什么是杨辉三角
在杨辉三角中，每个数是它左上方和右上方的数的和。如下图所示。
杨辉三角
题目
题目1：给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。——LeetCode118
输入: 5
输出:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
题目2：给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。——LeetCode119
输入: 3
输出: [1,3,3,1]
抽象化模型
如果把杨辉三角前五行存入一个二维数组中，设row为当前行数(从0起始)，rowS为row行的第一个元素下标，rowE为row行的最后一个元素下标。则row，rowS和rowE之间的关系如下图所示：
二维数组存储杨辉三角前五行
观察上图可知：
- 当前行数为row，则数组最后一个元素的下标rowE等于row。
- 当前行数row，下标为rowS的第一个元素和下标为rowE的最后一个元素固定为1。
- 当前行数row的中间元素，下标i的元素等于row-1行的下标i和下标i-1元素的和。
题目1代码
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> res = new LinkedList<>();
//健壮性校验
if(numRows <= 0){
return res;
}
//从第1行开始，下标从0开始
int row = 0;
//生成numRows行的杨辉三角
while(row < numRows){
//第row行的数据存储在list中
List<Integer> list = new LinkedList<>();
//如果当前row大于1(也就是从第三行起)，需要获取前一行的数据进行计算
List<Integer> preList = row > 1 ? res.get(row - 1) : null;
//为符合示例图，便于理解，这里定义rowS和rowE。其实就是0和row。
final int rowS = 0;
int rowE = row;
//生成第row行的数据
for(int i = rowS; i <= rowE; ++i){
//如果是首尾两个元素，固定为1
if(i == rowS || i == rowE){
list.add(1);
} else {
//否则，是前一行的第i个元素与第i-1个元素之和
list.add(preList.get(i) + preList.get(i - 1));
}
}
//存储第row行的结果
res.add(list);
row++;
}
return res;
}
题目2代码
题目1的杨辉三角打印出来找到对应的行，即可解决问题。不过，这里结果只要指定的行，我们没有必要保存所有的行，可以使用一维数组记录每次算出来的第row行结果，一直算到要求的第k行停止。
public List<Integer> getRow(int rowIndex) {
//结果放入list返回
List<Integer> res = new LinkedList<>();
//健壮性校验
if(rowIndex < 0){
return res;
}
//rowIndex从0开始，rowIndex行一共rowIndex+1个元素。
//初始化长度为rowIndex+1的数组
int[] temp = new int[rowIndex + 1];
//row从0开始
int row = 0;
//计算每一行的元素，直到第rowIndex行
while(row <= rowIndex){
//为便于理解，与示例图一致，定义rowS和rowE。其实就是0和row。
final int rowS = 0;
int rowE = row;
//从row行的最后一个元素下标rowE开始，往前遍历计算
//从后向前，因为非首尾下标i的元素等于上一行的i和i-1元素之和
//也就是上一行的i-1的元素即在计算本行的i时用到，也在计算本行的i-1时用到
//如果从前往后，那么计算本行的i-1时就会把上一行的i-1元素覆盖掉，无法计算i位置的元素
for(int i = rowE; i >= rowS; --i){
//首尾元素固定为1
if(i == rowS || i == rowE){
temp[i] = 1;
} else {//中间元素i为上一行的i-1和i元素之和
temp[i] = temp[i-1] + temp[i];
}
}
row++;
}
//数组转换为list返回
for(int i = 0; i <= rowIndex; ++i){
res.add(temp[i]);
}
return res;
}
