代码随想录算法训练营第十一天| 20. 有效的括号、1047. 删除字符串中的所有相邻重复项、150. 逆波兰表达式求值

本文主要是介绍代码随想录算法训练营第十一天| 20. 有效的括号、1047. 删除字符串中的所有相邻重复项、150. 逆波兰表达式求值，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

20. 有效的括号

在这里插入图片描述

题目链接：20. 有效的括号
文档讲解：代码随想录
状态：so easy

思路： 使用栈，如果是左括号就入栈，如果是右括号则判断是否和栈顶括号匹配，如果匹配就出栈，否则判断遍历完字符串后栈中是否还有残留。

题解：

    public boolean isValid(String s) {if (s.length() % 2 != 0)return false;char[] chars = s.toCharArray();Deque<Character> stack = new ArrayDeque<>();for (char c : chars) {// 如果当前字符是开放括号，将其压入栈中if (c == '(' || c == '[' || c == '{') {stack.push(c);}// 如果当前字符是闭合括号，并且栈不为空且栈顶元素与当前闭合括号匹配// 则弹出栈顶元素，表示括号匹配成功else if (c == ')' && !stack.isEmpty() && stack.peek() == '(') {stack.poll();} else if (c == ']' && !stack.isEmpty() && stack.peek() == '[') {stack.poll();} else if (c == '}' && !stack.isEmpty() && stack.peek() == '{') {stack.poll();} else {return false;}}return stack.isEmpty();}

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

在这里插入图片描述

题目链接：1047. 删除字符串中的所有相邻重复项
文档讲解：代码随想录
状态：还行

思路： 使用栈，栈顶元素如果和即将入栈元素相同就出栈。

普通栈解法：

    public String removeDuplicates2(String s) {char[] chars = s.toCharArray();Deque<Character> stack = new ArrayDeque<>();for (char c : chars) {Character peek = stack.peek();if (peek != null && peek == c) {stack.poll();} else {stack.push(c);}}StringBuilder sb = new StringBuilder();while (!stack.isEmpty()) {sb.append(stack.poll());}return sb.toString();}

数组模拟栈：

    public String removeDuplicates(String s) {// 将输入字符串转换为字符数组char[] cs = s.toCharArray();// 用于模拟栈的数组char[] stack = new char[s.length()];// 栈顶指针int top = -1;// 遍历输入字符串的每个字符for (char c : cs) {if (top >= 0 && stack[top] == c) {// 如果栈不为空且栈顶元素与当前字符相同，弹出栈顶元素top--;} else {// 否则，将当前字符压入栈stack[++top] = c;}}// 将栈中的字符组成字符串return new String(stack, 0, top + 1);}

双指针： 本质上和数组模拟栈的逻辑是一样的

public String removeDuplicates(String s) {char[] ch = s.toCharArray();int fast = 0;int slow = 0;while(fast < s.length()){// 直接用fast指针覆盖slow指针的值ch[slow] = ch[fast];// 遇到前后相同值的，就跳过，即slow指针后退一步，下次循环就可以直接被覆盖掉了if(slow > 0 && ch[slow] == ch[slow - 1]){slow--;}else{slow++;}fast++;}return new String(ch,0,slow);
}

150. 逆波兰表达式求值

在这里插入图片描述

题目链接：150. 逆波兰表达式求值
文档讲解：代码随想录
状态：还可以

思路： 逆波兰表达式一般使用栈，遇到运算符就将运算符前两个数拿出来做对应计算然后再入栈。

自带栈解法：

    public int evalRPN(String[] tokens) {Deque<Integer> stack = new ArrayDeque<>();for (String token : tokens) {if (!token.equals("+") && !token.equals("-") && !token.equals("*") && !token.equals("/")) {stack.push(Integer.valueOf(token));} else {int second = stack.pop(); // 出栈两个操作数int first = stack.pop();switch (token) {case "+":stack.push(first + second); // 将计算结果入栈break;case "-":stack.push(first - second);break;case "*":stack.push(first * second);break;case "/":stack.push(first / second);break;}}}return stack.pop();}

数组模拟栈：

class Solution {public int evalRPN(String[] tokens) {int[] stack = new int[tokens.length];int top = -1; // 栈顶指针，初始化为-1表示空栈for (String token : tokens) {if ("+-*/".contains(token)) {int b = stack[top--]; // 出栈两个操作数int a = stack[top--];stack[++top] = calculate(a, b, token); // 将计算结果入栈} else {stack[++top] = Integer.parseInt(token); // 将操作数入栈}}return stack[top]; // 返回栈顶元素即为最终结果}private int calculate(int a, int b, String operator) {switch (operator) {case "+":return a + b;case "-":return a - b;case "*":return a * b;case "/":return a / b;default:throw new IllegalArgumentException("Invalid operator: " + operator);}}
}