Python实现帕斯卡三角追加新行时旧列表元素末尾出现多余0

问题描述 #

• 实现目标：在LeetCode求解帕斯卡三角题目，要求输入指定行数，返回对应结构的帕斯卡三角二维列表
• 初始实现逻辑：封装getNextRow(row)工具函数，传入当前行数据计算推导下一行内容，循环调用该函数逐行生成结果，依次追加到最终结果列表
• 异常表现：每次向结果列表追加新生成的行时，已经存入列表的历史行末尾会凭空多出一个多余的0

复现信息 #

• 测试输入：5（需生成5行帕斯卡三角）
• 实际错误输出：[[1,0],[1,1,0],[1,2,1,0],[1,3,3,1,0],[1,4,6,4,1]]
• 正确预期输出：[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
• 可复现代码：

def getNextRow(row):
    res = [1]
    if len(row) == 0:
        return res
    row.append(0)
    for i in range(len(row) - 1):
        res.append(row[i] + row[i+1])
    return res


def generate(numRows):
    pascal = [] # 存储最终生成的帕斯卡三角
    currentRow = []
    num = 0 # 行数计数器
    while num < numRows:
        currentRow = getNextRow(currentRow)
        pascal.append(currentRow)
        num += 1
    return pascal
                
if __name__ == '__main__':
    print(generate(5))

根因分析 #

Python中列表是可变对象，函数传参时传递的是列表的引用而非副本。getNextRow函数中直接对传入的row参数执行row.append(0)是原地修改原列表对象，而之前生成的行已经被存入pascal结果列表，这些已存储的行和传入函数的currentRow是同一个对象，因此追加0的操作会同步修改已经存在结果里的历史行，导致每行末尾多一个多余的0。

修复方案 #

不要在函数内原地修改传入的原行列表，两种可选改法：

1. 调整计算逻辑，完全不修改传入的原列表。帕斯卡三角下一行的首尾固定为1，中间元素是上一行相邻两元素之和，不需要给上一行补0做计算，修改后的getNextRow如下：

def getNextRow(row):
    res = [1]
    if len(row) == 0:
        return res
    for i in range(len(row) - 1):
        res.append(row[i] + row[i+1])
    res.append(1)
    return res

2. 如果要保留补0计算的逻辑，先对传入的行做浅拷贝，在副本上做修改，不影响原对象：

def getNextRow(row):
    res = [1]
    if len(row) == 0:
        return res
    # 拷贝一份临时列表做计算，不修改原传入的row
    temp_row = row.copy()
    temp_row.append(0)
    for i in range(len(temp_row) - 1):
        res.append(temp_row[i] + temp_row[i+1])
    return res

两种改法运行后都能得到符合预期的输出。

内容的提问来源于stack exchange，提问作者Max S