作业题
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); } }
