1. 判斷合法括號串 letcode 20

   描述：給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判斷字符串是否有效。

   有效字符串需滿足：

   • 左括號必須用相同類型的右括號閉合。
   • 左括號必須以正確的順序閉合。

   示例

   1. 輸入：s = "()"
      輸出：true
   2. 輸入：s = "()[]{}"
      輸出：true
   3. 輸入：s = "(]"
      輸出：false
   

   思路：采用棧先入后出，如果遇到左括號入棧，遇到右括號時對應(yīng)棧頂?shù)淖罄ㄌ栃枰鰲＃枰闅v完所有，stack同樣為空。

   算法：

private final static Map<Character, Character> map = new HashMap<Character, Character>() {
        {
            put(')', '(');
            put(']', '[');
            put('}', '{');
        }
    };
    public static boolean isValid(String s) {
        int n = s.length();
        if (n % 2 == 1) { // 奇數(shù)不是有效
            return false;
        }
        Deque<Character> stack = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (map.containsKey(c)) {
              // 有效的字符必定棧頂當(dāng)前循環(huán)的字符成對。
                if (stack.isEmpty() || !stack.peek().equals(map.get(c))) {  
                    return false;
                }
                stack.pop(); // 出棧
            } else {
                stack.push(c);
            }
        }
        return stack.isEmpty();
    }

2. 使括號有效的最小填充 letcode 921

   描述：給定一個由 '(' 和 ')' 括號組成的字符串 S，我們需要添加最少的括號（ '(' 或是 ')'，可以在任何位置），以使得到的括號字符串有效。

   從形式上講，只有滿足下面幾點之一，括號字符串才是有效的：

   • 它是一個空字符串
   • 它可以被寫成 AB （A 與 B 連接）, 其中 A 和 B 都是有效字符串，
   • 它可以被寫作 (A)，其中 A 是有效字符串。 給定一個括號字符串，返回為使結(jié)果字符串有效而必須添加的最少括號數(shù)。

   示例：

   1. 輸入："())"
      輸出：1
   2. 輸入："((("
      輸出：3
   3. 輸入："()))(("
      輸出：4
   

   思路：定義一個棧，用來存儲"(" , 遍歷字符串s，當(dāng)遇到"(" 則進棧，如果是")"則判斷當(dāng)前棧是否為空，不為空，則表示存在與當(dāng)前右括號匹配的左括號，匹配后棧頂出棧。若為空，則表示沒有能與"("匹配的，此時需要進行記錄count。
   遍歷完字符串s，找到未匹配到")"的數(shù)量；如果棧不為空，說明有未匹配到"(",需要返回棧大小,最后兩數(shù)相加就是結(jié)果。

public static int minAddToMakeValid(String s) {
    int n = s.length();
    int count = 0;
    Stack<Character> stack = new Stack<>();
    for (int i = 0; i < n; i++) {
        if (s.charAt(i) == '(') {
            stack.push(s.charAt(i));
        }
        if (s.charAt(i) == ')') {
            if (!stack.isEmpty()) {
                stack.pop();
            } else {
                count++;
            }

        }
    }
    return stack.isEmpty() ? count : stack.size() + count;
}