首页 > 代码库 > LeetCode: Pascal's Triangle II 解题报告
LeetCode: Pascal's Triangle II 解题报告
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也能搞定：
1 public class Solution { 2 public List<Integer> getRow(int rowIndex) { 3 List<Integer> ret = new ArrayList<Integer>(); 4 5 for (int i = 0; i <= rowIndex; i++) { 6 for (int j = i; j >= 0; j--) { 7 if (j == i) { 8 ret.add(1); 9 } else if (j != 0) {10 // ERROR: use add instead of set11 //ret.add(ret.get(j) + ret.get(j - 1));12 ret.set(j, ret.get(j) + ret.get(j - 1));13 }14 } 15 }16 17 return ret;18 }19 }
GitHub代码链接
LeetCode: Pascal's Triangle II 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。