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 | |