【LeetCode篇-Java实现】118. Pascal's Triangle
题目描述
Given a non-negative integer numRows, generate the first numRows of Pascal’s triangle.
杨辉三角形:第i行第j个元素值=第i-1行第j-1个元素值+第j个元素值
In Pascal’s triangle, each number is the sum of the two numbers directly above it.
Example:
Input: 5
Output:
[
1,
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
给定总行数,最后需要输出所有行的元素(使用list的嵌套结构进行输出)
解题思路
思路很简单,先分别求出每一行的元素,再把所有行的元素输出。
- 创建一个list用来存放所有的行;
- 再创建numRows个list用来存放每一行的元素
(在循环中创建,每次循环建立一个list存放某一行元素,再把这个list放入到总的list中); - 确定每一行元素:
首先每一行第一个和最后一个都是1,
剩下的即符合:第i行第j个元素值=第i-1行第j-1个元素值+第j个元素值
实现代码
根据上述思路可得Java代码:.
public List<List<Integer>> generate1(int numRows) {
//allrows存放所有行的元素,嵌套list的list---可以理解为外部list
List<List<Integer>> allrows = new ArrayList<List<Integer>>();
//循环从第一行开始,到第numRows行
for(int i = 1; i <= numRows; i++) { //每一行都是一层循环,算出每一行的所有元素
//row存放每一行的元素
List<Integer> row = new ArrayList<Integer>();
for(int j = 1; j <= i; j++) { //每一行元素个数=第几行数,所以用j==i代表每行最后一个元素
if(j == 1 || j == i) { //每一行第一个和最后一个元素都是1
row.add(1);
} else {
//第i行第j个元素值=第i-1行第j-1个元素值+第j个元素值
//get(i-2) (j-2)是因为list的下标从0开始,而i,j为了易于理解都是从1开始的,所以需要减去2
row.add(allrows.get(i - 2).get(j - 2) + allrows.get(i - 2).get(j - 1));
}
}
allrows.add(row); //每求出一行,就把结果加入到allrows里
}
return allrows;
}
参考
参考https://leetcode.com/problems/pascals-triangle/discuss/38141/My-concise-solution-in-Java这个解法下面的一个评论(个人感觉这个解法逻辑最容易理解)