检查列表是否是另一个与重复项一起使用的列表的轮换

Question

我有这个函数来确定列表是否是另一个列表的轮换:

def isRotation(a,b):
  if len(a) != len(b):
    return False

  c=b*2
  i=0

  while a[0] != c[i]:
    i+=1

  for x in a:
    if x!= c[i]:
      return False
    i+=1

  return True

例如

>>> a = [1,2,3]
>>> b = [2,3,1]
>>> isRotation(a, b)
True

如何使用重复项进行此操作？例如

a = [3,1,2,3,4]
b = [3,4,3,1,2]

它可以及时完成O(n)吗？

Answer 1

以下元算法将解决它.

• 构建a例如a = [3,1,2,3,4]=> 的串联aa = [3,1,2,3,4,3,1,2,3,4].

• 运行一个字符串匹配算法,例如,任意字符串匹配博耶·摩尔发现b在aa.

我首先尝试的一个特别简单的实现是使用Rabin Karp作为底层算法.在这,你会的

• 计算拉宾指纹的b

• 计算拉宾指纹aa[: len(b)],aa[1: len(b) + 1]...,并比较列表仅在指纹匹配

注意

• 可以非常有效地迭代计算滑动窗口的Rabin指纹(在Rabin-Karp链接中读取它)

• 如果你的列表是整数,你实际上比字符串更容易,因为你不需要考虑一个字母的数字哈希值是什么

-

Answer 2

您可以使用最大后缀算法的修改版本在0(n)时间和0(1)空间上执行此操作:

来自弦乐学的宝石: 词语的循环平等

长度为n的单词u的旋转是形式为u [k + 1 ... n] [l ... k]的任何单词.让你,你是两个长度相同的词.如果某些i,j的u(i)== w(j),则认为它们是循环等价的.

如果将单词u和w写成圆圈,则如果圆圈在适当的旋转后重合,则它们是循环等效的.

有几种线性时间算法可用于测试两个单词的循环等价.最简单的方法是将任何字符串匹配算法应用于模式pat = u和text = ww,因为如果文本中出现pat,则单词u和w是循环=等效的.

另一种算法是找到uu和ww的最大后缀,并检查它们在大小为n的前缀上是否相同.我们之所以选择这个问题,是因为有一个更简单有趣的算法,同时在线性时间和恒定空间中工作,值得表达.

Algorithm Cyclic-Equivalence(u, w)
{ checks cyclic equality of u and w of common length n }
    x := uu; y := ww;
    i := 0; j := 0;
    while (i < n) and (j < n) do begin
        k := 1;
        while x[i + k] = y[j + k] do k := k + 1;
        if k > n then return true;
        if x[i + k]> y[i + k] then i := i + k else j := j + k;
        { invariant }
    end;
    return false; 

哪个翻译成python变成:

def cyclic_equiv(u, v):
    n, i, j = len(u), 0, 0
    if n != len(v):
        return False
    while i < n and j < n:
        k = 1
        while k <= n and u[(i + k) % n] == v[(j + k) % n]:
            k += 1
        if k > n:
            return True
        if u[(i + k) % n] > v[(j + k) % n]:
            i += k
        else:
            j += k
    return False

举几个例子:

In [4]: a = [3,1,2,3,4]   
In [5]: b =[3,4,3,1,2]   
In [6]: cyclic_equiv(a,b)
Out[6]: True    
In [7]: b =[3,4,3,2,1]    
In [8]: cyclic_equiv(a,b)
Out[8]: False    
In [9]: b =[3,4,3,2]    
In [10]: cyclic_equiv(a,b)
Out[10]: False
In [11]: cyclic_equiv([1,2,3],[1,2,3])
Out[11]: True
In [12]: cyclic_equiv([3,1,2],[1,2,3])
Out[12]: True

更天真的方法是使用collections.deque来旋转元素:

def rot(l1,l2):
    from collections import deque
    if l1 == l2:
        return True
    # if length is different we cannot get a match
    if len(l2) != len(l1):
        return False
    # if any elements are different we cannot get a match
    if set(l1).difference(l2):
        return False
    l2,l1 = deque(l2),deque(l1)
    for i in range(len(l1)):
        l2.rotate() # l2.appendleft(d.pop()) 
        if l1 == l2:
            return True
    return False

Answer 3

我想你可以使用这样的东西:

a1 = [3,4,5,1,2,4,2]
a2 = [4,5,1,2,4,2,3]

# Array a2 is rotation of array a1 if it's sublist of a1+a1
def is_rotation(a1, a2):
   if len(a1) != len(a2):
       return False

   double_array = a1 + a1

   return check_sublist(double_array, a2)

def check_sublist(a1, a2):
   if len(a1) < len(a2):
       return False

   j = 0
   for i in range(len(a1)):
        if a1[i] == a2[j]:
              j += 1
        else:
              j = 0

        if j == len(a2):
              return True

   return j == len(a2)

如果我们谈论面试问题,那就是常识:

• 我们应该记住,解决方案应该易于编码和描述.
• 不要试图记住面试的解决方案.最好记住核心原则并重新实现它.