检查列表是否是有效的块序列。
检查列表是否是有效的块序列。
我想检查一个列表是否是有效的块序列,其中每个块都以某个值开头,并以下一个相同值的出现结束。例如,下面是一个由三个块组成的有效序列:
lst = [2, 7, 1, 8, 2, 8, 1, 8, 2, 8, 4, 5, 9, 0, 4, 5, 2]
\___________/ \_____/ \_______________________/
而这个是无效的:
lst = [2, 7, 1, 8, 2, 8, 1, 8, 2, 8, 4, 5, 9, 0, 4]
\___________/ \_____/ \_____ ... 缺少结束块的2
我有一个解决方案,但不好。你看到更好的方法了吗?
def is_valid(lst):
while lst:
start = lst.pop(0)
if start not in lst:
return False
while lst[0] != start:
lst.pop(0)
lst.remove(start)
return True
# 测试,应该输出: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', 'N', 'O', 'A', 'I', 'L', 'L', 'T', 'R', 'X', 'I', 'I', 'N', 'X', 'F', 'T']))
print(is_valid(['T', 'I', 'N', 'I', 'X', 'R', 'O', 'F', 'T', 'I', 'N', 'I', 'X', 'L', 'L', 'A']))
print(is_valid([]))
问题的出现原因:
从给定的内容中,我们可以看到问题的出现原因是要判断一个列表是否是有效的片段序列。具体而言,我们需要检查列表中的每个元素是否在列表的其他位置也存在。
解决方法:
作者提供了多种解决方法,每种方法都使用了迭代器来遍历列表,并使用不同的方式检查元素是否存在于其他位置。
第一种方法是使用next
函数和生成器表达式来搜索与当前元素匹配的下一个元素。这种方法需要定义一个哨兵obj = object()
来解决None
作为列表元素的问题。
第二种方法是使用any
函数代替next
函数,并解决了默认元素的问题。any
函数会消耗迭代器,直到找到匹配的元素。
第三种方法在第二种方法的基础上进一步简化,使用all
函数代替外部的for
循环。
最后一种方法进一步简化了第三种方法,使用x in it
来判断元素是否存在于迭代器中。
还有各种解决方法的性能比较,结果表明这些方法在不同的测试用例下具有不同的效率,但都是O(n)的时间复杂度。在长列表的情况下,使用index
函数的解决方法是最快的,而使用x in it
的解决方法也表现不错。在短测试列表的情况下,使用一个迭代器和for-for-else
以及for-in
的解决方法是最快的。
通过本文的讨论,我们了解到了问题的出现原因以及多种解决方法。这些解决方法都使用了迭代器来遍历列表,并通过不同的方式判断元素是否存在于其他位置。作者还对这些解决方法进行了性能比较,展示了它们在不同情况下的效率表现。无论哪种方法,都保证了每个元素只被访问一次,原始列表不会被修改,几乎不需要额外的空间,并且易于阅读和理解。
检查一个列表是否是有效的块序列的问题的出现是因为需要判断一个给定的列表是否满足特定的条件。解决这个问题的方法有两种,一种是使用迭代器实现的方法,另一种是使用itertools库实现的方法。
首先,第一种方法使用了迭代器来实现。每次外部循环的迭代对应一个块(chunk)。当我们在这里没有元素时,我们结束了在块边界处的序列,并且可以返回True。否则,我们通过迭代器循环直到找到一个匹配的元素。如果我们用完了元素(没有使用break的for循环进入了else),我们返回False。
第二种方法使用了itertools库。我不会优先选择它,主要是因为使用了带有哨兵的next函数的奇怪用法。这种方法与上述的解决方案类似,但是可以使用另一个外部的for循环来代替try/while/next/except。
这两种方法都是有效的解决方案,选择哪种方法取决于个人的偏好和需求。第一种方法更容易理解和阅读,但是第二种方法使用了itertools库,可能在某些情况下更加方便。所以,最终选择哪种方法应该根据具体情况来决定。
题目:检查列表是否是有效的块序列
原因:在代码中使用pop(0)对列表进行突变是昂贵且不必要的。而且,对于大块的情况下,可以使用index方法,这可能会更快。
解决方法:可以使用index方法来检查块序列的有效性。下面是一个示例代码:
def is_valid(lst): i = 0 n = len(list) while i < n: try: i = lst.index(lst[i], i + 1) + 1 except: return False return True
虽然对于大型输入列表来说,调用index方法同样昂贵,因为需要重复扫描输入列表的内容,但是它们使用的是编译后的代码进行扫描,与在Python代码中进行迭代的循环相比,执行时间更短。因此,当块的大小相对较大时,执行时间会更短。
在这个解决方案中,index方法并没有从列表的开头开始索引,而是从i + 1开始索引。
如果想要进行性能比较,可以使用随机包含10万个个位数的列表进行基准测试。可以在以下链接中找到一个基准测试的示例:[repl.it](https://replit.com//httpsstackoverflowcoma690929425459839)。