Python代码向字典添加新键时触发KeyError:1，求排查解决

问题描述 #

编写求解最大整除子集的Python代码时，向字典添加新键时触发KeyError:1错误。

原始代码 #

nums = sorted(nums)
n = len(nums)
maps = { 0 : [nums[0]]}
maps[2] = ["shot"]
dp = [1 for _ in nums]

for i in range(1 , n):
    for j in range(i , -1 , -1):
        if nums[i] % nums[j] == 0:
            dp[i] = dp[j]+1
            print(maps)
            if i not in maps.keys():
                maps[i] = maps[j].append(nums[i])

错误信息 #

KeyError: 1
maps[i] = maps[j].append(nums[i])
Line 15 in largestDivisibleSubset (Solution.py)
ret = Solution().largestDivisibleSubset(param_1)
Line 41 in _driver (Solution.py)
_driver()
Line 52 in <module> (Solution.py)

输入示例 #

nums = [1,2,3,5,7]

问题排查 #

1. KeyError根源：初始maps字典只初始化了键0和2，当循环中j=1时（比如i=1，j从1开始遍历），maps中不存在键1，直接访问maps[j]就会触发KeyError。
2. 列表操作错误：list.append()方法会直接修改原列表，并且返回None，这会导致maps[i]被赋值为None，后续使用时会引发其他问题。
3. DP逻辑缺陷：当前代码找到第一个满足整除条件的j就更新dp[i]，没有考虑到可能存在多个j，需要选择dp[j]最大的那个来保证子集长度最长。

修复方案 #

1. 初始化完整的maps字典：为每个索引i初始化对应的初始子集[nums[i]]，确保所有索引都存在于maps中。
2. 正确生成新子集：使用列表拼接maps[j] + [nums[i]]来创建新的子集，避免修改原列表，同时保证maps[i]存储的是有效列表。
3. 优化DP更新逻辑：遍历所有可能的j，找到能使dp[i]最大的那个j，再更新dp[i]和maps[i]。

修复后的完整代码 #

def largestDivisibleSubset(nums):
    if not nums:
        return []
    nums = sorted(nums)
    n = len(nums)
    # 初始化每个索引对应的初始子集
    maps = {i: [nums[i]] for i in range(n)}
    dp = [1] * n
    max_len = 1
    max_index = 0

    for i in range(1, n):
        for j in range(i):
            if nums[i] % nums[j] == 0 and dp[j] + 1 > dp[i]:
                dp[i] = dp[j] + 1
                # 拼接新子集，不修改原列表
                maps[i] = maps[j] + [nums[i]]
                # 更新最长子集的信息
                if dp[i] > max_len:
                    max_len = dp[i]
                    max_index = i
    return maps[max_index]

# 测试输入
nums = [1,2,3,5,7]
print(largestDivisibleSubset(nums))

代码说明 #

• 先对nums排序，保证整除关系的单调性。
• maps字典存储每个索引对应的最大整除子集，初始时每个子集只有自身元素。
• 遍历每个元素i，再遍历其之前的所有元素j，若nums[i]能被nums[j]整除，且dp[j]+1大于当前dp[i]，则更新dp[i]和maps[i]。
• 最后返回长度最长的那个子集。

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