Pascal's Triangle II

题目描述

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?

解题方法

和triangle一样的思路，follow up就是只用上一层和这一层两个array，这样就只需要 O(k)的space

Solution

class Solution(object):
    def getRow(self, rowIndex):
        """
        :type rowIndex: int
        :rtype: List[int]
        """

        cur = [1]
        if rowIndex == 0:
            return cur

        for i in range(1, rowIndex+1):
            tmp = [0 for i in range(i+1)]
            for j in range(i+1):
                if j == 0:
                    tmp[0] = 1
                elif j == i:
                    tmp[j] = 1
                else:
                    tmp[j] = cur[j-1] + cur[j]
            cur = list(tmp)

        return tmp

Reference