确定两个数组是否是彼此的旋转版本

Question

在JAVA中也问过类似的问题，但有人可以帮助我改进代码吗：并解释一下我的代码的时间复杂度和空间复杂性。我的代码检查两个数组是否相互轮换：list1 = [1， 2， 3， 4， 5， 6， 7]list2b = [4， 5， 6， 7， 1， 2， 3]is_rotation（list1， list2b） 应返回 True。list2c = [4， 5， 6， 9， 1， 2， 3]is_rotation（list1， list2c） 应返回 False。我的代码：def is_rotation (list1,list2):    i = 0    j = 0    k = 0    result = True    if len(list1) != len(list2):        return False      while i < len(list1) -1 and j < len(list1) -1:        if list1[i] == list2[j]:            i = i +1            j = j +1            break        elif list1[i] > list2[j]:            j = j +1        else:            i = i +1    else:        return False    for l in range(i,len(list1)):        if i == j:            if list1[i] != list2[j]:                 return False        elif list1[i] != list2[j] or list2[i] != list1[k]:            return False        else:            i = i +1            j = j +1            k = k +1    return result

Answer 1

有点笨拙的方式：

def is_rotation(lst1, lst2):

    if(len(lst1)==len(lst2)):

        return (str(lst1)[1:-1] in str(lst2+lst2)) & (str(lst2)[1:-1] in str(lst1+lst1)) 

    else:

        return False

它是如何工作的：

（1）检查两个列表的长度是否相同，如果没有返回False

（2）如果他们这样做，将第一个列表转换为，删除最外括号（通过删除第一个和最后一个字符 - 你可以在那里做任何括号，不仅是方形的，它也可以是一个）。stringtuple

（3）将按顺序返回复制的所有元素（如此一个接一个）。然后转换为字符串，它将只返回其字符串格式lst2+lst2lst2lst2list

（4）根据注释-为了处理角落情况-我们应该双向检查，因为如果是旋转版本，那么就是旋转版本的lst1lst2lst2lst1

测试

print(is_rotation([561, 1, 1, 1, 135], [1, 1, 1, 1, 1]))

#outputs False

print(is_rotation([[1,2,3,4], 2, 3, 4], [1, 2,3,4]))

#outputs False

print(is_rotation([1, 2, 3, 4, 5], [4, 5, 1, 2, 3]))

#outputs True

Answer 2

我通过另一种方式来做到这一点：

def is_rotation (list1,list2):

    if len(list1) != len(list2):

        return False

    for i in range(len(list1)):

        if list1[i:] + list1[:i] == list2:

            return True

    return False

1）测试两者是否具有相同的长度。

2）循环将旋转列表的所有可能性，并检查其中一个是否相等。

我不知道这是否是最好的方法，但很容易理解;)

Answer 3

您可以使用循环从迭代工具优化比较的数量，并避免创建数据的其他副本。（即 O（1） 空间在 O（n） 时间内）

下面是一个函数示例，如果两个列表是彼此的旋转，则返回旋转偏移量;如果它们不匹配，则返回 None。该逻辑永远不需要超过2N的比较来确定偏移量。

from itertools import cycle

def getRotation(listA,listB):

    if len(listA) != len(listB): return None

    unmatched,offset = len(listA),0

    iterA,iterB      = cycle(listA),cycle(listB)

    a = next(iterA)

    while unmatched and offset<len(listA):

        b = next(iterB)

        if a==b:

            unmatched -= 1

            a = next(iterA)

        else:

            unmatched = len(listA)

            offset   += 1

    if unmatched: return None

    return offset

外：

list1 = [1, 2, 3, 4, 5, 6, 7]

list2b = [4, 5, 6, 7, 1, 2, 3]

print(getRotation(list1,list2b)) # 4 (rotation to the right)

如果需要，您可以将其调整为仅返回 True 或 False。

它也可以很容易地进行调整，以检查是否可以通过循环使用另一个列表来生成列表。（例如[2，3，1，2，3，1，2，3，1，2]可以通过循环[1，2，3]产生）。我没有在示例中包含该功能，以避免混淆问题。

Answer 4

对于更明确的方法，您可以使用itertools逐个生成给定列表的所有旋转，如下所示：

import itertools as it

def get_rotations(lst1):

    foo = it.cycle(lst1)

    for y in range(len(lst1)):

        result = []

        for x in range(len(lst1)):

            result.append(next(foo))

        yield result

        next foo

然后你可以做：

def is_rotated(L1, L2) -> bool:

    bar = get_rotations(L1)

    While True:

        try:

            if next(bar) == L2;

                return True

        except StopIteration:

                return False

题外话：我认为这打破了所有关于使用异常来控制程序逻辑的正常流程的传统观点，但是......不知何故，感觉不对劲（C++的背景，我们一再被告知永远不要做这种事情）。是Pythonic吗？