1

最初に、「バランスの取れた」括弧の文字列を、すべての「(」に対して、その「(」の後のどこかに一意の一致する「)」が 1 つあるような文字列として定義します。

たとえば、次の文字列はすべて「バランス」です。

()

()()

(())()

これらはそうではありませんが：

)(

())(

括弧の文字列 (長さ <= 1,000,000) と範囲クエリのリストが与えられた場合、<= 100,000 の各クエリの各範囲内でバランスの取れた括弧の最大長を見つけます (範囲に 0 インデックスを使用)

元：

()))()(())

範囲: [0,3] -> 最長 = 2 : "()"

範囲: [0, 4] -> 最長 = 2 : "()"

範囲: [5, 9] -> 最長 = 4: "(())"

私の考えは次のとおりです。

まず、スタックを維持することで、文字列が「バランスが取れている」かどうかを判断できます。「(」に遭遇した場合はスタックにプッシュし、「)」に遭遇した場合はスタックからポップアウトします。末尾に「(」が残っている場合、文字列は「バランスが取れていません」。

ただし、すべての範囲でこれを繰り返すのは O(N*M) の複雑さであり、入力のサイズに対して長すぎます。

ここで、範囲クエリに注目すると、プレフィックスの合計とバイナリ インデックス ツリー/セグメント ツリーが思い浮かびます。プレフィックスの合計範囲全体を配列に事前計算できる場合は、差をとることで、より小さなプレフィックスの合計を見つけることができます。これにより、大きな複雑さが得られます。

+1 の値を '(' に、-1 の値を ')' に割り当てて、'(' に遭遇するたびに累積合計に 1 を追加し、') に遭遇したときにその方法を考えました。 'あなたは減少します。したがって、次のような有効な「バランスのとれた」文字列の))()場合: -1 -2 -1 -2.

しかし、私の質問は、これをどのように使用して「バランスが取れている」かどうかを判断するのですか? また、特定の間隔内で最大の「バランスの取れた」文字列を見つける必要があるため、特定の部分文字列が「バランスが取れている」かどうかを確認する機能を使用して、その特定の間隔内で最大の文字列を見つけるにはどうすればよいでしょうか。

4

1 に答える 1

1

序章

位置 のすべての開始ブラケットについて、位置xで一致する終了ブラケットを見つけて、からyまでの部分x文字列 , がバランスのとれた最大の部分文字列になるようにします。閉じ括弧で始まる部分文字列には関心がありません。これは、そこから始まる文字列は、最初の後続の開き括弧で始まる文字列と同じくらい良いからです。yS[x, y]

最も重要な観察事項は次のとおりです。 のある位置で始まるすべての開き括弧x'に対してx < x' < y、対応する閉じ括弧は のy'場所にありx' < y' < yます。これは、 のすべての接頭辞にS[x, y]は、少なくとも閉じ括弧と同じ数の開き括弧がS[x', y]含まれているため、多くても閉じ括弧と同じ数の開き括弧が含まれているためです。

この知識を使用して、各ノードが最大のバランスの取れた部分文字列を表すツリーを構築できるため、開始位置と終了位置があります。このノードの子は、この最上位部分文字列のバランスの取れた部分文字列を表します。左括弧と一致しない右括弧が存在する可能性があるため、単一のルートは存在しないため、実際にはフォレスト1があります。

写真は千の言葉以上を語ります。次の例を検討してください。

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
) ) ( ( ) ( ( ) ) )  )  (  (  )  )

これにより、次のツリーが得られます。

   (2, 9)       (11, 14)
   /     \          |
(3, 4) (5, 8)   (12, 13)
          |
       (6, 7)

ツリーの構築

ツリーの作成は非常に簡単です。空のスタックから始めます。位置で開き括弧に遭遇したときはいつでもx：

  • ノードを作成する(x, ..)
  • 現在スタックの一番上にあるノードの子としてそのノードを追加します (存在する場合、そうでない場合、これはルートです)。
  • 新しいノードをスタックにプッシュする

位置で閉じ括弧に遭遇したときはいつでもy：

  • スタックの一番上にあるノードをポップし(x, ..)ます (そのようなノードがない場合、これは一致しない閉じ括弧です: 無視します)
  • 終了インデックスを設定します。(x, y)

文字列を 1 回スキャンし、各ステップで一定数の操作を実行するため、構造の構築は線形時間で行われます。

ツリーのクエリ

次に、クエリを実行する必要があります。クエリ が与えられた場合、に完全に含まれる(p, q)最大のノード (サイズは ) を見つける必要があります。2 つのバイナリ検索を実行して、ツリー内の開始位置と終了位置を見つけるだけです。(位置の文字が閉じ括弧の場合、最小の を探します。同様に、位置の文字が開き括弧の場合、最大の を探します。)とへのパスに沿って最大の間隔を見つけます。y - x + 1(p, q)px > pqy < pxy

ツリーのバランスが取れている場合、各クエリにはO(lg n)時間がかかります。最悪の場合、文字列はすべて左大括弧で始まり、すべて右大括弧で終わります。その後、クエリには最大で線形時間がかかる場合があります。

1これは、一致しない閉じ括弧と同じ数の開き括弧を文字列の前に追加することで解決できます。

于 2014-10-28T07:50:49.770 に答える