1 回答

TA贡献1872条经验 获得超3个赞
浏览列表会更快,将每个值与前一个值进行比较,以确保它严格增加。对于列表中的一个数字,允许此错误,并跳过此数字。不幸的是,这并不是那么简单,正如我们在下面看到的那样:
不起作用(例如。[1,4,2,3])
def almostIncreasingSequence(sequence):
lastValue = sequence[0]
removed_value = False
for i in range(1,len(sequence)):
if sequence[i] <= lastValue:
if removed_value:
return False
else:
removed_value = True
else:
lastValue = sequence[i]
return True
相反,如果我们遇到非增加,我们需要涵盖两种可能性:删除当前数字(例如。[1,2,1,3])或删除前一个(例如。[1,2,8,4])。我们还有一些边缘情况用于删除列表中的第一个或最后一个数字。
最终(不那么漂亮)的解决方案
def almostIncreasingSequence(sequence):
lastValue = sequence[0]
skipped_value = False
for i in range(1,len(sequence)):
if sequence[i] <= lastValue:
if i+1 == len(sequence):
return not skipped_value # last number is not decreasing, skip if we can
if skipped_value:
# if we've already skipped a number - won't work
return False
elif sequence[i+1] > sequence[i-1]:
# skipping the current number will fix it
skipped_value = True
lastValue = sequence[i-1]
else:
# try and skip the previous number
skipped_value = True
if i == 1 or sequence[i] > sequence[i-2]:
# can skip the previous number and it'll work
lastValue = sequence[i]
else:
# we have no chance
return False
else:
lastValue = sequence[i]
return True
添加回答
举报