在某算法比赛上看到的惊为天人的算法解决计算完美闭合括号数量问题（（）（）？？））——java

算法比赛上看到的惊为天人的算法解决计算完美闭合括号数量问题（（）（）？？））——java"/>

在某算法比赛上看到的惊为天人的算法解决计算完美闭合括号数量问题（（）（）？？））——java

原题是这样的：

给定字符串序列 （）（）？？（？

判断 这里面包含几个完美闭合的（）。？可以代表）或者（。

e.g.  上述序列的完美闭合（） 字串是：

（）

（）

？？

（？

（）（）

（）？？

？？（？

（）（）？？

（）？？（？

（）（）？？（？

答案是10， 因为有十种可以完美闭合的字串。

注： （？？） 可以表示为 （）（）和（（）） 都是完美闭合的括号。但是计数的时候算一次，因为要找多少组数量，而不是多少种组合。

对于这道题，我第一思路是，用一个char的数组，通过闭合消解的方式（把可以闭合的答案用‘0’来代替），最后判断char数组中是否全部为0，这样解决的算法非常难以平衡一些特殊情况，可能需要用递归方式判断各种可能性，而且算法效率也不高。

在众多码农中，有一个人写的答案让我叹为观止。

他的解法是这道题复杂度的最优算法 On^2。（必须两个for循环来遍历所有组合）

而他的判断方法如下：

假设str就是我们得到的序列

char[] cha = str.toCharArray();
int count = 0;
for(int i = 0; i< cha.length; i++){int x = 0;int y = 0;for (int j = i; j<cha.length; j++){if(cha[j]==')'){x--;y--;}else{if(cha[j]=='('){x++;y++;}else{x--;y++;}if(x<0) x=0;if(y<0) break;if(x=0&& (j-i)%2==1) count++;}
}

简直牛匹的令人发指。。。。我看过后边所有用java提交的18个答案，这个是最简洁，时间复杂度最低，最牛逼的一个解法了。

解释：

这个算法的y，相当于最大限度有多少个前缀——（，来记录整个字串的‘ ）’是否属于无法闭合的情况（比如‘ )(????() ’就是无法闭合的情况)，如果小于0，就代表任由后面跟着多少个符号，以这个字串开头的后面所有字串都不行。（非花括号的倒数第二行）

而x，用来记录这个字串的弹性，也可以称为最小限度有多少个待闭合的‘（ ’。如果有‘（ ’的时候才加1，否则其他情况都减1，对于有问好的情况，减1之后，在下边三行中的第一行，会给他赋值回0（对于‘ ）’出现在无法闭合位的情况，有y在记录）

当x = 0的时候，就证明这个字串是可能闭合的情况，用这个条件&&上后边  j-i对2取模 是否等于1的条件（等于1 证明这个字串长度是双数）来判断，如果在字串长度是双数的条件下（闭合所要符号数量的必要不充分条件）如果这个数值为0，就说明经过一系列加加减减，符号‘ ）’ 可以被完全的抵消掉。这个时候，此字串为完美闭合括号串，计数自加1。

可能是我道行太浅，少见多怪。

我是真的觉得。。山外有山……