Pascal's Triangle II
Total Accepted: 19384 Total Submissions: 63446 My Submissions Question Solution
Given an index k, return the kth row of the Pascal's triangle.
For example, given k = 3,
Return [1,3,3,1].
Note:
Could you optimize your algorithm to use only O(k) extra space?
解:
题目里要求O(k),与上一题 杨辉三角 类似,但是我们稍微改一下,只需要存上一行的结果就行了。
这样就不需要消耗太多内存。
更厉害的是:Inplace也可以,只要你每次从后往前扫描就行了。一个array也能搞定:
public class Solution {
public List<Integer> getRow(int rowIndex) {
List<Integer> ret = new ArrayList<Integer>(); for (int i = 0; i <= rowIndex; i++) {
for (int j = i; j >= 0; j--) {
if (j == i) {
ret.add(1);
} else if (j != 0) {
// ERROR: use add instead of set
//ret.add(ret.get(j) + ret.get(j - 1));
ret.set(j, ret.get(j) + ret.get(j - 1));
}
}
} return ret;
}
}