동전 토큰 문자열에서 꼬리가 소수 인 부분 문자열

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이 배열에 있다고 상상해보십시오. 이것은 음이 아닌 sum subarray의 수를 계산하는 문제를 줄입니다. 이것은 축적 된 배열을 계산하고 역전의 수를 찾는 것으로 해결할 수있는 알려진 문제입니다.

O (n^2)에서 A [i]> A [j] 인 쌍을 검색하여 naively 계산할 수 있습니다. 병합 정렬 변형을 사용하여 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을 기반으로합니다.