0119._Pascal's_Triangle_II.md

119. Pascal's Triangle II

难度: Easy

刷题内容

原题连接

• https://leetcode.com/problems/pascals-triangle-ii/description/

内容描述

Given a non-negative index k where k ≤ 33, return the kth 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:

Input: 3
Output: [1,3,3,1]
Follow up:

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

解题方案

思路 1 - 时间复杂度: O(k^2)- 空间复杂度: O(k)******

太简单了，注意一点算数就好, beats 99.89%

class Solution(object):
    def getRow(self, rowIndex):
        """
        :type rowIndex: int
        :rtype: List[int]
        """
        if rowIndex == 0:
            return [1]
        res = [1]
        for i in range(1, rowIndex+1):
            tmp = [1]
            for j in range(1, i):
                tmp.append(res[j-1]+res[j])
            tmp.append(1)
            res = tmp
        return res