LeetCode Pascal's Triangle II

BabbleDay posted @ 2015年7月17日 01:50 in 刷题防身 with tags LeetCode Pascal's Triangle II Python , 371 阅读

注意这里的输入是行的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

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter