题目:Pascal三角的变形,要求只用O(K)的额外空间。
思路:由于Pascal三角中,tri[n][i] = tri[n - 1][i] + tri[n-1][i-1],(通常情况下)
如果已经获得K = 2时的数组:
1 | 2 | 1 |
1、 普通思路,从前部开始,想要生成下一行,在不能申请其它辅助空间时,
1 | 1 | 1 |
在生成了红色的3后发现,第二个3已经无法生成了。
2、那么,考虑从数组尾部开始考虑,
1 | 2 | 1 |
在生成了红色3后,还能够继续往下生成,2并没有被覆盖,能够顺利得到K = 3时的结果:
1 | 3 | 3 | 1 |
OK,此题的解题思路,即从上一行数组的尾部开始,生成下一行数组的每一个数据,这样既不会覆盖,也能够满足O(K)的空间限制。
代码:
public List<Integer> getRow(int rowIndex) { List<Integer> result = new ArrayList<Integer>();
for(int i = 0 ; i <= rowIndex ; i++){
result.add(1);
}
if(rowIndex == 0 || rowIndex == 1) return result; int help = 2;
while(help <= rowIndex){
for(int i = help - 1 ; i > 0 ; i--){
result.set(i , result.get(i) + result.get(i - 1));
}
help++;
}
return result;
}