括号匹配问题在力扣中有好几道，简单的括号匹配问题即一个左括号需要对应一个右括号，判断是否匹配或者需要加入几个左括号或右括号，此时的问题比较简单，当字符串中的字符只有一种类型的括号时，直接用一个变量存储需要的左括号或者右括号数量即可，当有多种括号类型时，可以利用栈保存字符串数组中的字符，根据栈后进先出的特点，检查括号是否匹配。
这个问题的解决比较简单，因为只有一种类型的括号，且一个左括号必须对应一个右括号。使用left变量记录左括号的需求量，使用right变量记录右括号的需求量。当是左括号的时候，right+1；当是右括号的时候，right-1，且当right为-1的时候，表示此时右括号的数量已经比左括号多了，此时left需要+1，且right变为0。
public int minAddToMakeValid(String s) {
int left = 0;
int right = 0;
for(char ch:s.toCharArray()){
if(ch=='(') right++;
else {
right--;
if(need==-1) {
left++;
right=0;
}
}
}
return (left+right);
}
这个题和上一道题目的思想差不多，但是这道题是一个左括号对应两个右括号。仍然使用两个变量left和right分别记录左右括号所需量。遇到右括号的情况和上边一样，当right=-1时说明右括号太多了，需要一个左括号，且因为一个左括号对应两个右括号，此时右括号的需求变成1。当是左括号的时候，如果右括号的需求是奇数，则表示前面差一个右括号，此时用temp来记录此左括号之前差一个右括号，且右括号的总需求-1。（直接用left变量来存储也是可以的，因为left变量只进行了加法，其他时候并没有进行修改）
public int minInsertions(String s) {
int left=0,right=0,temp=0;
for(char ch: s.toCharArray()){
if(ch=='(') {
right += 2;
if(right%2!=0){
temp+=1;
right-=1;
}
}
else {
right--;
if(right==-1){
//此时说明右括号太多了
left++;
right=1;
}
}
}
return left+right+temp;
}
Original: https://www.cnblogs.com/boboray/p/16344007.html
Author: 啵啵ray
Title: 力扣刷题之路-括号匹配问题
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/685592/
转载文章受原作者版权保护。转载请注明原作者出处！