leetcode解题: Pascal's Triangle II (119)

发表于 | 分类于

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?

解法1： 重复利用Array, O(k^2) Time + O（K） Space

题目要求节省空间，想到的办法就是不停的修改当前的array。这里要注意的是：

  1. 修改array的时候要从后往前修改，这样在计算前面的数值的时候不会受到已经修改过的数值的影响。
  2. 在修改array的时候是从1到当前的最后一个。因为当修改完毕之后array的大小才会增加。如果不注意这一点会出现[1,1,1]这样的结果。
    C++
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    class Solution {
    public:
        vector<int> getRow(int rowIndex) {
            vector<int> res;
            res.push_back(1);
            for (int i = 0; i < rowIndex; ++i) {
                for (int j = res.size(); j >= 1; --j) {
                    res[j] += res[j - 1];
                }
                res.push_back(1);
            }
            return res;
        }
    };

Java

1