计算自上次头部以来的尾巴数量

Question

考虑一系列抛硬币：1,0,0,1,0,1，其中尾部= 0，正面= 1。

所需的输出是序列：0， 1， 2， 0， 1， 0

输出序列的每个元素都会计算自最后一个头部以来的尾数。

我尝试了一种幼稚的方法：

def timer(seq):
if seq[0] == 1: time = [0]
if seq[0] == 0: time = [1]
for x in seq[1:]:
if x == 0: time.append(time[-1] + 1)
if x == 1: time.append(0)
return time

问题：有没有更好的方法？

Answer 1

使用 NumPy：

import numpy as np 
seq = np.array([1,0,0,1,0,1,0,0,0,0,1,0])
arr = np.arange(len(seq))
result = arr - np.maximum.accumulate(arr * seq)
print(result)

收益 率

[0 1 2 0 1 0 1 2 3 4 0 1]

---

为什么arr - np.maximum.accumulate(arr * seq)？所需的输出似乎与整数的简单级数有关：

arr = np.arange(len(seq))

所以自然的问题是，如果seq = np.array([1, 0, 0, 1, 0, 1])和预期的结果是expected = np.array([0, 1, 2, 0, 1, 0])，那么x的价值是什么？

arr + x = expected

因为

In [220]: expected - arr
Out[220]: array([ 0,  0,  0, -3, -3, -5])

看起来x应该是arr * seq的累积最大值：

In [234]: arr * seq
Out[234]: array([0, 0, 0, 3, 0, 5])
In [235]: np.maximum.accumulate(arr * seq)
Out[235]: array([0, 0, 0, 3, 3, 5])

Answer 2

第 1 步 ：反转l：

In [311]: l = [1, 0, 0, 1, 0, 1]
In [312]: out = [int(not i) for i in l]; out
Out[312]: [0, 1, 1, 0, 1, 0]

第 2 步：列出 comp;如果当前值为 1，则将先前的值添加到当前值。

In [319]: [out[0]] + [x + y if y else y for x, y in zip(out[:-1], out[1:])]
Out[319]: [0, 1, 2, 0, 1, 0]

这通过压缩相邻元素来摆脱多风的ifs。

Answer 3

使用itertools.accumulate：

>>> a = [1, 0, 0, 1, 0, 1]
>>> b = [1 - x for x in a]
>>> list(accumulate(b, lambda total,e: total+1 if e==1 else 0))
[0, 1, 2, 0, 1, 0]

accumulate仅在 Python 3 中定义。不过，如果你想在 Python 2 中使用它，上面的文档中有等效的 Python 代码。

需要反转a因为accumulate返回的第一个元素是第一个列表元素，独立于累加器函数：

>>> list(accumulate(a, lambda total,e: 0))
[1, 0, 0, 0, 0, 0]

Answer 4

所需的输出是与输入长度相同的数组，并且没有一个值等于输入。因此，算法必须至少为 O(n( 才能形成新的输出数组。此外，对于此特定问题，您还需要扫描输入数组的所有值。所有这些操作都是 O(n(，它不会变得更有效率。常量可能会有所不同，但您的方法已经在 O(n( 中，并且不会更低。

Answer 5

使用reduce：

time = reduce(lambda l, r: l + [(l[-1]+1)*(not r)], seq, [0])[1:]

Answer 6

我尝试在以下代码中清楚，并且在使用显式累加器方面与原始代码不同。

>>> s = [1,0,0,1,0,1,0,0,0,0,1,0]
>>> def zero_run_length_or_zero(seq):
"Return the run length of zeroes so far in the sequnece or zero"
accumulator, answer = 0, []
for item in seq:
accumulator = 0 if item == 1 else accumulator + 1
answer.append(accumulator)
return answer
>>> zero_run_length_or_zero(s)
[0, 1, 2, 0, 1, 0, 1, 2, 3, 4, 0, 1]
>>>