[leetcode-python]杨辉三角2
给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
示例 1:
输入: rowIndex = 3 输出: [1,3,3,1]
示例 2:
输入: rowIndex = 0 输出: [1]
示例 3:
输入: rowIndex = 1 输出: [1,1]
提示:
0 <= rowIndex <= 33
进阶：
你可以优化你的算法到 O(rowIndex) 空间复杂度吗？
方案一：双层内循环，时间复杂度很高
class Solution:
def getRow(self, rowIndex: int) -> List[int]:
a = [1]
b = [1,1]
if rowIndex == 0:
return a
elif rowIndex == 1:
return b
else:
for i in range(2,rowIndex+1):
result = [1]
for j in range(i-1):
x = b[j] + b[j+1]
result.append(x)
result.append(1)
b = result
return result
方案二：
class Solution:
def getRow(self, rowIndex: int) -> List[int]:
#杨辉三角是对称的，我们只需要计算一半，另一半翻转对称过去即可
def expend(rowIndex,rowlist):
###rowIndex索引
####翻转换算
if rowIndex%2 == 0:
###偶数，中间数不需对称
num = len(rowlist) - 1
else:
###奇数，中间数需对称
num = len(rowlist)
temp = rowlist[0:num].copy()
j = -1
for i in range(num):
rowlist .append(temp[j])
j = j - 1
return rowlist
def calNextHalfList(rowIndex,rowlist):
###利用上一半list计算出下一组的一半
###rowIndex：上一组索引
###rowlist 上一组list
####翻转换算
result = [1]
if rowIndex%2 == 0:
###上组索引为偶数，本组输出为偶数,后面一个不需要自己加自己
for i in range(len(rowlist)-1):
x = rowlist[i] + rowlist[i+1]
result.append(x)
else:
###上组索引为奇数，本组输出为奇数,后面一个需要自己加自己
for i in range(len(rowlist)-1):
x = rowlist[i] + rowlist[i+1]
result.append(x)
x = rowlist[-1]*2
result.append(x)
return result
if rowIndex == 0:
return [1]
elif rowIndex == 1:
return [1,1]
else:
fistlist = [1]
for zzzzz in range(1,rowIndex):
fistlist = calNextHalfList(zzzzz,fistlist)
result = expend(rowIndex,fistlist)
return result