程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> LeetCode Pascal's Triangle II

LeetCode Pascal's Triangle II

編輯:關於C++

LeetCode解題之Pascal’s Triangle II


原題

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

注意點:

從0開始計算行數,即第0行為[1]

例子:

輸入: 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]
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved