GuilinDev
Lc0119
05 August 2008
119 - Pascal’s Triangle II
原题概述
Given a non-negative index k where k ≤ 33, return the _k_th index row of the Pascal’s triangle.
Note that the row index starts from 0.
In Pascal’s triangle, each number is the sum of the two numbers directly above it.
Example:
1
2
Input: 3
Output: [1,3,3,1]
Follow up:
Could you optimize your algorithm to use only O(k) extra space?
题意和分析
跟上一道题相比，这道题只需要知道某一行的结果。上一道题我们需要知道当前行第i个元素的值的时候，是前一行的result[i] + result[i+1]，这是从前往后扫，这里可以看到i和i+1数据是往前看的（得知i+1，需要先知道i，再加上1），而如果我们通过前一行result[i] + result[i-1]来得到当前行第i个元素的值，那就是数据从后往前扫，result[i] 只在当前步用到，下一步就用不到了，可以被覆盖，因此只需要一行的空间。
这个方法类似动态规划省空间，主要就是看我们需要的数据是之前的数据还是新的数据，从而来决定我们遍历的方向。这个考点适合于电面的时候。
时间复杂度还是O(n^2)，而空间这里是O(k)来存储结果，仍然不需要额外空间。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public List<Integer> getRow(int rowIndex) {
List<Integer> result = new ArrayList<>();
if (rowIndex < 0) {//rowIndex可以等于0
return result;
}
result.add(1);//先初始化为一行的值
for (int i = 1; i <= rowIndex; i++) {//注意rowIndex是从0开始数，到rowIndex结束；上一题的numRows是共多少行，从1开始数
//这里loop到rowIndex之前不用创建一个array来保存当前的行了
for (int j = result.size() - 2; j >= 0; j--) {//从前一行的倒数第二个开始计算，而前一行的倒数第一个数由倒数第二个数可以知道
result.set(j+1, result.get(j) + result.get(j+1));//将j+1位置上(通过j得知)的元素替换成前一行j+1相对应的两个值相加
}
result.add(1);//加上当前行的最后一个元素
}
return result;
}
}
同样也有另外一种写法，每一轮在index 0的位置添加一个1，然后在前一行的基础上得到当前行的值即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public List<Integer> getRow(int rowIndex) {
List<Integer> result = new ArrayList<>();
if (rowIndex < 0) {
return result;
}
for (int i = 0; i <= rowIndex; i++) {
result.add(0, 1);//每一轮在index 0的位置插入一个1
for (int j = 1; j < result.size() - 1; j++) {//
result.set(j, result.get(j) + result.get(j+1));//在j的位置从左往右更新，因为已经插入了1，所以是j和j+1，而不是j-1和j，左边更新的数可以得出右边的数，刚好
}
}
return result;
}
}