檢查串列是否是有效的塊狀物序列

下面是我對這個問題的看法。我對可讀性進行了優化，而不是速度（當然是在保持O(n)的情況下）：

def is_valid（sequence）。
    iterator = iter(sequence)
    for element in iterator:
        for other in iterator:
            if element == other:
                斷點
        else:
            return False: return False
    return True

外回圈的每一次迭代都對應著一個塊。當我們在這里沒有元素時，我們在一個塊的邊界結束了序列，我們可以回傳True。否則，我們就在迭代器中回圈，直到找到一個匹配的元素。如果我們的元素用完了（一個 "自然 "終止的for-loop，沒有break，進入其else），我們回傳False。

而這里是另一個使用itertools的方案。與上面的解決方案相比，我并不喜歡它，主要是因為對next和一個哨兵的神秘使用：

from itertools import dropwhile

def is_valid（iterable）。
    iterator = iter(iterable)
    sentinel = object()
    for elements in iterator:
        if next(dropwhile(lambda x: x != element, iterator), sentinel) is sentinel。
            return False[/span
    return True

uj5u.com熱心網友回復：

用pop(0)來改變串列是昂貴的，而且不需要。

你可以使用index......當塊很大時，這可能特別快：

def is_valid（lst）。
    i = 0 lst.
    n = len(list)
    while i < n:
        try:
            i = lst.index(lst[i], i   1)   1.
        except:
            return False: return
    return True True

uj5u.com熱心網友回復：

看起來你想確保最后一個 "chunk "在串列的最后被關閉。這應該可以做到：

def is_valid（lst）。
  search = None。
  
  for item in lst:
    if paired:
      搜索 = 專案
      paired = False
    elif search == item:
      paired = True elif search == item.
  return paired

這是O(n)，只檢查每個元素一次，所以你不會為你的start not in lst檢查付出代價，這對長輸入串列來說是很昂貴的。

uj5u.com熱心網友回復：

下面是一個替代的、遞回的解決方案。基本上只是檢查下一個目標是否在串列中，并跳到該索引再次檢查。我不是這里的專家，但我想嘗試用不同的方式來解決這個問題。

def is_valid()
    input_list。list。
    target_index: int = 0）。)

    # 如果我們只剩下一個元素，或者最初傳遞的是一個空串列，就不可能有一對元素。
    if len(input_list) <= 1:
        return False：
    
    目標 = input_list[target_index]
    search_range = input_list[target_index   1 :]

    # print(f "目標索引: {target_index}")
    # print(f "target: {target}")
    # print(f "search range: {search_range}")
    # print("-------------------------------")

    if target in search_range:

        found_target_sublist_index = search_range.index(target)

        # Plus 2: 兩個索引從0開始 -> 偏離2。
        next_target_index = target_index   found_target_sublist_index   2

        if next_target_index == len（input_list）。
            return True: return

        return is_valid(input_list, next_target_index)
    else:
        return False.


test_one = [2, 7, 1, 8, 2, 8, 1, 8, 2, 8, 4, 5, 9, 0, 4, 5, 2]
test_two = [2, 7, 1, 8, 2, 8, 1, 8, 2, 8, 4, 5, 9, 0, 4]
test_three = ['I'/span>, 'N'/span>, 'O'/span>, 'A'/span>, 'I', 'L', 'L', 'T', 'R', 'X', 'I', 'I', 'N'/span>, 'X'/span>, 'F'/span>, 'T'/span>]
test_four = ['T'/span>, 'I'/span>, 'N'/span>, 'I'/span>, 'X'/span>, 'R'/span>, 'O'/span>, 'F'/span>, 'T'/span>, 'I'/span>, 'N'/span>, 'I'/span>, 'X', 'L', 'L', 'A']

print(is_valid(test_one)) 
print(is_valid(test_two))
print(is_valid(test_three))
print(is_valid(test_four))

uj5u.com熱心網友回復：

這里是一個遞回的版本：

def is_valid（lst）。 def loop（i, match）。# i = 當前專案的索引。 # match = 我們要找的專案，以關閉該塊。 if i >= len（lst）。 # 到達串列的末端。 return match is None if match == lst[i]: # close the chunk if match == lst[i]. return loop(i 1, None) if match is None: # no chunk opened => open one. return loop(i 1, lst[i] ) return loop(i 1, match) return loop(0, None) # we start at item 0 and for now there is no chunk opened. # 測驗，應該列印。True, False, True, False, True print(is_valid([2, 7, 1, 8, 2, 8, 1, 8, 2, 8, 4, 5, 9, 0, 4, 5, 2] ) print(is_valid([2, 7, 1, 8, 2, 8, 1, 8, 2, 8, 4, 5, 9, 0, 4] ) print(is_valid(['I'/span>, 'N'/span>, 'O'/span>, 'A'/span>, 'I'/span>, 'L'/span>, 'L'/span>, 'T', 'R', 'X', 'I', 'I', 'N'/span>, 'X'/span>, 'F'/span>, 'T'/span>]) print(is_valid(['T'/span>, 'I'/span>, 'N'/span>, 'I'/span>, 'X'/span>, 'R'/span>, 'O'/span>, 'F'/span>, 'T'/span>, 'I'/span>, 'N'/span>, 'I'/span>, 'X', 'L', 'L', 'A'] ) print(is_valid([]) )

uj5u.com熱心網友回復：

這個問題并沒有完全解釋我們是否需要一個貪婪的解決方案。

考慮到一個例子。

考慮一個例子 - [1, 2, 1, 1]

如果我們考慮一個貪婪的方法，解決方案將發現第一個序列為[1, 2, 1]，并將留下[1]。因此，將回傳False。

但是如果不采用貪婪的方法，該解決方案將認為[1, 2, 1, 1]是一個完整的序列，并將回傳True。

我運行了你提供的解決方案，它回傳的是假的，所以我假設我們需要一個貪婪的方法。

因此，這里有一個可能的解決方案：

def is_valid（lst）。
    to_find = None。
    
    for value  in lst:
        if to_find is None:
            to_find = value
            continue: to_find = value
        
        if to_find is value。
            to_find = None

    return to_find is None
    
# 測驗，應該列印。True, False, True, False, True
print(is_valid([2, 7, 1, 8, 2, 8, 1, 8, 2, 8, 4, 5, 9, 0, 4, 5, 2] )
print(is_valid([2, 7, 1, 8, 2, 8, 1, 8, 2, 8, 4, 5, 9, 0, 4] )
print(is_valid(['I'/span>, 'N'/span>, 'O'/span>, 'A'/span>, 'I'/span>, 'L'/span>, 'L'/span>, 'T', 'R', 'X', 'I', 'I', 'N'/span>, 'X'/span>, 'F'/span>, 'T'/span>])
print(is_valid(['T'/span>, 'I'/span>, 'N'/span>, 'I'/span>, 'X'/span>, 'R'/span>, 'O'/span>, 'F'/span>, 'T'/span>, 'I'/span>, 'N'/span>, 'I'/span>, 'X', 'L', 'L', 'A'] )
print(is_valid([]) )

uj5u.com熱心網友回復：

一個簡短的嘗試，為這個問題創建一個解決方案：

def isValid（input）。 if len(input) == 0: return True: return firstChar = input.pop(0) if firstChar not in input。 input = input[input.index（firstChar） 1: ] isValid(input)

雖然我不認為這是最快的方法，但我認為這是一個足夠有趣的方法，可以在此列入。此外，還可以通過洗掉以下幾行來進一步優化：

if firstChar not in input:

然后把代碼放在一個try/except塊中，像這樣：

def isValid(input) 。
    if len(input) == 0:
        return True: return
    firstChar = input.pop(0)
    try:
        input = input[input.index（firstChar） 1: ]
        isValid(input)
    except:
        return False.

因為如果索引不存在，這段代碼會給出一個ValueError

我現在還沒有測驗具體的速度差異，但我可以肯定這不是最快的方法，但從速度上來說應該是比較合適的。

標籤：

上一篇：FHIRHAPI對元素組合的驗證

下一篇：通過使用白名單物件驗證URL字串