1

我最近试图解决一个 HackerEarth 问题。该代码适用于我提供的示例输入和一些自定义输入。但是，当我提交时，它显示超出时间限制的错误。有人可以解释我如何使代码运行得更快吗？

问题陈述：循环移位

一个大的二进制数由大小为 N 的字符串 A 表示，由 0 和 1 组成。您必须对此字符串执行循环移位。循环移位操作定义如下：

如果字符串 A 为 [A0, A1,..., An-1]，则在执行一次循环移位后，字符串变为 [A1, A2,..., An-1, A0]。

您执行了无限次移位，并且每次都记录了字符串表示的二进制数的值。执行（可能为 0）操作后形成的最大二进制数是 B。您的任务是确定可以执行的循环移位数，以使字符串 A 表示的值第 K 次等于 B。

输入格式：

第一行：一个整数 T 表示测试用例的数量对于每个测试用例：第一行：两个空格分隔的整数 N 和 K 第二行：A 表示字符串

输出格式：

对于每个测试用例，打印一行，其中包含一个整数，该整数表示执行的循环移位操作的数量，使得字符串 A 表示的值第 K 次等于 B。

代码：

import math


def value(s):
    u = len(s)
    d = 0
    for h in range(u):
        d = d + (int(s[u-1-h]) * math.pow(2, h))
    return d


t = int(input())
for i in range(t):
    x = list(map(int, input().split()))
    n = x[0]
    k = x[1]
    a = input()
    v = 0
    for j in range(n):
        a = a[1:] + a[0]
        if value(a) > v:
            b = a
            v = value(a)
    ctr = 0
    cou = 0
    while ctr < k:
        a = a[1:] + a[0]
        cou = cou + 1
        if a == b:
            ctr = ctr + 1
    print(cou)
4

2 回答 2

2

在该问题中，对 n 的约束是 0<=n<=1e5。在函数 value() 中，您从长度可以达到 1e5 的二进制字符串计算整数。所以你计算的整数可以高达 pow(2, 1e5)。这肯定是不切实际的。

正如 Prune 所提到的，你必须使用一些有效的算法来找到一个子序列，比如 sub1，它的重复构成给定的字符串 A。如果你用蛮力解决这个问题，时间复杂度将是 O(n*n)，如n 的最大值为 1e5，会超过时间限制。所以使用一些有效的算法。

于 2020-08-19T07:13:20.083 回答
1

我对您发布的代码无能为力，因为您用无意义的变量和缺乏解释混淆了它。当我扫描它时，我的印象是您已经采用了在长时间运行的循环中进行一位数移位的简单方法。你计算迭代，直到你第一次命中B。K

这很容易理解，但是麻烦且效率低下。

由于循环每次N迭代都会重复，因此您不会从重复该过程中获得新信息。您需要做的就是找到N您遇到的一系列迭代中的哪个位置B......这可能是多次。

为了B出现多次，A必须由特定的比特子序列组成，重复 2 次或更多次。例如，101010或011011。您可以通过对当前算法的简单添加来检测这一点：在每次迭代中，检查当前字符串是否与原始字符串匹配。第一次点击时，只需将重复因子计算为rep = len(a) / j。此时，退出移位循环： 的当前值b是正确的。

现在您已经有了b它在第一次j旋转中的位置，您可以直接计算所需的结果而无需进一步处理。

我希望您可以从这里完成算法并进行编码。

啊-作为需求描述，您的问题的措辞表明这B是给定的。如果不是，那么您需要检测最大值。

要查找B，请附加A到自身。找到具有最大值的 A 长度字符串。您可以通过查找 s 的最长字符串来加速此过程，在第一个之后的那些最大字符串1之后对值树应用其他众所周知的字符串搜索算法。0

请注意，当您迭代 时A，您会寻找重复原始值的第一个位置：这是所需的重复长度，它驱动我答案第一部分中的直接计算阶段。

于 2020-08-15T07:25:49.613 回答