Kattis"数字"问题：为什么我的第一组代码超过了时间限制，而我的第二组代码却没有？

Question

我目前正在Kattis上做一个问题(https://open.kattis.com/problems/digits)。

任务描述如下：

给定任何数字x0，使用以下递推式定义序列xi+1=xi的十进制表示中的位数您的任务是确定最小的正i，使xi=xi−1。

我最初想到了代码A，但在代码A未能达到时间限制后，我对代码进行了一些修改，以达到代码B。

样本输入

42
5
END

样本输出

3
2

代码A:

#time limit exceeded
def recurrence_index(prev):
counter = 1
while True:
current = len(str(prev))
if current == prev:
return counter
else:
counter += 1
prev = current

while True:
initial = input().strip()
if initial == 'END':
break
initial = int(initial)
print(recurrence_index(initial))

代码B:

def recurrence_index(prev):
counter = 2
while True:
current = len(str(prev))
if current == prev:
return counter
else:
counter += 1
prev = current

while True:
initial = input().strip()
if initial == 'END':
break
l = len(initial)
if l == 1 and int(initial) == 1:
print(1)
else:
print(recurrence_index(l))

不幸的是，我不太清楚为什么代码B比代码A快。看来我是幸运地找到了正确的答案。如果有人能帮助解释为什么代码B比代码A快，我们将非常感谢您的帮助。非常感谢。

Answer 1

在第一段代码中，int(initial)在巨大的整数上是昂贵的，而且这种努力被放弃了，因为你最终只对它调用str((，这可能也很昂贵。

在第二段代码中，您只需直接调用len(initial)，因此您只会对小于100万的小整数调用str()，以获得小于len("1000000")==7的长度。