在JAVA中也問過類似的問題，但有人可以幫助我改進(jìn)代碼嗎：并解釋一下我的代碼的時(shí)間復(fù)雜度和空間復(fù)雜性。我的代碼檢查兩個(gè)數(shù)組是否相互輪換：list1 = [1， 2， 3， 4， 5， 6， 7]list2b = [4， 5， 6， 7， 1， 2， 3]is_rotation（list1， list2b） 應(yīng)返回 True。list2c = [4， 5， 6， 9， 1， 2， 3]is_rotation（list1， list2c） 應(yīng)返回 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 回答
動(dòng)漫人物
TA貢獻(xiàn)1815條經(jīng)驗(yàn) 獲得超10個(gè)贊
有點(diǎn)笨拙的方式：
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）檢查兩個(gè)列表的長度是否相同，如果沒有返回False
（2）如果他們這樣做，將第一個(gè)列表轉(zhuǎn)換為，刪除最外括號(hào)（通過刪除第一個(gè)和最后一個(gè)字符 - 你可以在那里做任何括號(hào)，不僅是方形的，它也可以是一個(gè)）。stringtuple
（3）將按順序返回復(fù)制的所有元素（如此一個(gè)接一個(gè)）。然后轉(zhuǎn)換為字符串，它將只返回其字符串格式lst2+lst2lst2lst2list
（4）根據(jù)注釋-為了處理角落情況-我們應(yīng)該雙向檢查，因?yàn)槿绻切D(zhuǎn)版本，那么就是旋轉(zhuǎn)版本的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貢獻(xiàn)1817條經(jīng)驗(yàn) 獲得超14個(gè)贊
我通過另一種方式來做到這一點(diǎn)：
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）循環(huán)將旋轉(zhuǎn)列表的所有可能性，并檢查其中一個(gè)是否相等。
我不知道這是否是最好的方法，但很容易理解;)
揚(yáng)帆大魚
TA貢獻(xiàn)1799條經(jīng)驗(yàn) 獲得超9個(gè)贊
您可以使用循環(huán)從迭代工具優(yōu)化比較的數(shù)量，并避免創(chuàng)建數(shù)據(jù)的其他副本。（即 O（1） 空間在 O（n） 時(shí)間內(nèi)）
下面是一個(gè)函數(shù)示例，如果兩個(gè)列表是彼此的旋轉(zhuǎn)，則返回旋轉(zhuǎn)偏移量;如果它們不匹配，則返回 None。該邏輯永遠(yuǎn)不需要超過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)
如果需要，您可以將其調(diào)整為僅返回 True 或 False。
它也可以很容易地進(jìn)行調(diào)整，以檢查是否可以通過循環(huán)使用另一個(gè)列表來生成列表。（例如[2，3，1，2，3，1，2，3，1，2]可以通過循環(huán)[1，2，3]產(chǎn)生）。我沒有在示例中包含該功能，以避免混淆問題。
飲歌長嘯
TA貢獻(xiàn)1951條經(jīng)驗(yàn) 獲得超3個(gè)贊
對于更明確的方法，您可以使用itertools逐個(gè)生成給定列表的所有旋轉(zhuǎn)，如下所示：
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
題外話：我認(rèn)為這打破了所有關(guān)于使用異常來控制程序邏輯的正常流程的傳統(tǒng)觀點(diǎn)，但是......不知何故，感覺不對勁（C++的背景，我們一再被告知永遠(yuǎn)不要做這種事情）。是Pythonic嗎？
添加回答
舉報(bào)
0/150
提交
取消