这个题目如果熟悉判断一个括号序列是否合法的方法的话,应该还比较容易想到解法,所以先提一下判断括号序列是否合法的一个方法。
我们将一个括号序列中的左括号当成1,右括号当成-1,然后从左至右依次累加,就可以得到一个整数序列,比如()(()())对应的整数序列就是1 0 1 2 1 2 1 0,如果整数序列中不存在负数,且最后一个数是0,那么这个括号序列就是合法的。
接下来我们考虑此题的解法。由于题目说了答案至少是1,那么也就是说这个序列相比合法的括号序列而言只是少了一个括号,至于少的是左括号还是右括号,我们根据括号的数量是很容易判断出来的。
不妨先讨论缺少一个左括号的情况。比如(()))()这个序列,对应的整数序列就是1 2 1 0 -1 0 -1。接着我们考虑在哪里插入一个左括号可以使其变成一个合法的括号序列,其实也就是考虑在哪里插入一个左括号后使这个整数序列所有的值都是非负的。考虑 到插入一个左括号的效果是插入一个整数,并且让插入位置右边的所有整数都+1,因此左括号可以插入的最右的位置应该是最左的-1的左边,同时这个位置左边 的任何一个位置都可以作为插入位置。这样我们只要遍历一下这个整数序列找到第一个-1出现的位置就可以知道有多少个位置可以插入左括号了。
至于缺少一个右括号的情况,比如()((())这个序列,我们可以将其翻转一下,就变成了(()))(),这样就又变成了缺少一个左括号的情况了。
我们将一个括号序列中的左括号当成1,右括号当成-1,然后从左至右依次累加,就可以得到一个整数序列,比如()(()())对应的整数序列就是1 0 1 2 1 2 1 0,如果整数序列中不存在负数,且最后一个数是0,那么这个括号序列就是合法的。
接下来我们考虑此题的解法。由于题目说了答案至少是1,那么也就是说这个序列相比合法的括号序列而言只是少了一个括号,至于少的是左括号还是右括号,我们根据括号的数量是很容易判断出来的。
不妨先讨论缺少一个左括号的情况。比如(()))()这个序列,对应的整数序列就是1 2 1 0 -1 0 -1。接着我们考虑在哪里插入一个左括号可以使其变成一个合法的括号序列,其实也就是考虑在哪里插入一个左括号后使这个整数序列所有的值都是非负的。考虑 到插入一个左括号的效果是插入一个整数,并且让插入位置右边的所有整数都+1,因此左括号可以插入的最右的位置应该是最左的-1的左边,同时这个位置左边 的任何一个位置都可以作为插入位置。这样我们只要遍历一下这个整数序列找到第一个-1出现的位置就可以知道有多少个位置可以插入左括号了。
至于缺少一个右括号的情况,比如()((())这个序列,我们可以将其翻转一下,就变成了(()))(),这样就又变成了缺少一个左括号的情况了。