在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
4 回答
動漫人物
TA貢獻1815條經驗 獲得超10個贊
有點笨拙的方式：
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
大話西游666
TA貢獻1817條經驗 獲得超14個贊
我通過另一種方式來做到這一點：
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）循環將旋轉列表的所有可能性，并檢查其中一個是否相等。
我不知道這是否是最好的方法，但很容易理解;)
揚帆大魚
TA貢獻1799條經驗 獲得超9個贊
您可以使用循環從迭代工具優化比較的數量，并避免創建數據的其他副本。（即 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]產生）。我沒有在示例中包含該功能，以避免混淆問題。
飲歌長嘯
TA貢獻1951條經驗 獲得超3個贊
對于更明確的方法，您可以使用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嗎？
添加回答
舉報
0/150
提交
取消