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

Question

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

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

如果字符串A是[A0，A1，…，An-1]，则在执行一个循环移位，字符串变为[A1，A2，…，An-1，A0]。

你执行了无数次轮班，每次记录由字符串表示的二进制数的值。这个在执行(可能为0(操作是B。您的任务是确定循环移位的次数可以执行，使得字符串A表示的值将在第K次等于B。

输入格式：

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

输出格式：

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

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)