计算列表中的循环移位对

Question

A 循环移位 将数字中的一些数字移动到数字的开头，并将所有其他数字向前移动到下一个位置。例如，

564

的所有循环移位都是

564, 645, 456

。

假设两个长度相等的数字

a

和

b

是循环对，如果

a

可以通过循环移位变成

b

。使用上面的示例，

564

的循环对是

645

和

456

。

给定正整数数组

nums

，计算圆形对

i

和

j

的数量，其中

0 <= i < j < len(nums)

例如，

circular_shifts([13, 5604, 31, 2, 13, 4560, 546, 654, 456])

应返回

5

。配对为

(13, 31), (13, 13), (5604, 4560), (31, 13), (546, 654)

。

我写了一个蛮力解决方案，将数字的所有循环移位保存在字典

shifts

中，并且对于

num

中的每个数字

nums

，我检查以下所有数字，并且如果数字

num2

与以下数字相同

num

，我看看

num2

是否在

num

的循环移位中。如果是，那么我将其添加到总数中。

不幸的是，这个算法运行太慢并且超时，我正在寻找一种更快的方法来解决这个问题，任何人都可以想到优化、巧妙的技巧或其他策略来加快速度吗？

Answer 1

不是很优雅，因为时间不多，但以下应该更快，因为不会重复访问列表。为了简单起见，移位是在字符串上完成的。

from collections import Counter

def big(num):
    max = num
    s = str(num)
    for _ in s:
        x = int(s[-1] + s[0:-1])
        if x > max:
            max = x
    return max
        
circs = [big(z) for z in mylist]

c = Counter(circs)

total = 0
for i in c:
    if c[i] > 1:
        total += c[i]
print(total)

Answer 2

1. 用最大循环移位替换数组中的每个数字。例如，1234 将变成 4123
2. 计算每个结果数字出现的次数
3. 如果一个数字出现n次，则表示n(n-1)/2个循环移位对。把它们全部加起来。

Answer 3

这是我的解决方案，我们

1. 遍历列表
2. 将每个数字长度旋转1次
3. 仅当在剩余列表中找到该号码时才打印

    numbers = [13, 5604, 31, 2, 13, 4560, 546, 654, 456]
    # shift_pairs = [(13,31),(13,13),(5604,4560),(31,13),(546,654)]
    pairsFound = 0
    for i in range(len(numbers)):
        number = numbers[i]
        length = len(str(number))
        numberToRotate = number
        shift_remaining = length - 1
        temp_list = numbers[i+1:]
        while(shift_remaining >= 0):
            t_remainder = numberToRotate % 10 # 4
            numberToRotate = numberToRotate // 10 # 560
            numberToRotate = numberToRotate + t_remainder * 10 **(length-1) # 4560
            # we should also check for length for cases like 4560, where on a shift we get 456
            if(numberToRotate in temp_list and len(str(numberToRotate)) == length):
                print("({},{})".format(number,numberToRotate))
                pairsFound += 1
            shift_remaining -= 1
    print("no of pairs:", pairsFound)

输出

(13,31)
(13,13)
(5604,4560)
(31,13)
(546,654)
no of pairs: 5

Answer 4

from collections import Counter

def big(num):
    max_num = num
    s = str(num)
    for _ in s:
        x = int(s[-1] + s[0:-1])
        if x > max_num:
            max_num = x
        s = s[-1] + s[0:-1]  # Update s for the next iteration
    return max_num
        
mylist = [1, 1, 1, 1]  # Example list
circs = [big(z) for z in mylist]

c = Counter(circs)

total = 0
for i in c:
    if c[i] > 1:
        total += c[i] * (c[i] - 1) // 2
print(total)