小编典典

查找字符串中重复字符的最长子字符串

algorithm

(这是此代码强制问题的基础)

除非我真的真的被卡住了,否则我会尽量不寻求有关代码强制问题的帮助,而这恰好是现在。

您的第一个任务是找到火星数据库的密码。为此,您的最佳机密人员已经发现以下事实:密码是给定字符串的子字符串,该字符串由一系列非递减数字组成。密码尽可能长。密码始终是回文式。向后读取相同的字符串。赛车,鲍勃和中午都是著名的例子。鉴于这些事实,您可以找到数据库的所有可能的密码吗?输入第一行包含n,即输入字符串的长度(1≤n≤105)。下一行包含长度为n的字符串。该字符串的每个字符都是一个数字。字符串中的数字按非降序排列。输出在第一行上,打印可能的密码数k。在接下来的k行中

我的观察是:

  1. 非递减字符串中的回文仅是重复字符的字符串(例如“ 4444”或“ 11”)

  2. 在字符i上,i的最后一个实例-i的第一个实例+1 =重复字符的长度

  3. 跟踪最大密码长度,然后过滤出所有比最大密码长度短的项目,以确保输出的密码为最大长度

基于这些观察,我的解决方案是:

n,s = [input() for i in range(2)]#input

maxlength = 0

results = []


for i in s:
    length = (s.rfind(i)-s.find(i))+1

    if int(i*(length)) not in results and length>=maxlength:

        results.append(int(i*(length)))

        maxlength = length



#filer everything lower than the max password length out
results = [i for i in results if len(str(i))>=maxlength]


#output
print(len(results))

for y in results:
    print(y)

不幸的是,该解决方案实际上是错误的,并且在第4个测试用例上失败。我不了解代码有什么问题,因此无法修复。有人可以帮忙吗?

谢谢阅读!


阅读 390

收藏
2020-07-28

共1个答案

小编典典

您的程序将失败:

4
0011

它只会返回11

问题是的长度str(int('00'))等于1。

您可以通过从程序中删除intstr调用来解决此问题(即将答案另存为字符串而不是整数)。

2020-07-28