秒杀所有括号类问题

20. 有效的括号

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

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

有效的括号

题目详情可见 有效的括号

思路：利用栈来辅助判断。栈中仅存放左括号，当遇到右括号时，判断栈顶元素是否匹配。需要注意栈空的情况

xxxxxxxxxx
public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();
    for (char c : s.toCharArray()) {
        // 左括号入栈
        if (c == '(' || c == '{' || c == '[') stack.push(c);
        // 右括号
        else {
            // 栈不空且匹配，弹出栈顶元素
            if (!stack.isEmpty() && getLeft(c) == stack.peek()) stack.pop();
            else return false;
        }
    }
    return stack.isEmpty();
}
// 根据右括号返回对应的左括号
private char getLeft(char c) {
    if (c == ')') return '(';
    if (c == '}') return '{';
    return '[';
}

使括号有效的最少添加

题目详情可见 使括号有效的最少添加

判断合法性的策略：对于一个字符串s来说，s的任意一个子串[0...i]中，(的数量肯定大于或等于)的数量

思路：如果left小于right，我们就补一个左括号

xxxxxxxxxx
public int minAddToMakeValid(String s) {
    int left = 0, right = 0;
    int ans = 0;
    for (char c : s.toCharArray()) {
        if (c == '(') left++;
        else right++;
        // 注意：此时左括号的数量需要加我们补上的数量
        if (left + ans < right) ans++;
    }
    // 如果最后左右括号的数量不一致，说明右括号少了，需要补上
    if (left + ans != right) ans += (left + ans - right);
    return ans;
}

更新时间：2022-08-10 00:16:58

果然相同的题目，不同时间写，会有不一样的写法，根据自己的积累，解法会越来越精简，特此记录一波！！

xxxxxxxxxx
public int minAddToMakeValid(String s) {
    // 记录左右括号合并成一个变量 count
    int ans = 0, count = 0;
    for (char c : s.toCharArray()) {
        if (c == '(') count++;
        else count--;
        if (count < 0) {
            ans -= count;
            count = 0;
        }
    }
    ans += count;
    return ans;
}

平衡括号字符串的最少插入次数

题目详情可见 平衡括号字符串的最少插入次数

思路和上一题差不多，但是需要注意，))必须连续才有效

xxxxxxxxxx
public int minInsertions(String s) {
    // 记录左右括号的数量
    int left = 0, right = 0;
    // 记录需要添加的左右括号的数量
    int leftAdd = 0,  rightAdd = 0;
    int i = 0;
    while (i < s.length()) {
        // 一次性遍历完连续的 (
        while (i < s.length() && s.charAt(i) == '(') {
            left++;
            i++;
        }
        // 一次性遍历完连续的 )
        while (i < s.length() && s.charAt(i) == ')') {
            right++;
            i++;
        }
        // 如果原有的和新加的一共是奇数，那么就需要 +1 凑成偶数，因为 )) 必须连在一起
        if ((right + rightAdd) % 2 == 1) rightAdd++;
        // 计算需要添加的左括号
        int need = (right + rightAdd) / 2 - (left + leftAdd);
        leftAdd += (need > 0 ? need : 0);
    }
    // 补齐缺少的右括号
    if ((left + leftAdd) * 2 != right + rightAdd) rightAdd += ((left + leftAdd) * 2 - right - rightAdd);
    return leftAdd + rightAdd;
}

更新时间：2022-08-10 00:19:06

public int minInsertions(String s) {
    int ans = 0;
    int left = 0, right = 0;
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c == '(') left++;
        else {
            right += 2;
            if (i + 1 < s.length() && s.charAt(i + 1) == ')') {
                i++;
            } else {
                ans++;
            }
        }
        if (2 * left < right) {
            left++;
            ans++;
        }
    }
    ans += 2 * left - right;
    return ans;
}