代码随想录day11

20. 有效的括号

● 力扣题目链接
● 给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串，判断字符串是否有效。
● 有效字符串需满足：
● 左括号必须用相同类型的右括号闭合。
● 左括号必须以正确的顺序闭合。
● 注意空字符串可被认为是有效字符串。

思路

● 使用栈即可，前括号就入栈对应的后括号
● 如果不是前括号，看栈是否空"{}}“，然后看栈顶元素能否匹配”{]“，不能返回false，能就弹出
● 循环结束看栈是否为空”("
● 时间复杂度O(n) 空间复杂度O(n)

代码

class Solution {public boolean isValid(String s) {Deque<Character> stack = new ArrayDeque();for (int i = 0; i < s.length(); i++) {Character c = s.charAt(i);if (c.equals('(')) {stack.addFirst(')');} else if (c.equals('[')) {stack.addFirst(']');} else if (c.equals('{')) {stack.addFirst('}');} else if (stack.isEmpty() || !stack.peekFirst().equals(c)) {return false;} else {stack.removeFirst();}}return stack.isEmpty();}
}

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

● 力扣题目链接
● 给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
● 在 S 上反复执行重复项删除操作，直到无法继续删除。
● 在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

思路

● 使用栈，遍历字符串，如果栈空或元素不相等，就入栈，否则出栈
● 最后遍历栈元素，从尾部弹出，返回字符串即可

代码

class Solution {public String removeDuplicates(String s) {Deque<Character> stack = new ArrayDeque();for (int i = 0; i < s.length(); i++) {if (stack.isEmpty() || stack.peek() != s.charAt(i)) {stack.addFirst(s.charAt(i));} else {stack.removeFirst();}}StringBuilder builder = new StringBuilder();while (!stack.isEmpty()) {builder.append(stack.removeLast());}return new String(builder);}
}

150. 逆波兰表达式求值

● 力扣题目链接
● 根据 逆波兰表示法，求表达式的值。
● 有效的运算符包括 + , - , * , / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
● 说明：
● 整数除法只保留整数部分。 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

思路

● 使用栈处理即可，根据不同的情况入栈出栈

代码

class Solution {public int evalRPN(String[] tokens) {Deque<Integer> stack = new ArrayDeque();for (String str : tokens) {if (str.equals("+")) {stack.addFirst(stack.removeFirst() + stack.removeFirst());} else if (str.equals("-")) {int temp = stack.removeFirst();stack.addFirst(stack.removeFirst() - temp);} else if (str.equals("*")) {stack.addFirst(stack.removeFirst() * stack.removeFirst());} else if (str.equals("/")) {int temp = stack.removeFirst();stack.addFirst(stack.removeFirst() / temp);} else {stack.addFirst(Integer.parseInt(str));}}return stack.peekFirst();}
}