[leetcode]_Pascal's Triangle II

时间:2023-03-08 17:07:15
[leetcode]_Pascal's Triangle II

题目: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;
}