美文网首页
每天(?)一道Leetcode(12) Pascal's Tri

每天(?)一道Leetcode(12) Pascal's Tri

作者: 失业生1981 | 来源:发表于2019-01-26 22:21 被阅读0次

    Array

    119. Pascal's Triangle II

    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.

    即输出杨辉三角中的第k行
    杨辉三角的每一行组合数其实可以通过计算C_n^m,m=1,\ldots,n得到
    比如第三行是1,3,3,1 对应 C_3^0,C_3^1,C_3^2,C_3^3
    所以只要知道计算方法就ok,C_n^m=\frac{n!}{m!(n-m)!}
    [yeah~~~这是我自己做的第二个beats 100\%]

    class Solution:
        def getRow(self, rowIndex):
            """
            :type rowIndex: int
            :rtype: List[int]
            """
            res = []
            k = rowIndex
            nums = jc(k)
            for i in range(k+1):
                res.append(int(nums/(jc(i)*jc(k-i))))
            return res
        
        
        
        
    def jc(n):
        if n==0:
            return 1
        else:
            s = 1
            for i in range(1,n+1):
                s = s*i
            return s
    

    相关文章

      网友评论

          本文标题:每天(?)一道Leetcode(12) Pascal's Tri

          本文链接:https://www.haomeiwen.com/subject/ekywjqtx.html