时间戳

首页 > 解决方案 > 如何解决“超出 CPU 限制”的问题？

python - 如何解决“超出 CPU 限制”的问题？

问题描述

我正在尝试解决Toph 上的“Aaj Kemon Bodh Korcho”问题：

巴塞罗那和皇家马德里之间有一场比赛。[...] 比赛的每一秒都有一个进球。所有的目标可能不是有效的，即一些目标可以从超出规则的 OFF SIDE 完成。

[输出]“Aaj Kemon Bodh Korcho”（不带引号）如果巴塞罗那赢得比赛，“Hala Madrid”（不带引号）如果皇家马德里赢得比赛或“Meh :\”（不带引号）如果没有获胜者。

[...] 从 OFF SIDE 完成的目标属于（原文如此）著名系列 [...]：

0, 1, 1, 2, 3, 5, 8 ..., ..., ..., ..., ...,第 n项

输入

你得到一个整数T，它表示测试用例的数量(T <=100)。在（原文如此）中，每行T都包含一个字符串（S），后面是字符(B, M)。字符串的最大长度不会大于10 5。请注意，起始索引将为0。

在这里，
如果第i个字符是B，那么它表示巴塞罗那在第 i 秒完成了一个进球。 如果第 i个字符是M，则表示皇家马德里在第 i 秒完成了一个进球。

输出

对于每条T行，您必须首先根据格式Case #X打印案例编号，其中 X 是案例编号。然后，如果巴塞罗那赢得比赛，则必须打印Aaj Kemon Bodh Korcho；如果皇家马德里赢得比赛，则必须打印Hala Madrid 。否则打印 Meh :\。有关更多说明，请参见下面的示例。

样本

Input   Output

2
BBMMMM  Case #1: Hala Madrid
MMBBBB  Case #2: Aaj Kemon Bodh Korcho

这是我的代码：

f=[0,1]
num_of_testcase = int(input())
store_2 = []
for i in range(num_of_testcase):
    numbers = input()
    store_1 = list(numbers)
    for x in range(len(store_1)):
        f.append(f[x]+f[x+1])
    f = sorted(set(f), key=f.index)
    for y in f:
        try:
            del store_1[y]
        except:
            store_2.append(store_1)
    if store_1.count("B") > store_1.count("M"):
        print("Case #" + str(int(i+1)) + ":" + " Aaj Kemon Bodh Korcho")
    elif store_1.count("B") < store_1.count("M"):
        print("Case #" + str(int(i+1)) + ":" + " Hala Madrid")
    else:
        print("Case #" + str(int(i+1)) + ":" + " Meh :\\")

当我提交我的代码时，它会在第二个测试用例上显示 CPU Time Exceeded。如何让我的代码运行得更快？

标签： pythonpython-3.xalgorithm

解决方案

在您的程序中，您有这一行 del store_1[y]。根据此处，这是一个 O(n) 操作。因此，您的代码在 O(n 2 ) 中有效。这就是为什么你得到CPU Time Exceeded。

维持2个柜台，b=0和m=0。遍历给定的字符串并查找给定的索引是否是集合的一部分，如果是，则不做任何事情。否则检查它是否是B或M。因此，增加计数器并在最后进行必要的检查。

此外，您实际上可以生成一次并一次又一次地将结果用于测试用例，而不是多次生成斐波那契数列。

推荐阅读