可能导致错误的角点情况
最近我尝试了一些过去一年的AIO问题，但我解决不了这个问题。
问题如下：
安全破解输入文件: safein.txt输出文件: safeout.txt时间限制:几个世纪以来，许多战争都赢了，不是力量之战，而是智慧之战。你的消息来源最近告诉你，你的母亲购买了最新的电脑游戏WheeZork的预发行版本，并把它藏在家里的保险箱里。要打开保险箱，必须按正确的顺序将圆形刻度盘旋转到每个数字，从而输入一长串数字。
如果正确的数字顺序被输入保险箱，保险箱打开，你可以提前偷偷地把你的圣诞礼物拿出来。如果你的顺序弄错了，警报系统就会启动，你就会被终身禁足！幸运的是，你知道你妈妈把代码写在床头抽屉里的一张纸上，她喜欢称之为“电码表”。
她经常夸耀自己有多聪明，并向你解释，表格上的数字确实是保险箱的代码，但是序列中的每一个数字都被一个常数的非负整数k增加了，只有她知道。如果没有这个价值，纸是无用的，因此只有她才能打开保险箱.或者她是这么想的！
为了确定正确的代码，您已经监视了您的母亲打开保险箱时，您设法记住了她输入的部分代码。您不确定代码的哪一部分对应，但这肯定是代码中连续的数字序列。有了这些知识，你就着手确定保险柜的全部代码。
您的任务是，考虑到您的母亲在她的代码表上写下的全部数字列表，以及您所知道的在实际代码中显示的较短的序列，确定整个序列以解锁保险箱。
例如，如果保险柜的代码是7、9、4、6、8、12，而你母亲将所有数字增加4，那么她的代码单将读11、13、8、10、12、16。这是因为7+4= 11，给出第一个数字11。第二个数字是通过添加9+4= 13得到的。第三个数字是通过添加4+4= 8得到的，等等。你可能已经看到她按顺序进入了数字4，6，8。有了这些知识，您就可以确定整个代码。
输入输入文件的第一行将包含两个整数，a b，由空格分隔。整数a是写在母代码表上的序列的长度(2 <= a <= 100000)。整数b是包含在安全代码中的序列的长度(2 <= b <= 30)。
后面是一行，每一行包含1到1000000之间的单个整数。这些行是写在您母亲的代码表上的顺序，按照它们被输入保险箱的顺序。
后面是b行，每一行包含一个整数，也在1和1000000之间。这几行描述了对保险箱的实际代码的一瞥。
您可以保证，对于任何给定的输入场景，只有一个可能的解决方案。
输出您的输出文件应该由一行组成。这些行中的每一行都应该包含一个整数，表示打开保险箱所需的完整数字序列。
我的代码(通过大多数测试用例)如下：
'''program implements a function diff which is returns a list that is the difference of the current elements in the list
to solve the problem, the subset list is reduced until it consists of a single integer
the index of this integer in the original list is then found, before determining the non-negative integer
which was used to encode the numbers'''
def diff(lst):
lst2=[]
for i in range(len(lst)-1):
lst2.append(lst[i+1]-lst[i])
return lst2
infile = open("safein.txt", "r")
outfile = open("safeout.txt", "w")
a, b = map(int, infile.readline().split())
lst, sub = [], []
for i in range(a):
lst.append(int(infile.readline()))
for j in range(b):
sub.append(int(infile.readline()))
temp_sub=sub
temp_lst=lst
k = 0
while len(temp_sub) != 1:
temp_sub=diff(temp_sub)
k+=1
for x in range(k):
temp_lst=diff(temp_lst)
n = temp_lst.index(temp_sub[0])
m = lst[n]-sub[0]
lst=[x-m for x in lst]
for i in lst:
outfile.write(str(i) + "\n")由于这段代码通过了大多数测试用例，除了一些给出错误的情况(我不知道它是什么错误)，我想知道是否有人可以提出一些导致该算法产生错误的角用例。到目前为止，我想到的所有案件都已经过去了。
编辑:正如niemmi在下面所指出的，有一些我的算法无法处理的情况。因此，我重写了另一个算法来解决这个问题。该算法通过了大多数测试用例，除了执行时间超过1s外，没有错误。有人能帮助减少这个解决方案的时间复杂度吗？
def subset(lst1, lst2):
if lst2[0] in lst1:
idx = lst1.index(lst2[0])
for i in range(len(lst2)):
if lst2[i]==lst1[idx+i]:
continue
else:
return False
else:
return False
return True
infile = open("safein.txt", "r")
outfile = open("safeout.txt", "w")
a, b = map(int, infile.readline().split())
lst, sub = [], []
for x in range(a):
lst.append(int(infile.readline()))
for y in range(b):
sub.append(int(infile.readline()))
if subset(lst, sub):
for i in range(a):
outfile.write(str(int(lst[i])) + "\n")
infile.close()
outfile.close()
exit()
i=1
while True:
temp_sub = [x+i for x in sub]
if subset(lst, temp_sub):
lst = [x-i for x in lst]
for j in range(a):
outfile.write(str(int(lst[j])) + "\n")
infile.close()
outfile.close()
exit()
i+=1编辑:感谢niemmi，他提供了下面的解决方案，我稍微编辑了一下，以通过一个返回错误的测试用例。
def diff(seq):
return (seq[i - 1] - seq[i] for i in range(1, len(seq)))
with open('safein.txt') as in_file:
a, b = (int(x) for x in in_file.readline().split())
code = [int(in_file.readline()) for _ in range(a)]
plain = [int(in_file.readline()) for _ in range(b)]
code_diff = tuple(diff(code))
plain_diff = tuple(diff(plain))
k = 0
def index(plain_diff, code_diff, plain, code, a, b, k):
for i in range(k, a - b):
for j, x in enumerate(plain_diff, i):
if code_diff[j] != x:
break
else:
k = code[i] - plain[0]
break # found match, break outer loop
return k
k = index(plain_diff, code_diff, plain, code, a, b, k)
with open('safeout.txt', 'w') as out_file:
out_file.write('\n'.join(str(x - k) for x in code))谢谢!
回答 1
Stack Overflow用户
发布于 2017-08-25 12:18:45
上面的实现重复计算以下几行中连续元素的差异：
while len(temp_sub) != 1:
temp_sub=diff(temp_sub)
k+=1在第一轮之后针对示例输入运行时，temp_sub是[2, 2]，第二轮也是最后一轮之后是[0]。然后，该实现继续对temp_lst进行同样的简化，其中包含导致[-7, 7, 0, 2]的增量代码。
然后使用index从temp_lst中找到带有0值的索引，然后用于推断k。显然，如果在试图查找索引之前temp_lst上还有另一个0值，这种方法显然无法工作。在这种情况下，我们可以轻松地创建一个输入，例如，在代码表的开头添加两次11，这样完整的工作表将是[11, 11, 11, 13, 8, 10, 12, 16]。
编辑为什么不使用后续数字差异的初始方法来找到k呢？下面的代码在代码表上循环，并对每个位置检查是否可以从那里开始，也就是说，如果数字等于或大于普通序列中的第一个数字，因为k被定义为非负整数。然后，它在代码单和普通序列上循环下一个b - 1数字，以查看差异是否匹配。
最糟糕的情况是时间复杂度是O(ab)，如果这还不够好，您可以利用KMP进行更快的匹配。
with open('safein.txt') as in_file:
a, b = (int(x) for x in in_file.readline().split())
code = [int(in_file.readline()) for _ in range(a)]
plain = [int(in_file.readline()) for _ in range(b)]
for i in range(a):
k = code[i] - plain[0]
if k < 0:
continue
for j in range(1, b):
if code[i] - code[i + j] != plain[0] - plain[j]:
break
else:
break # found match, break outer loop
with open('safeout.txt', 'w') as out_file:
out_file.write('\n'.join(str(x - k) for x in code))https://stackoverflow.com/questions/45880448
复制相似问题
腾讯云开发者
