列表求杨辉三角

本文主要是介绍列表求杨辉三角，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

利用列表可变，有序，可追加的特性来求杨辉三角。

（1）：列表嵌套列表

n = 6
triangle = [[1], [1, 1]]
for i in range(2, n):pre = triangle[i-1]cur = [1] * (i+1)for j in range(i-1):cur[j+1] = pre[j] + pre[j+1]triangle.append(cur)
print(triangle) 

此种方法是在内存中开辟3个列表，triangle、pre前一行列表、cur现在的列表，当i=2时，cur[1] = pre[0] + pre[1]。缺点是会频繁生成pre、cur列表，产生大量垃圾。

（2）：在列表后面补0

new = [1]
n = 6
print(new)
for i in range(1, n):old = new.copy()old.append(0)new.clear()for j in range(i+1):new.append(old[j-1] + old[j]print(new)

相较于第一种方法，计算量增加了，频繁地生成新旧两行，会产生大量的垃圾。

（3）：利用对称性

n = 6
triangle = []
for i in range(n):cur = [1] * (i+1)triangle.append(cur)for j in range(1, i//2+1):pre = triangle[i-1]val = pre[j-1] + pre[j]cur[j] = valif i != 2 * j:cur[-j-1] = val
print(triangle)     

相较于前两种方法，计算量减半了，空间复杂度还是一样的。

（4）：利用单行列表和对称性

n = 6
cur = [1] * n
for i in range(n):offset = n - im = 1for j in range(1, i//2+1):val = m + cur[j]m = cur[j]cur[j] = valif i != 2 * j:cur[-j-offset] = valprint(cur[:i+1])

相较前面的方法，计算量减半了，空间复杂度也减少了。

这篇关于列表求杨辉三角的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---