时间戳

首页 > 解决方案 > 确定两个数组是否是彼此的旋转版本

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

问题描述

在 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

标签： pythonpython-3.xalgorithm

解决方案

有点hacky的方式：

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）如果他们这样做，将第一个列表转换为string，删除最外面的括号（通过删除第一个和最后一个字符 - 你可以在那里做任何括号，不仅是方括号，它也可以是 a tuple）。

(3)会依次lst2+lst2返回所有重复的元素（这样一个接一个）。然后转换为字符串，它将只返回其字符串格式lst2lst2list

（4）根据评论 - 为了处理极端情况 - 我们应该检查两种方式，因为 iflst1是旋转版本lst2thenlst2是旋转版本lst1

测试

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

推荐阅读