在给定列表中按顺序查找 0,0,1 的简单方法

Question

我正在尝试编写一个简单的函数来查找 0,0,1 是否按顺序出现在列表中。
它应该 return True 或 False.

列表可以包含任意数量的数字。
对于函数 ZeroZeroOne 示例如下：

>> ZeroZeroOne( [0,0,1] )
>> True

>> ZeroZeroOne( [1,0,0] )
>> False

# there are 2s in between but the following does have 0,0,1 occurring and in correct order 
>> ZeroZeroOne( [0,2,2,2,2,0,1] )
>> True

我有这个功能：

def ZeroZeroOne(nums):
      
    FoundIt = False

    #quick return if defo not possible
    if (nums.count(0) < 2) and (nums.count(1) == 0):
        return FoundIt

    n = len(nums)
    for x in range(n-2):
        if nums[x] == 0:
            for i,z in enumerate(nums[(x+1):]):
                if z==0 and z!=1:
                    for j,q in enumerate(nums[(i+1):]):
                        if q==1 and q!=0:
                            FoundIt=True

    return FoundIt

为什么函数 return 对于此列表 [0, 1, 0, 2, 1] 为真？

此外....
对于一个看似简单的问题，这个函数似乎过于复杂了。

在 Python 中是否有解决此问题的正确方法 - canonical 或 Pythonic 方法？
或者这些方法只是基于意见？

Answer 1

我想这就是你想要的:)

def ZeroZeroOne(arr):
    dropped = [x for x in arr if x==0 or x==1]
    slices = [dropped[i:i+3] for i in range(len(dropped)-2)]
    if [0,0,1] in slices: return True
    else: return False

Answer 2

您可以通过单个循环实现此目的 - O(n) 时间复杂度。因为它是针对这个特定案例的。试试下面的代码。

def ZeroZeroOne(nums):
    found_pattern = []
    for num in nums:
        if num == 1:
            found_pattern.append(1)
            if len(found_pattern) == 3:
                return True
            else:
                found_pattern = []
        elif num == 0 and len(found_pattern) < 2:
            found_pattern.append(0)
    return False


print(ZeroZeroOne([0, 0, 1]))
print(ZeroZeroOne([0, 1, 0, 2, 1]))
print(ZeroZeroOne([0, 2, 0, 1]))
print(ZeroZeroOne([0, 0, 0, 1]))
print(ZeroZeroOne([0, 2, 2, 2, 2, 0, 1]))

但我认为如果需要，您也可以概括这一点。如果您想要一种通用方法，您可能需要了解 grep 的工作原理并根据您的用例对其进行修改。

Answer 3

您可以简单地修改 this answer 中的有序子序列测试以获得优雅的解决方案：

def ZeroZeroOne(arr):
    test = iter(a for a in arr if a in (0, 1))
    return all(z in test for z in (0, 0, 1))

我现在知道你不想接受 0, 1 0, 1.

您可以使用 itertools.tee 检查匹配项：

def ZeroZeroOne(arr):
    e = itertools.tee((a for a in arr if a in (0, 1)), 3)
    # move second iterator forward one
    next(e[1])
    # move third iterator forward two
    next(e[2])
    next(e[2])
    return (0, 0, 1) in zip(*e)

在这种情况下使用 tee 的好处是它可以有效地为您维护最后三个元素的滚动缓冲区。您不需要创建一个新的切片或在索引上循环任何类似的东西。

只是为了好玩，这里有一个更通用的纯 python 解决方案。它接受 arr 和 template:

的任何可迭代对象

def contains_template(arr, template):
    template = tuple(template)
    unique = set(template)
    filtered = (a for a in arr if a in unique)
    e = itertools.tee(filtered, len(template))
    for n, it in enumerate(e):
        for _ in range(n):
            next(it)
    return template in zip(*e)

虽然 itertools.tee 是维护滚动缓冲区的好方法，但您可以使用列表实现同样的事情（或更有效地，collections.deque）：

def contains_template(arr, template):
    template = list(template)
    unique = set(template)
    filtered = (a for a in arr if a in unique)
    buffer = [next(filtered) for _ in range(len(template) - 1)]
    buffer.insert(0, None)
    for e in filtered:
        buffer.pop(0)
        buffer.append(e)
        if template == buffer:
            return True
    return False

最后，这是真正简单的解决方案，没有滚动缓冲区：

def contains_template(arr, template):
    template = list(template)
    n = len(template)
    unique = set(template)
    filtered = [a for a in arr if a in unique]
    return any(filtered[i:i + n] == template for i in range(len(filtered) - n))

Answer 4

你也可以用递归函数来做:

def check(seq, liste, i=0, j=0):
    if i >= len(seq):
        return True
    if j >= len(liste):
        return False
    if seq[i] == liste[j]:
        return check(seq, liste, i + 1, j + 1)
    elif liste[j] in seq:
        # look for the last index you can restart from
        for k in range(i - 1, -1, -1):
            if seq[k] == liste[j]:
                if seq[:k] == seq[i - k:i]:
                    ind = k
                    break
        else:
            ind = 0
        return check(seq, liste, ind, j + (not i))
    else:
        return check(seq, liste, i, j + 1)



# seq = [0,0,1] for ZeroZeroOne
print(check([0, 0, 1], [0, 0, 0, 0, 1]))  # True
print(check([0, 0, 1], [0, 200, 0, 0, 101, 1]))  # True
print(check([0, 2, 2, 0, 1], [0, 2, 0, 4, 2, 5, 2, 0, 3, 1]))  # True
print(check([0, 2, 2, 0, 1], [0, 2, 4, 2, 5, 2, 0, 3, 1]))  # False

Answer 5

def ZeroZeroOne(nums):
    filtered_nums = [x for x in nums if x in [0,1]]
    return '*'.join([str(x) for x in [0,0,1]) in '*'.join([str(x) for x in filtered_nums])

在给定列表中按顺序查找 0,0,1 的简单方法

Simple method to find 0,0,1 in that order, within a given List

python

python-3.x

subsequence