括号相关的应用

括号相关的应用

力扣上，括号相关的题目如下：

序号	题目	难度
1	20. 有效的括号	简单
2	1541. 平衡括号字符串的最少插入次数	中等
3	921. 使括号有效的最少添加	中等

1. Leetocde 20. 有效的括号

1.1. 解题思路

维护一个栈 \(stack\)，顺序遍历字符串，对于遇到的每一个字符：

如果它是一个左括号，就将其入栈；
如果它是一个右括号，就弹出栈顶的元素，并判断是否与之匹配，若不匹配，则返回 \(false\)。

遍历完字符串后，如果栈里面还有剩余元素，则返回 \(false\)，否则，就返回 \(true\)。

1.2. 代码实现

class Solution {

    public boolean isValid(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        Map<Character, Character> map = new HashMap<>();

        map.put(')', '(');
        map.put(']', '[');
        map.put('}', '{');

        for (int i = 0;i< s.length();i++) {
            // 遇到左括号就从栈里面弹出一个元素，并判断是否是对应的右括号
            if (map.containsKey(s.charAt(i))) {
                if (stack.isEmpty() || stack.peek() != map.get(s.charAt(i))) {
                    return false;
                }
                stack.pop();
            } else {
                // 遇到左括号就压栈
                stack.push(s.charAt(i));
            }
        }
        // 如果站里面还有剩余元素，就返回失败
        return stack.isEmpty();
    }
}

2. Leetocde 1541. 平衡括号字符串的最少插入次数

2.1. 解题思路

我们维护两个变量，来记录所需插入的括号数量：

所需要插入的括号：\(needInsert\)，包含插入左括号和插入右括号；
维持平衡所需要的右括号数量：\(needRight\)。

我们遍历字符串 \(S\) ，对于遇到的每一字符：

如果当前字符是一个左括号，就将 \(needRight\) 加 \(2\)；

此时，如果对右括号的需求数变为奇数，说明它的左侧有一个不配对的右括号，那么，就需要插入一个右括号来保持平衡，这样，对右括号的需求就减 \(1\)。

因此，\(needInsert\) 需要加 \(1\)，同时，将 \(needRight\) 减 \(1\)。
如果当前字符是一个右括号，就将 \(needRight\) 减 \(1\)；

此时，如果对右括号的需求减少到 \(-1\)，说明它的左侧右括号较多，就需要插入一个左括号来保持平衡。

因此，\(needInsert\) 需要加 \(1\)，同时，将\(needRight\) 加 \(2\)。

2.2. 代码实现

class Solution {
    public int minInsertions(String s) {
        int needInsert = 0;
        int needRight = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                // 对右括号的需求加2
                needRight += 2;
                // 遇到左括号的时候，右括号的需求为奇数，说明当前字符的左侧有一个不配对的右括号
                if (needRight % 2 == 1) {
                    // 需要插入一个右括号
                    needInsert++;
                    // 对右括号的需求减1
                    needRight--;
                }
            } else {
                needRight--;
                // 右括号减到-1，说明需要插入一个左括号与之匹配
                if (needRight == -1) {
                    // 需要插入一个左括号
                    needInsert++;
                    // 对右括号的需求加2
                    needRight += 2;
                }

            }
        }
        return needRight + needInsert;
    }
}

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

3.1. 解题思路

3.1.1. 方法一：栈

使用一个栈 \(stack\) 记录所有的左括号，当遇到一个右括号就弹出栈里的左括号，如果栈为空，就将需要插入的左括号数量加 \(1\)。

遍历完整个字符串后，如果栈里还剩余有左括号，那么，也需要对应数量的右括号。

3.1.2. 方法二：模拟

我们维护两个变量，来记录所需添加的括号数量：

用 needLeftCount 表示需要插入的左括号数量；
用 right 表示对的右括号需求。

我们以左括号为基准，遍历字符串 \(S\)从左右往右遍历字符串：

如果遇到一个左括号，就对 right 加 1，
如果遇到一个右括号，就对 right 减 1，如果 right 小于零了，表示右括号太多了，需要新插入一个左括号来平衡一下，此时，将 needLeftCount 加 1。

因此，需要插入的括号数量，就是待插入的左括号与右括号的需求之和。

3.2. 代码实现

方法一

class Solution {
    public int minAddToMakeValid(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(s.charAt(i));
            } else {
                if (!stack.isEmpty()) {
                    stack.pop();
                } else {
                    count++;
                }
            }
        }
        return count + stack.size();
    }
}

方法二

class Solution {
    public int minAddToMakeValid(String s) {
        // 需要插入左括号的数量
        int needLeftCount = 0;
        // 记录遍历过程中，需要的右括号数量
        int right = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                // 遇到一个左括号，就需要一个右括号
                right++;
            } else {
                // 遇到一个右括号，所需要的右括号数量就减一
                right--;
                // 右括号的需求减少到零，说明右括号太多了，就插入一个左括号
                if (right == -1) {
                    // 插入一个左括号
                    needLeftCount++;
                    // 将右括号的需求重置为零
                    right = 0;
                }
            }
        }
        // 如果遍历完了之后，还有右括号，需要插入等量的左括号
        return needLeftCount + right;
    }
}