[LeetCode] Pascal\'s Triangle II_综合

[Problem]

Given an index k, return the k^th 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?

[Analysis]
对于第n行，一共有n个数：
第0项 f(0) = 1
第1项 f(1) = f(0) * (n-1)/1
第2项 f(2) = f(1) * (n-2)/2
第3项 f(3) = f(2) * (n-3)/3
......
第n-2项 f(n-2) = f(n-1) * 2/(n-2)
第n-1项 f(n-1) = f(n-2) * 1/(n-1)

需要注意的是，
（1）当n为奇数时，可以直接使用上面的方法；
（2）当n为偶数时，第n/2项与第n/2-1项相同，既f(n/2) = f(n/2 - 1)

[Solution]

class Solution {
      
public:
    vector<int> getRow(int rowIndex) {
      
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<int> res;

        // the first row
        int n = rowIndex + 1;
        if(n == 1){
      
                res.push_back(1);
        }
        else{
      
                // the first column
                res.push_back(1);

                // column 1:n-1
                long long sum = res.back();
                for(int j = 1; j < n-1; ++j){
      
                        if(n%2 == 0 && j == n/2){
      
                                ;
                        }
                        else{
      
                                sum = sum * (n-j)/j;
                        }
                        res.push_back(sum);
                }
        }

        return res;
    }
};