Difficulty: Easy

Given a non-negative index k where k ≤ 33, return the k^th index row of the Pascal’s triangle.

Note that the row index starts from 0.

In Pascal’s triangle, each number is the sum of the two numbers directly above it.

Example:

1 2	Input: 3 Output: [1,3,3,1]

Follow up:

Could you optimize your algorithm to use only O(k) extra space?

解法

下面的方法是根据数字规律直接计算值，比较巧妙。

class :
    def getRow(self, rowIndex: int) -> List[int]:
        res = []
        for i in range(rowIndex+1):
            val = self.pascalVal(rowIndex, i)
            res.append(val)
        return res
        
    def pascalVal(self, row, col):
        if col == 0:
            return 1
        if row == 0:
            return col
        return (row * self.pascalVal(row-1, col-1)) // col

119. pascal’s triangle ii 解法

解法

近期文章

近期评论

标签

热门

文章归档

分类目录

功能