0119. Pascal's Triangle II.md

题目

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]

我的思路

这题和118题一样，改动一下最后的输出即可。

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        res = []
        if rowIndex == 0:
            return [1]
        for i in range(rowIndex+1):
            res.append([])
            for j in range(i+1):
                if j == 0 or j == i:
                    res[i].append(1)
                else:
                    temp =  res[i-1][j-1] + res[i-1][j]
                    res[i].append(temp)            
        return res[rowIndex]

思考有没有更简单的方法，毕竟这道题不需要输出整个三角。运行时其实只需要保留当前层和上一层即可。

class Solution:
    def getRow(self, rowIndex: int): -> List[int]:
        curr, prev = [1], [1]
        for i in range(1, rowIndex+1):
            curr = [1]*(i+1)

            for j in range(1, i):
                curr[j] = prev[j-1] + prev[j]
            prev = curr
        return prev   

这道题用递归也可以做，尝试了提交了一下，发现运行时间超时了。