现在的位置: 首页 > 综合 > 正文

LeetCode OJ 之 Pascal’s Triangle II (杨辉三角II )

2019年07月18日 ⁄ 综合 ⁄ 共 608字 ⁄ 字号 评论关闭

题目:

Given an index k, return the kth row of the Pascal's triangle.

给定k,求杨辉三角第k行的数字

For example, given k = 3,

Return [1,3,3,1].

杨辉三角

[
0     [1],
1    [1,1],
2   [1,2,1],
3  [1,3,3,1],
4 [1,4,6,4,1]
]

Note:

Could you optimize your algorithm to use only O(k) extra space?

你可以只使用O(k)的存储空间使你的算法最优吗?即空间复杂度为 O(k)

代码:

class Solution {
public:
    vector<int> getRow(int rowIndex) 
    {
        //滚动数组
        vector<int> array;
        for (int i = 0; i <= rowIndex; i++) 
        {
            // 0        [1],
            // 1       [1,1],
            // 2      [1,2,1],
            // 3     [1,3,3,1],
            // 4    [1,4,6,4,1]
            //每次循环,确定第i行的数据,下次循环的结果由上次循环得到的数据确定
            //比如第5行,先确定第4个元素4是由第四行的第4个元素1与第3个元素3想加得到
            //第3个元素6是由第四行的第3个元素3和第2个元素3求和得到
            for (int j = i - 1; j > 0; j--)
            {
                array[j] = array[j - 1] + array[j];
            }
            array.push_back(1);
        }
        return array;
        
    }
};

抱歉!评论已关闭.