1

かっこの文字列が与えられた場合、2 種類の操作を行う必要があります。

  1. 反転 - i 番目の括弧を反対の括弧に変更します (left->right 、 right->left)
  2. チェック - 文字列がバランスの取れた括弧式であるかどうか

文字列の長さは最大 30000 です。

実行する操作の数は最大 100000 です。

この種の問題を解決するには、どのようなデータ構造を使用する必要がありますか?

セグメント ツリーは適切なデータ構造ですか?

はいの場合、どのように使用する必要がありますか？

例

文字列 = ()((

操作数=4

  1. フリップ 4 {新しい文字列は ()()}
  2. check {文字列はバランスが取れています}
  3. フリップ 2{新しい文字列は ((()} になります)
  4. check{文字列のバランスが取れていません}
4

2 に答える 2

1

すべて(を a+1とし、すべて)を aとし-1ます。次に、文字列全体の合計がゼロで、すべての範囲の合計が[0, k]負でない場合、括弧の文字列はバランスが取れています。

[i,j]substringとsumの2 つの関数を定義しましょうmin。sumは明らかであり、どこmin(i,j)からでも最小値として定義されています。sum(i,k)k <= j

そう

sum(i,k) = sum(i,j) + sum(j+1, k)

と

min(i,k) = MIN( min(i,j), sum(i,j) + min(j + 1, k) )

+1これで、葉がと-1であり、ルートが範囲全体である二分木を構築できます[0, N-1]。保持するすべてのノードについて、minとsum.

バランスのクエリは明らかです。root.min >= 0とroot.sum == 0、そうをチェックしO(1)ます。

フリップは、リーフ ノードを更新し、変更をルートに伝達することによって行われます。以上のlog(N)+1ノードが更新されることはなく、すべての更新はO(1)ですO(logN)。

于 2016-08-08T13:21:01.613 に答える
0

弦のバランスが取れているかチェックする機能は簡単に作れます。文字列をステップ実行し、"(" 文字に一致する場合はゼロで初期化された値をインクリメントし、")" に一致する場合はデクリメントします。結果が 0 で、実行中に 0 を下回らなかった場合、文字列はバランスが取れています。文字列の n 番目の位置で括弧を反転するのは簡単です。

これは、ループ内の文字列のランダムな文字を反転し、各反転後に結果の文字列の有効性をチェックする JavaScript での簡単な実装です。

http://jsbin.com/vagalijoca/edit?html、コンソール

function checkbalanceness(str){
  var res = 0;
  for(i=0;i<str.length;i++) {
    str[i]=="(" ? res++ : res--;
    if (res < 0) break;
  }
  return res == 0;
}

function flipp(str, i){
  if (i >= str.length) return str;
  return str[i]=="(" ?
    str.substr(0,i) + ")" + str.substr(i+1) :
    str.substr(0,i) + "(" + str.substr(i+1) ;
}

//initial string
var curr = "()(())";
//operations to be executed
var ops = 40;

console.log('initial string: ' + curr + ' ' + checkbalanceness(curr));
console.log('operations: ' + ops);
console.log('start');
var ii;
var chartoflip;
for(ii=0;ii<ops;ii+=2){
  chartoflip = (ii/2)%(curr.length);
  curr = flipp(curr, chartoflip);
  console.log((ii) + ' - flip char ' + chartoflip + ': ' + curr);
  console.log((ii+1) + ' - checking ' + curr + ' ' + checkbalanceness(curr));
}
console.log('end');
于 2016-08-08T12:15:55.397 に答える