【LeetCode】Pascal’s Triangle II 解题报告

标签（空格分隔）： LeetCode

题目地址：https://leetcode.com/problems/pascals-triangle-ii/description/

题目描述：

Given an index k, return the kth row of the Pascal’s triangle.

For example, given k = 3,
Return [1,3,3,1].

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

Ways

杨辉三角。这个题之前用java做过，不过现在改用python重新刷。

杨辉三角的算法是上层的两个相邻的数字相加得到该层的数字。其实可以看做下面这种方式相加：

[1]

[1,1]=[0,1]+[1,0]

[1,2,1]=[0,1,1]+[1,1,0]

[1,3,3,1]=[0,1,2,1]+[1,2,1,0]

......

即上面一层的在首尾分别添加上0之后再对应相加。这样就可以先生成后面的两个首尾加0的列表，再用列表生成式对应位置相加计算出来每层的元素。

"""@author: fuxuemingzhu"""

class Solution(object):

    def getRow(self, rowIndex):

        """

        :type rowIndex: int

        :rtype: List[int]

        """

        answer = [1]

        for _ in xrange(rowIndex):

            answer = [x + y for x,y in zip([0] + answer, answer + [0])]

        return answer

Date

2017 年 8 月 28 日

巴特西

【LeetCode】Pascal's Triangle II 解题报告

【LeetCode】Pascal’s Triangle II 解题报告

题目描述：

Ways

Date

最新文章

热门文章