FXTi's blog
0%

pascal-s-triangle-ii

Posted on Edited on

Pascal’s Triangle II – LeetCode 119

Problem

Description

Given an index k, return the $k^{th}$ row of the Pascal’s triangle.

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

Example

For example, given k = 3,

Return [1,3,3,1].

Answer

Original

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> result;
        vector<int> tmp;
        for (int i = 0; i <= rowIndex; i++) {
            result.resize(i + 1);
            result[0] = result[i] = 1;
  
            for (int j = 1; j < i; j++)
                result[j] = tmp[j - 1] + tmp[j];
            
            tmp = result;
        }
        
        return result;
    }
};

思路

同上一题，时间复杂度$O(n^2)$，空间复杂度$O(n)$。

Better

思路

还有就是组合公式法，但恕我直言，考虑到连续的阶乘极有可能导致溢出，所以并不提倡，就不写了。