Leetcode: Pascal's Triangle II

墨蓝 2022-08-07 03:57 9阅读 0赞

题目：  
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;
        }
    };