[LeetCode] 119. Pascal's Triangle II

轉自LeetCode

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?

<Solution>

這題是 Pascal's Triangle 的衍生題

差別在於，這次只要回傳指定的 row of Pascal's triangle

並且，題目有要求只能使用 O(k) 的 extra space

想法如下

• 多用一個 prv vector 來儲存上次的數值

• 每次要求出目前的數值的時候，先把值存到 prv，再從 prv 算出新的值

code 如下

再仔細看一下，會發現需要 extra space 是因為是用由前往後的方式來計算數值

所以前面的數值會被先更新，因此需要先記錄下來

這時候如果改成由後往前計算，這樣就不會發生需要參考的數值被改掉的情況

因此也可以省掉多使用 O(k) 的 extra space

code 如下