leetcode 119. 杨辉三角 II
题目
给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。
img
==在杨辉三角中，每个数是它左上方和右上方的数的和。==
示例:
输入: 3
输出: [1,3,3,1]
进阶：
你可以优化你的算法到 O(k) 空间复杂度吗？
解题
class Solution(object):
def getRow(self, rowIndex):
"""
:type rowIndex: int
:rtype: List[int]
"""
# 1 2 行特殊
if row_index == 0: # 第一行
return [1]
if row_index == 1: # 第二行
return [1, 1]
# 第三行开始
tmp = []
pre_row = [1, 1] # 前一行
for i in range(2, row_index+1): # 第 2 行 ~ 第 k 行
# per row
tmp.append(1) # 每行第一个数是 1
for pre_idx in range(i - 1): # 求中间的数的循环次数: 0 ~ i-2 (除掉第一个和最后一个)
tmp.append( pre_row[pre_idx] + pre_row[pre_idx+1] ) # 中间的每个数是它左上方和右上方的数的和
tmp.append(1) # 每行最后一个数是 1
pre_row = tmp
tmp = []
return pre_row
