数一数掷硬币串中有少数尾巴的子串

Question

给定一系列的头和尾，我想计算有效子串的个数，其中头的个数不小于尾的个数。我想在O（NlogN）时间内实现这一点。你知道吗

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

输出示例：

11

说明：

{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 logn）。你知道吗

但在这种情况下，数组中的值最多可以是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。你知道吗