题目: 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),则可以使用一个临时的vector保存上次计算的结果,然后迭代这计算最终结果。 最后注意index k是从0开始的。
C++参考代码:
class Solution
{
public:
vector<int> getRow(int rowIndex)
{
vector<int> result;
if (rowIndex < 0)
{
return result;
}
result.push_back(1);
if (rowIndex == 0)
{
return result;
}
result.push_back(1);
if (rowIndex == 1)
{
return result;
}
vector<int> previous;
vector<int>::size_type size;
for (int i = 2; i <= rowIndex; i++)
{
previous = result;
size = previous.size();
result[0] = 1;
for (vector<int>::size_type j = 1; j < size; j++)
{
result[j] = previous[j - 1] + previous[j];
}
/*
这里我原来写的语句是result[size] = 1;可是结果一直不对,后来调试发现vector下标越界。
我想可能英文是上一次循环结果result的下表最大为size-1,我这里使用下标size,vector不会动态申请空间。
所以最后结论是使用push_back()方法,vector就可以动态申请空间了。
*/
result.push_back(1);
}
return result;
}
};