LeetCode 119. Pascal's Triangle II [Easy] [C++] 解題筆記

 Given an integer rowIndex, return the rowIndexth row of the Pascal's triangle.

Notice that the row index starts from 0.

In Pascal's triangle, each number is the sum of the two numbers directly above it.

Follow up:

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

 

Example 1:

Input: rowIndex = 3
Output: [1,3,3,1]

Example 2:

Input: rowIndex = 0
Output: [1]

Example 3:

Input: rowIndex = 1
Output: [1,1]

想法:

    這題要我們求帕斯卡三角形的最後一個 row，這題可以像 118. Pascal's Triangle 求出整個三角形後再回傳

最後一個 row 就好了，但是題目希望可以在 O(k)的空間複雜度內完成，因此觀察可以得知要求當前 row 的每個 col，

只需要知道上一個 row 的值就夠了，因此我們可以宣告一個大小為最後一個 row 行數的 vector 來存放當前結果，

因此 res[j] = res[j] + res[j - 1]; res[0] = 1，從最後一個 col 往回填，因為由前往後填會把下一個 col 需要知道的

information 給蓋掉！(res[j] = res[j] + res[j - 1])。
                 //當前 row  上一個 row 的 col[j] + 上一個 row 的 col[j - 1]

完整程式碼:

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        // row index starts from 0
        vector<int> res(rowIndex + 1);
        res[0] = 1;
        for (int i = 1; i <= rowIndex; i++) {
            for (int j = i; j >= 1; j--) {
                res[j] += res[j - 1];
            }
        }
        return res;
    }
};