代码随想录 Day11 - 栈与队列（下）
作者：jjn0703
- 2023-07-09 江苏
本文字数：1770 字
阅读完需：约 6 分钟
作业题
20. 有效的括号
输入字符串判断时，遇到 "}])"时，即可和栈尾做对比，若匹配，则抵消。
package jjn.carl.stack_queue;
import java.util.*;
/** * @author Jiang Jining * @since 2023-07-09 11:39 */public class LeetCode20 { public boolean isValid(String s) { if (s == null) { return false; } Deque<Character> cur = new ArrayDeque<>(); Map<Character, Character> map = new HashMap<>(); map.put('}', '{'); map.put(')', '('); map.put(']', '['); for (int i = 0; i < s.length(); i++) { if (cur.isEmpty() || !Objects.equals(cur.peekLast(), map.get(s.charAt(i)))) { cur.offer(s.charAt(i)); } else { cur.pollLast(); } } return cur.isEmpty(); } public static void main(String[] args) { System.out.println("new LeetCode20().isValid(\"()[]{}\") = " + new LeetCode20().isValid("()[]{}")); System.out.println("new LeetCode20().isValid(\"{[]}\") = " + new LeetCode20().isValid("{[]}")); }}
复制代码
1047. 删除字符串中的所有相邻重复项
每个字符均与栈顶元素做对比，若相同则抵消，要么压栈，考虑字符串操作，直接使用 StringBuilder 类进行操作。
package jjn.carl.stack_queue;
import java.util.Objects;
/** * @author Jiang Jining * @since 2023-07-09 14:54 */public class LeetCode1047 { public String removeDuplicates(String s) { StringBuilder stringBuilder = new StringBuilder(); for (char c : s.toCharArray()) { if (stringBuilder.isEmpty() || !Objects.equals(stringBuilder.charAt(stringBuilder.length() - 1), c)) { stringBuilder.append(c); } else { stringBuilder.deleteCharAt(stringBuilder.length() - 1); } } return stringBuilder.toString(); } public static void main(String[] args) { String removedDuplicates = new LeetCode1047().removeDuplicates("abbaca"); System.out.println("removedDuplicates = " + removedDuplicates); }}
复制代码
150. 逆波兰表达式求值
碰到“+”，“-”，“*”，“/”符号时，则取出栈顶的两个数进行计算，并压入栈中；碰到数字则直接压栈。
package jjn.carl.stack_queue;
import java.util.Set;import java.util.Stack;
/** * @author Jiang Jining * @since 2023-07-09 15:16 */public class LeetCode150 { public int evalRPN(String[] tokens) { Set<String> operations = Set.of("+", "-", "*", "/"); Stack<Integer> stack = new Stack<>(); for (String token : tokens) { if (isOperation(token, operations)) { int first = stack.pop(); int second = stack.pop(); stack.push(calc(first, second, token)); } else { stack.push(Integer.parseInt(token)); } } return stack.pop(); } private boolean isOperation(String token, Set<String> operations) { return operations.contains(token); } private int calc(int first, int second, String operation) { if ("+".equals(operation)) { return second + first; } if ("-".equals(operation)) { return second - first; } if ("*".equals(operation)) { return second * first; } return second / first; } public static void main(String[] args) { int result = new LeetCode150().evalRPN(new String[]{"10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"}); System.out.println("result = " + result); }}
复制代码
划线
评论
复制
发布于: 刚刚阅读数: 3
版权声明: 本文为 InfoQ 作者【jjn0703】的原创文章。
原文链接:【http://xie.infoq.cn/article/3e5648083372afd6acea362da】。
本文遵守【CC-BY 4.0】协议，转载请保留原文出处及本版权声明。
jjn0703
关注
Java工程师/终身学习者 2018-03-26 加入
USTC硕士/健身健美爱好者/Java工程师.
评论