由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - Pascal's Triangle II 的优化解?
相关主题
Palindrome Partitioning II 的DP做法?C++ 程序求助
leetcode wordsearch的时间复杂度?问个题
leetcode的run time error设计钞票系统的面值
这小段code有什么问题吗?Given a string, find all its permutations without any repetition?
two questionsleetcode triganle 通不过。。。
[InterviewStreet] Grid Walking (Score 50 points)leetcode 的 triangle 一题 oj 怎么不过
java的基本问题为什么oj.leetcode上面的triangle那道题总是超时
说实话Pascal's Triangle这题目要是没做过 电面写Leetcode上subsets-ii的疑问
相关话题的讨论汇总
话题: res话题: int话题: vector话题: rowindex话题: pascal
进入JobHunting版参与讨论
1 (共1页)
a***e
发帖数: 413
1
问道简单题,
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?
对下面这种优化解总觉得不是很清楚。感觉如果不是自己想出来的东西下次又会忘,有
没有同学解释下原理?为啥内循环要从右忘左扫?多谢!
vector getRow(int rowIndex) {
vector res;
if (rowIndex<0) return res;

res.resize(rowIndex+1);
res[0]=1;

for (int i=1; i {
for (int j=i; j>=1; j--)
res[j]=res[j-1]+res[j];
}

return res;
}
r*******e
发帖数: 971
2
你自己跑一下不就知道了??别人解释也没用啊。
自己拿那个1331 手动跑一下,每一步都画在纸上。
a***e
发帖数: 413
3
早跑过了。
但这个最初是怎么想出来的?Pascal's Triangle 像下面这样写,很简单,但怎么能够
想到从右到左扫来优化?
class Solution {
public:
vector > generate(int numRows) {
vector> res;
if (numRows==0) return res;

vector curRow;
curRow.push_back(1);
res.push_back(curRow);

for (int i=1; i {
vector prevRow=curRow;
curRow.clear();

for (int j=0; j {
if (j==0)
{
curRow.push_back(1);
}
else
{
curRow.push_back(prevRow[j-1]+prevRow[j]);
}
}
curRow.push_back(1);
res.push_back(curRow);
}

return res;
}
};
p**t
发帖数: 157
4
因为从左往右你没地方保存上一行的数据。。。
从右往左的话 用过的上一行的数就没用了 thats it

【在 a***e 的大作中提到】
: 早跑过了。
: 但这个最初是怎么想出来的?Pascal's Triangle 像下面这样写,很简单,但怎么能够
: 想到从右到左扫来优化?
: class Solution {
: public:
: vector > generate(int numRows) {
: vector> res;
: if (numRows==0) return res;
:
: vector curRow;

w*****t
发帖数: 485
5
dp状态压缩常用的方法
不容易想清楚
1 (共1页)
进入JobHunting版参与讨论
相关主题
Leetcode上subsets-ii的疑问two questions
问一道题k Sum[InterviewStreet] Grid Walking (Score 50 points)
请教一道L的题java的基本问题
一个面经说实话Pascal's Triangle这题目要是没做过 电面写
Palindrome Partitioning II 的DP做法?C++ 程序求助
leetcode wordsearch的时间复杂度?问个题
leetcode的run time error设计钞票系统的面值
这小段code有什么问题吗?Given a string, find all its permutations without any repetition?
相关话题的讨论汇总
话题: res话题: int话题: vector话题: rowindex话题: pascal