leetcode筆記：Pascal's Triangle II

一. 題目描述

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?

二. 題目分析

關於帕斯卡三角形的定義，可參考：http://baike.baidu.com/link?url=qk_-urYQnO4v6v3P4BuMtCa0tMNUqJUk4lmbkb1aqbqikBU-ndiMlTF20fq2QUjTTFTeTohZ72KFxgBnz4sJha

該題要求只輸出第k行的元素值，並且要求空間復雜度為O(k)，因此，采用的方法是只使用一個定長的數組，用於存放每一行的元素值，對於每個新的行，可對原先存放的行從後往前掃描，主要分為以下三種情況：

這樣，就只需要O(k)的空間。

三. 示例代碼

class Solution {
public:
    vector getRow(int rowIndex) 
    {
        vector result(rowIndex + 1);
        result[0] = 1;
        if (rowIndex < 1) return result;

        for(int i = 1; i <= rowIndex; ++i)
            for(int j = i; j >= 0; --j)
                if (j == i || j == 0)
                    result[j] = 1;
                else
                    result[j] = result[j-1] + result[j];

        return result;                    
    }
};

四. 小結

若不要求O(k)的空間復雜度，該題的難度更低，但這樣也沒什麼技巧可言了。