1

给定括号字符串，我们必须做两种操作：

  1. flip- 将第 i 个括号更改为相反的括号（left->right , right->left）
  2. 检查字符串是否为平衡括号表达式

字符串的长度最大为 30000。

要执行的操作数最多为 100000。

应该使用什么样的数据结构来解决这类问题？

Segment Tree 是一种合适的数据结构吗？

如果是，应该如何使用它？

例子

字符串 = ()((

操作次数=4

  1. 翻转 4 {新字符串是 ()()}
  2. 检查{字符串是否平衡}
  3. 翻转 2{新字符串变为 ((()}
  4. 检查{字符串不平衡}
4

2 回答 2

1

让每一个(都是一个+1，每一个)都是一个-1。然后，如果整个字符串的总和为零并且每个范围的总和[0, k]为非负数，则括号字符串是平衡的。

让我们为 substring和[i,j]定义两个函数。是显而易见的，并被定义为从所有位置的最小值。summinsummin(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's 和-1's，而根是整个范围[0, N-1]。对于我们保留的每个节点min和sum。

查询余额很明显：我们检查root.min >= 0and 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,console

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 回答