给定一个非负整数numRows
,生成杨辉三角的前numRows
行。
在杨辉三角中,每个数是它左上方和右上方的数的和。
输入:numRows = 5 输出:[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]
输入:numRows = 1 输出:[1]
1 <= numRosw <= 30
杨辉三角的性质:
题解:
杨辉三角的第0行只有一个数:1。对于 1 ≤ i < numRows
。用pervRow
表示杨辉三角的第 i - 1
行,用curRow
表示杨辉三角的第 i
行.
curRow
,表示当前行的首个数是1i - 1
个数分别等于其上方两数之和,因此对于 1 <= j < i
,有curRow[j] = pervRow[j] + pervRow[j - 1]
,依次将每个pervRow[j] + pervRow[j - 1]
添加到curRow
中。curRow
,表示当前行的末尾数是1.curRow
,将curRow
添加到杨辉三角。class Solution {
public List<List<Integer>> generate(int numRows) {
// 定义一个二维数组
List<List<Integer>> ret = new ArrayList<>();
List<Integer> list = new ArrayList<>();
list.add(1);
ret.add(list);
for (int i = 1; i < numRows; i++) {
// 每循环一次 就是一行
List<Integer> curRow = new ArrayList<>();
curRow.add(1); // 一行的第一个元素
// 处理中间元素
List<Integer> pervRow = ret.get(i - 1);
for (int j = 1; j < i; j++) {
int x = pervRow.get(j) + pervRow.get(j - 1);
curRow.add(x);
}
//最后一个元素
curRow.add(1);
ret.add(curRow);
}
return ret;
}
}
运行结果: