编码蝙蝠 sum67 适用于除"other tests"以外的所有内容

Question

这是我正在研究的问题:

返回数组中所有数字的总和，除了忽略以6开始并延伸到下一个7的数字部分(每个6后面至少有一个7)。没有数字返回0。

• sum67([1, 2, 2])→5
• sum67([1, 2, 2, 6, 99, 99, 7])→5
• sum67([1, 1, 6, 7, 2])→4

这是我的解决方案:

def sum67(nums):
if len(nums) == 0:
return 0

elif 6 not in nums:
return sum(nums)

else:
for num in nums:
if num ==6:
ind_six = nums.index(6)
ind_seven = nums.index(7,ind_six)
del nums[ind_six:ind_seven+1]
else:
pass

return sum(nums)

我的代码适用于所有列出的输入，但没有通过"其他测试"。请参考图片。有谁能告诉我为什么吗?我错过了什么?谢谢你! !预期与运行图

我已经试过集思广益其他可能失败的输入。

Answer 1

这是过度依赖Python的便利性而导致效率低下的一个很好的例子。您对in、.index()、slices和sum()的使用都可以遍历整个列表，因此它们是O(n)。总体复杂度为O(nn)。看看Python列表的时间复杂度。

一个更简单的方法是遍历列表，当你看到6到下一个7时停止求和:

def sum67(nums):
count = True
total = 0
for n in nums:
if n == 6:
count = False
if count:
total += n
if n == 7:
count = True
return total

一次通过，O(n).

有了上面的参考解决方案，我运行了一个模糊测试，看看是否有任何边缘情况你的解决方案遗漏:

import random
for _ in range(10000):
L = [random.randint(0, 20) for _ in range(random.randint(0, 20))]
if all(x != 6 or (7 in L[i:]) for i, x in enumerate(L)):
if sum67_ref(L[:]) != sum67(L[:]):
print(L)

失败的输入是L = [6, 7, 6, 1, 7, 7]。正确答案是7，但你的密码给出的是21。问题是，当您在迭代列表时从列表中删除元素时，迭代器会感到困惑并跳过元素。在本例中，删除[6, 7]子列表，然后迭代器跳过索引2处的下一个6，并发出1，这是计数的，以及它后面的7，这两个都应该被忽略。

如果没有参考解决方案，很难想象一个失败的测试用例(这是一个很好的实践!)，但是您可以遵循一个测试原则，即"大多数不正确的函数都可能在一个小的测试用例上失败"。这里确实如此——我们只需要一个长度为4的列表来触发失败:[6, 7, 6, 7]。您可以在一个小列表中生成6和7的排列，并根据代码的输出手工检查它们以验证它。