从一串硬币抛掷中计算出少数反面的子串

Question

给定一个正面和反面的序列，我想计算正面数量不少于反面数量的重要子串的数量。我想在 O(NlogN) 时间内实现。

示例输入： [ 'H', 'T', 'H', 'T', 'T', 'H' ]

示例输出：

解释：

{H} {H} {H}
{H, T} {T, H} {H, T} {T, H}
{H, T, H} 
{H, T, H, T} 
{H, T, T, H} 
{H, T, H, T, T, H}

我相信我当前的算法是 O(N^2)。我递归地解决了这个问题，迭代了两端切片的硬币列表。

这是我目前的算法。如何实现 O(NLogN) 时间？

def count_sequences( data ):
    print go(range(0,len(data)),data)
seen = set()
def go(rang,data):
    if tuple(rang) in seen: return 0
    seen.add(tuple(rang))
    h = 0
    summ = 0
    if len(rang)==0: return 0
    for i in rang:
        if data[i] == 'H': h += 1
        summ += go(rang[1:],data)
        summ += go(rang[:-1],data)
    if len(rang) == 1: 
        if h ==1: return 1
        else: return 0
    if h > (len(rang)-1)/2 : 
        return 1 + summ
    else: return summ

Answer 1

这是一个复杂度为 O(n) 的解决方案。

想象一下，您的数组中没有 H 和 T，而是 1 和 -1。这将问题简化为计算非负和子数组的数量。这是一个已知问题，可以通过计算累积数组并找到反转次数来解决。

这可以在 O(n^2) 中天真地计算，搜索对 i < j，其中 A[i]>A[j]。可以使用合并排序变体将其优化为 O(n log n)。

但特别是在这种情况下，数组中的值最多可以为 n，并且连续值的绝对差正好为 1，因此我们可以创建一个算法，在 O(n) 中即时计算这些反转:

def solve(A):
    count = 0
    accum = 0
    total = 0
    seen = {0: 1}

    for i, element in enumerate(A):
        if element == 'H': 
            count += 1
            accum -= seen.get(count, 0)
        else:
            accum += seen.get(count, 0)
            count -= 1

        seen[count] = seen.get(count, 0) + 1
        total += (i + 1 - accum)

    return total

print solve([ 'H', 'T', 'H', 'T', 'T', 'H' ])

print solve([ 'T', 'H', 'H', 'H', 'T' ])

该算法主要基于one I've read here。

从一串硬币抛掷中计算出少数反面的子串

Count substrings with a minority of tails from a string of coin tosses

python

algorithm