有代码执行时间限制的字符串排序问题

Question

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

问题陈述：循环移位

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

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

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

输入格式：

第一行：一个整数T表示测试用例的数量对于每个测试用例：第一行：两个 space 分隔的整数 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)

Answer 1

我对你发布的代码无能为力，因为你用无意义的变量和缺乏解释混淆了它。当我扫描它时，我得到的印象是您采用了在 long-running 循环中进行 single-digit 移位的直接方法。您计算迭代次数，直到第 K 次点击 B。

这很容易理解，但繁琐且效率低下。

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

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

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

我希望你能从这里完成算法并进行编码。

啊——作为需求描述，你的问题的措辞表明 B 是给定的。如果不是，则需要检测最大值。

要查找 B，请将 A 附加到自身。找到具有最大值的 A-length 字符串。您可以通过查找最长的 1 字符串，在第一个 0 之后的 value-trees 应用其他 well-known string-search 算法来加速此过程。

请注意，当您遍历 A 时，您会寻找重复原始值的第一个位置：这是所需的重复长度，它会驱动 direct-computation 阶段我回答的第一部分。

Answer 2

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

如 Prune 所述，您必须使用一些有效的算法来查找子序列，例如 sub1，其重复构成给定的字符串 A。如果您通过 brute-force 解决此问题，时间复杂度将为 O (n*n)，因为n的最大值为1e5，会超过时间限制。所以使用一些有效的算法。

有代码执行时间限制的字符串排序问题

String sorting problem with code execution time limit

python

arrays

sorting

string

time-limiting