代码随想录刷题|LeetCode 20. 有效的括号 1047. 删除字符串中的所有相邻重复项 150. 逆波兰表达式求值（上）

2022-12-14 71

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 代码随想录刷题|LeetCode 20. 有效的括号 1047. 删除字符串中的所有相邻重复项 150. 逆波兰表达式求值

20. 有效的括号

题目链接：力扣

思路

平衡符号是栈解决的经典应用，编译器检查程序的语法错误的时候，使用的就是栈这种数据结构。对应这种情况有用的工具就是检验是否每件事情都能成对完成的程序。栈结构的特殊性，很适合做对称匹配类题目

首先要解决的问题是，字符串中的括号有几种不匹配的情况：

1、左括号多了

2、右括号多了

3、括号不匹配

遍历字符串，如果是左括号就进行压栈，压的是对应的右括号，这样在遍历到右括号的时候，我们才可以与之直接进行比较和弹栈，而不是还需要进行转换，当然，你想转换也是可以的哈

最后如果出现栈中还有元素，或者遍历到与栈顶不匹配的括号，或者还没遍历完栈中却没了元素都视为无效的括号。只有括号顺序、括号个数匹配，并且栈为空才可以

有效的括号

第一步：创建栈

第二步：遍历字符串

第三步：如果是左括号，就将对应的右括号压栈

第四步：如果是右括号，就与栈顶元素进行比较

如果栈不为空，并且栈顶元素与字符相等，说明有效，弹栈

如果是其他情况，则说明不匹配

第五步：检查栈是否为空并返回

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        // 剪枝操作
        if (s.length() % 2 != 0) {
            return false;
        }
        // 遍历字符串
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '(') {
                stack.push(')');
            } else if (ch == '[') {
                stack.push(']');
            } else if (ch == '{') {
                stack.push('}');
            } else if (ch == ')' || ch ==']' || ch =='}') {
                if (!stack.isEmpty() && stack.peek().equals(ch) ) {
                    stack.pop();
                } else {
                    return false;
                }
            } 
        }
        return stack.isEmpty();
    }
}

1047. 删除字符串中的所有相邻重复项

题目链接：力扣

思路

两两匹配、两两成队、两两消除的这种就可以优先考虑是否可以使用栈

遍历字符串，将字符进行压栈，每次压栈的时候判断栈顶元素是否和要压栈的字符相同，如果一样，那就是重复相邻的字母，就不用压栈，而是进行弹栈了。就像对对碰一样

删除字符串中的所有相邻重复项

定义一个栈

如果因为压栈再弹栈和顺序会变化，所以最后要使用reverse()，如果不想反转可以从后往前遍历字符串

class Solution {
    public String removeDuplicates(String s) {
        Stack<Character> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (!stack.isEmpty() && stack.peek().equals(s.charAt(i))) {
                stack.pop();
            } else {
                stack.push(s.charAt(i));
            }
        }
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        return sb.reverse().toString();
    }
}

字符串作为栈

字符串sb作为栈，从字符串s的头开始添加字符，sb的最后一个字符就是栈顶元素，每次添加的时候直接进行比较，如果不相等就添加，如果相等，就删除最后一个字符

class Solution {
    public String removeDuplicates(String s) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            int top = sb.length() - 1;
            if (sb.length() != 0 && sb.charAt(top) == ch) {
                sb.deleteCharAt(top);
            } else {
                sb.append(ch);
            }
        }
        return sb.toString();
    }
}