括号问题

括号问题用栈一般都能解决

20. 有效的括号

题目描述：

思路：用栈

代码:

import java.util.Stack;
class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new  Stack<Character>();
        for (Character c : s.toCharArray()) {
         if(c=='{'||c=='['||c=='(') {
            //入栈
            stack.push(c);
         }else {
            if(!stack.isEmpty()&&charJT(c)==stack.peek()){
               stack.pop();
            }else {
               return false;
            }
         }
      }
        return stack.isEmpty();
    }
   private Character charJT(Character c) {
       if(c=='}') return '{';
       else if(c==')') return '(';
       else return '[';
   }
}

921. 使括号有效的最少添加

题目描述：

和上题一样的思路，用栈，于是乎：

package 使括号有效的最小添加;
import java.util.Stack;
class Solution {
    public int minAddToMakeValid(String s) {
        int count=0;
 Stack<Character> stack = new  Stack<Character>();
        for (Character c : s.toCharArray()) {
         if(c=='(') {
            //入栈
            stack.push(c);
         }else {
            if(!stack.isEmpty()){
               stack.pop();
            }else {
               count++;;
            }
         }
      }
        return stack.size()+count;
    }
    }

法二：

class Solution {
    public int minAddToMakeValid(String s) {
        // res 记录插入次数
        int res = 0;
        // need 变量记录右括号的需求量
        int need = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                // 对右括号的需求 + 1
                need++;
            }
            if (s.charAt(i) == ')') {
                // 对右括号的需求 - 1
                need--;
                if (need == -1) {
                    need = 0;
                    // 需插入一个左括号
                    res++;
                }
            }
        }
        return res + need;
    }
}

1541. 平衡括号字符串的最少插入次数（没写出来）

题目描述：

难点：内嵌的两个if不好想

代码:

class Solution {
    public int minInsertions(String s) {
        // need 记录需右括号的需求量
        int res = 0, need = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                 // 一个左括号对应两个右括号
                need += 2;
                if (need % 2 == 1) {  //没有下面这段的话 这个案例"()))()))"过不了 
                     // 插入一个右括号
                    res++;
                     // 对右括号的需求减一
                    need--;
                }
            }
            if (s.charAt(i) == ')') {
                need--;
                  // 说明右括号太多了
                if (need == -1) {
                     // 需要插入一个左括号
                    res++;
                     // 同时，对右括号的需求变为 1
                    need = 1;
                }
            }
        }
        return res + need;
    }
}