GuilinDev
Lc0118
05 August 2008
118 - Pascal’s Triangle
原题概述
Given a non-negative integer numRows, generate the first numRows of Pascal’s triangle.
In Pascal’s triangle, each number is the sum of the two numbers directly above it.
Example:
1
2
3
4
5
6
7
8
9
Input: 5
Output:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
题意
这道题输入是一个层数，要求输出帕斯卡三角的所有层，由一个二维数组来表示。思路很直接，每一层都用一个array来保存前一层的指针，当前行的数据由前一层来得到，每一层的每个元素由前一层的两个邻接元素相加；每一层的第一个和最后一个元素都是1。
Time： O(1+2+3+…+n)=O(n^2)；Space：一个二维数组来存最后的三角形，存前一层的指针和当前层只是一维数组，因此是O(n^2)。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (numRows <= 0) {
return result;
}
ArrayList<Integer> previousRow = new ArrayList<>();
previousRow.add(1);//第一行只有一个数，先加上
result.add(previousRow);
for (int i = 1; i <= numRows - 1; i++) {//从第二行开始有“前一行”
ArrayList<Integer> currentRow = new ArrayList<>();//新建一个array存当前行，当前行比前一行多两个元素
currentRow.add(1);//当前行的第一个元素为1，每一轮更新的时候上一轮的1会成为最右边的那个1
for (int j = 0; j < previousRow.size() - 1; j++) {//从上一行的第一个元素到最后一个元素都会参与计算
currentRow.add(previousRow.get(j) + previousRow.get(j+1));//前一行相邻两个元素相加，比如当前行的第2个元素就是上一行第0个和第1个相加，下一道题可以优化这里
}
currentRow.add(1);//当前行最后一个元素是1
result.add(currentRow);
previousRow = currentRow;
}
return result;
}
}
另外一种写法是在每一行生成时，在该行index 0的位置加入1，然后根据在2行以后根据上一行的元素推断出当前行的元素的值，更加清晰明了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
List<List<Integer>> generate(int numRows) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (numRows <= 0) {
return result;
}
ArrayList<Integer> currentRow = new ArrayList<>();
for (int i = 0; i < numRows; i++) {
currentRow.add(0, 1);
for (int j = 1; j < currentRow.size() - 1; j++) {//“掐头去尾”，头尾两个数都是1，中间的数才需要计算
currentRow.set(j, currentRow.get(j) + currentRow.get(j+1)); //在当前行从j位置开始更新
}
ArrayList<Integer> copyRow = new ArrayList<Integer>(currentRow);//这里直接add currentRow的话，当currentRow下一轮变化时会影响result里面的值
result.add(copyRow);
}
return result;
}
}
尾递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public List<List<Integer>> generate(int numRows) {
return generateHelper(new ArrayList<List<Integer>>(), numRows);
}
private List<List<Integer>> generateHelper(List<List<Integer>> triangle, int numRows) {
if (numRows == 0) { // 基线条件，需要创建的三角形行数
return triangle;
}
List<Integer> newList = new ArrayList<>(); // 新的一行
newList.add(1); // 每一行的第一个位置是1
if (triangle.size() != 0) { // 第一行加入的时候不用计算中间的值
List<Integer> lastList = triangle.get(triangle.size() - 1);
for (int i = 0; i < lastList.size() - 1; i++) {//没有包括最后一列
int current = lastList.get(i);
int next = lastList.get(i + 1);
newList.add(current + next); // 计算三角形的值
}
newList.add(1); //最后一列
}
triangle.add(newList); // 加入当前一行
return generateHelper(triangle, numRows - 1);
}
}