LeetCode解題之Pascal’s Triangle II

原題

用O(k)的空間得到楊輝三角第k行的數值。

注意點：

例子:

輸入: k = 3

輸出: [1,3,3,1]

[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

解題思路

現在要考慮的是在 Pascal’s Triangle 的基礎上節約空間，我們可以知道第k行需要(k+1)的空間，且下一行占用的長度都比上一行長，所以在計算下一行的值時適合從後往前計算。

AC源碼

class Solution(object):
    def getRow(self, rowIndex):
        """
        :type rowIndex: int
        :rtype: List[int]
        """
        result = [1] * (rowIndex + 1)
        for i in range(2, rowIndex + 1):
            for j in range(1, i):
                result[i - j] += result[i - j - 1]
        return result


if __name__ == "__main__":
    assert Solution().getRow(3) == [1, 3, 3, 1]