我有一些整數列表，例如：l1 = [8,9,8,9,8,9,8],
l2 = [3,4,2,4,3]我的目的是將它切成最小的重復片段。所以：output_l1 = [8,9]
output_l2 = [3,4,2,4]最大的問題是序列每次都沒有完全完成。所以不是'abcabcabc'只是'abcabcab'。
3 回答
慕容708150
TA貢獻1831條經驗 獲得超4個贊
def shortest_repeating_sequence(inp):
for i in range(1, len(inp)):
if all(inp[j] == inp[j % i] for j in range(i, len(inp))):
return inp[:i]
# inp doesn't have a repeating pattern if we got this far
return inp[:]
這段代碼是O(n^2)。最壞的情況是一個元素重復了很多次，然后在最后出現了一些打破模式的東西，例如[1, 1, 1, 1, 1, 1, 1, 1, 1, 8]。
您從 開始1，然后遍歷整個列表，檢查每個列表是否inp[i]等于inp[i % 1]。任何數字% 1都等于0，因此您要檢查輸入中的每一項是否等于輸入中的第一項。如果所有項目都等于第一個元素，那么重復模式是一個只有第一個元素的列表，所以我們返回inp[:1]。
如果在某個時候您遇到了一個不等于第一個元素的元素（all()一旦找到 a 就停止False），您可以嘗試使用2. 所以現在您要檢查偶數索引處的每個元素是否等于第一個元素 ( 4 % 2is 0)，以及每個奇數索引是否等于第二個元素( 5 % 2is 1)。如果你一直通過這個，模式是前兩個元素，所以 return inp[:2]，否則再試一次，3依此類推。
你可以這樣做range(1, len(inp)+1)，然后for循環將處理inp不包含重復模式的情況，但是你必須在最后不必要地迭代整個inp。而且你仍然必須return []在最后處理inp成為空列表。
我返回列表 ( inp[:])的副本而不是列表以具有一致的行為。如果我返回原始列表，return inp并且有人在沒有重復模式的列表上調用該函數（即他們的重復模式是原始列表），然后對重復模式執行某些操作，它也會修改他們的原始列表.
shortest_repeating_sequence([4, 2, 7, 4, 6]) # no pattern
[4, 2, 7, 4, 6]
shortest_repeating_sequence([2, 3, 1, 2, 3]) # pattern doesn't repeat fully
[2, 3, 1]
shortest_repeating_sequence([2, 3, 1, 2]) # pattern doesn't repeat fully
[2, 3, 1]
shortest_repeating_sequence([8, 9, 8, 9, 8, 9, 8])
[8, 9]
shortest_repeating_sequence([1, 1, 1, 1, 1])
[1]
shortest_repeating_sequence([])
[]
呼喚遠方
TA貢獻1856條經驗 獲得超11個贊
下面的代碼是的返工您的方案，解決了一些問題：
您發布的解決方案無法處理您自己的
'abcabcab'示例。您的解決方案即使在找到有效結果后也會繼續處理，然后過濾有效和無效結果。相反，一旦找到有效結果，我們就會處理并返回它。其他有效結果和無效結果將被簡單地忽略。
@Boris 關于在沒有重復模式的情況下返回輸入的問題。
代碼
def repeated_piece(target):
target = list(target)
length = len(target)
for final in range(1, length):
result = []
while len(result) < length:
for i in target[:final]:
result.append(i)
if result[:length] == target:
return result[:final]
return target
l1 = [8, 9, 8, 9, 8, 9, 8]
l2 = [3, 4, 2, 4, 3]
l3 = 'abcabcab'
l4 = [1, 2, 3]
print(*repeated_piece(l1), sep='')
print(*repeated_piece(l2), sep='')
print(*repeated_piece(l3), sep='')
print(*repeated_piece(l4), sep='')
輸出
% python3 test.py
89
3424
abc
123
%
您仍然可以使用：
print(''.join(map(str, repeated_piece(l1))))
如果您對更簡單的 Python 3 習慣用法感到不舒服：
print(*repeated_piece(l1), sep='')
喵喵時光機
TA貢獻1846條經驗 獲得超7個贊
解決方案
target = [8,9,8,9,8,9,8]
length = len(target)
result = []
results = [] * length
for j in range(1, length):
result = []
while len(result) < length:
for i in target[:j]:
result.append(i)
results.append(result)
final = []
for i in range(0, len(results)):
if results[i][:length] == target:
final.append(1)
else:
final.append(0)
if 1 in final:
solution = results[final.index(1)][:final.index(1)+1]
else:
solution = target
int(''.join(map(str, solution)))
'結果：[8, 9]'。
添加回答
舉報
0/150
提交
取消