查找带旋转的最大二进制数，超过时间限制

Question

通过了一些测试用例，但在提交后，超过了时间限制。如何优化解决方案以降低时间复杂性

A large binary number is represented by a string A of size N and comprises of 0s and 1s. You must perform a cyclic shift on this string. The cyclic shift operation is defined as follows:

If the string A is [A0, A1,..., An-1], then after performing one cyclic shift, the string becomes [A1, A2,..., An-1, A0].

You performed the shift infinite number of times and each time you recorded the value of the binary number represented by the string. The maximum binary number formed after performing (possibly 0) the operation is B. Your task is to determine the number of cyclic shifts that can be performed such that the value represented by the string A will be equal to B for the Kth time.

Input format:

First line: A single integer T denoting the number of test cases For each test case: First line: Two space-separated integers N and K Second line: A denoting the string

Output format:

For each test case, print a single line containing one integer that represents the number of cyclic shift operations performed such that the value represented by string A is equal to B for the Kth time.

num_test_cases = int(input())
for i in range(num_test_cases):
    array_length, num_of_repetition = map(int, input().split())

    count = 0
    bin_num = input()
    original_bin_num = bin_num
    dec_num = int(bin_num, 2)
    maximum = dec_num
    dec_num_array = [dec_num]

    for j in range(array_length - 1):
        bin_num = bin_num[1:] + bin_num[0]
        if bin_num == original_bin_num:
            break
        dec_num = int(bin_num, 2) 
        dec_num_array.append(dec_num)
    maximum = max(dec_num_array)
    maxIndex = dec_num_array.index(maximum)
    num_cyclic_shifts = 0
    for kek in range(num_of_repetition):
        if kek == 0:
            num_cyclic_shifts += maxIndex
        elif len(dec_num_array) == array_length:
            num_cyclic_shifts += array_length
        elif len(dec_num_array) < array_length:
            num_cyclic_shifts += len(dec_num_array)        
    print(num_cyclic_shifts)

Answer 1

既然你要求优化你的代码，我就是这样做的。 用公式替换最后一个for循环

num_cyclic_shifts = maxIndex + (len(dec_num_array) * (num_of_repetition-1))

整个代码将成为

num_test_cases = int(input())
for i in range(num_test_cases):
    array_length, num_of_repetition = map(int, input().split())

    count = 0
    bin_num = input()
    original_bin_num = bin_num
    dec_num = int(bin_num, 2)
    maximum = dec_num
    dec_num_array = [dec_num]

    for j in range(array_length - 1):
        bin_num = bin_num[1:] + bin_num[0]
        if bin_num == original_bin_num:
            break
        dec_num = int(bin_num, 2)
        dec_num_array.append(dec_num)
    maximum = max(dec_num_array)
    maxIndex = dec_num_array.index(maximum)
    num_cyclic_shifts = maxIndex + (len(dec_num_array) * (num_of_repetition-1))
    print(num_cyclic_shifts)