119. 杨辉三角 II

https://leetcode-cn.com/problems/pascals-triangle-ii/

解法一:迭代

与118题思路一样

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        if rowIndex == 0:
            return[1]
        elif rowIndex == 1:
            return [1, 1]
        row = [1,1]
        for i in range(2, rowIndex+1):
            new_row = [1] * (i+1)
            for j in range(1, i):
                new_row[j] = row[j-1] + row[j]
            row = new_row
        return row

解法二:组合数

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        res = [0] * (rowIndex+1)
        num, j = 1, 1
        res[0] = 1
        if rowIndex == 0:
            return res
        #用组合数C(rowIndex,k),k从1到rowIndex的一半,剩下一半对称
        mid =  rowIndex // 2
        for i in range(1, mid+1):
            num *= (rowIndex + 1 - i)
            num //= j
            j += 1
            res[i] = num
 
        if rowIndex % 2 == 0:
            res[mid+1:] = res[mid-1::-1]
        else:
            res[mid+1:] = res[mid::-1]
        return res

最后更新于