LeetCode Pascal's Triangle II

注意这里的输入是行的Index，不是行数

通过记录上一行

 

class Solution:
    # @param {integer} rowIndex
    # @return {integer[]}
    def getRow(self, rowIndex):
        rtn, prev = [1], [1,1]
        for k in range(rowIndex+1):
            rtn = [1] * (k+1)
            if k>1:
                for j in range(1,k):
                    rtn[j] = prev[j-1] + prev[j]
                prev = rtn
        return rtn

在一行内解决

观察

1 3 3 1

S1: 尾部加一  1 3 3 1 1

S2: 从倒数第二个到正数第二个，每个数变成当前数与其左边的数之和

1 3 3 4 1

1 3 6 4 1

1 4 6 4 1

 

刷题防身 LeetCode Pascal's Triangle II Python Comments(0) 2015年7月17日 01:50