算法训练day11|20. 有效的括号；1047. 删除字符串中的所有相邻重复项；150. 逆波兰表达式求值

  1// 双端队列调用栈方法实现
  2class Solution {
  3    public boolean isValid(String s) {
  4        Deque<Character> deque = new LinkedList<>();
  5
  6        for (int i = 0; i < s.length(); i++) {
  7            // 左侧括号处理操作，直接加入
  8            if (s.charAt(i) == '(') {
  9                deque.push(')');
 10            } else if (s.charAt(i) == '{') {
 11                deque.push('}');
 12            } else if (s.charAt(i) == '[') {
 13                deque.push(']');
 14
 15            // 右括号处理操作；
 16            // 不匹配：右括号多了；左括号多了和括号不匹配；
 17            } else if (deque.isEmpty() || deque.peek() != s.charAt(i)) {
 18                return false;
 19            } else {
 20            // 匹配：直接弹出
 21                deque.pop(); 
 22            }
 23        } 
 24        // 判断是否为空？true : false;
 25        return deque.isEmpty();
 26    }
 27}
 28// 双端队列调用队列方法实现
 29class Solution {
 30    public boolean isValid(String s) {
 31        Deque<Character> deque = new LinkedList<>();
 32
 33        for (int i = 0; i < s.length(); i++) {
 34            // 左侧括号处理操作，直接加入
 35            if (s.charAt(i) == '(') {
 36                deque.offer(')');
 37            } else if (s.charAt(i) == '{') {
 38                deque.offer('}');
 39            } else if (s.charAt(i) == '[') {
 40                deque.offer(']');
 41
 42            // 右括号处理操作；
 43            // 不匹配：右括号多了；左括号多了和括号不匹配；
 44            } else if (deque.isEmpty() || deque.peek() != s.charAt(i)) {
 45                return false;
 46            } else {
 47            // 匹配：直接弹出
 48                deque.poll(); 
 49            }
 50        } 
 51        // 判断是否为空？true : false;
 52        return deque.isEmpty();
 53    }
 54}
 55// 用队列实现
 56class Solution {
 57    public boolean isValid(String s) {
 58        Queue<Character> queue = new LinkedList<>();
 59
 60        for (int i = 0; i < s.length(); i++) {
 61            // 左侧括号处理操作，直接加入
 62            if (s.charAt(i) == '(') {
 63                queue.offer(')');
 64            } else if (s.charAt(i) == '{') {
 65                queue.offer('}');
 66            } else if (s.charAt(i) == '[') {
 67                queue.offer(']');
 68
 69            // 右括号处理操作；
 70            // 不匹配：右括号多了；左括号多了和括号不匹配；
 71            } else if (queue.isEmpty() || queue.peek() != s.charAt(i)) {
 72                return false;
 73            } else {
 74            // 匹配：直接弹出
 75                queue.poll(); 
 76            }
 77        } 
 78        // 判断是否为空？true : false;
 79        return queue.isEmpty();
 80    }
 81}
 82
 83// 用栈实现
 84class Solution {
 85    public boolean isValid(String s) {
 86        Stack<Character> stack = new Stack<>();
 87
 88        for (int i = 0; i < s.length(); i++) {
 89            // 左侧括号处理操作，直接加入
 90            if (s.charAt(i) == '(') {
 91                stack.push(')');
 92            } else if (s.charAt(i) == '{') {
 93                stack.push('}');
 94            } else if (s.charAt(i) == '[') {
 95                stack.push(']');
 96
 97            // 右括号处理操作；
 98            // 不匹配：右括号多了；左括号多了和括号不匹配；
 99            } else if (stack.isEmpty() || stack.peek() != s.charAt(i)) {
100                return false;
101            } else {
102            // 匹配：直接弹出
103                stack.pop(); 
104            }
105        } 
106        // 判断是否为空？true : false;
107        return stack.isEmpty();
108    }
109}

 1// 用栈实现(当然可以使用（双端）队列调用相应方法来实现)
 2class Solution {
 3    public String removeDuplicates(String s) {
 4        Stack<Character> stack = new Stack<>();
 5        char ch;
 6        // 判断是否相等，进行入栈和出栈的操作
 7        for (int i = 0; i < s.length(); i++) {
 8            ch = s.charAt(i);
 9            if (stack.isEmpty() || stack.peek() != ch) {
10                stack.push(ch);
11            } else {
12                stack.pop();
13            }
14        }
15        String str = "";
16        while (!stack.isEmpty()) {
17            str += stack.pop();
18        }
19        return new StringBuffer(str).reverse().toString();
20     }
21}

 1class Solution {
 2    public int evalRPN(String[] tokens) {
 3        Stack<Integer> stack = new Stack<>();
 4        for (String s : tokens) { // 增强for循环，s表示为tokens[i]的内容
 5            if ("+".equals(s)) {
 6                stack.push(stack.pop() + stack.pop());
 7            } else if ("-".equals(s)) {
 8                stack.push(-stack.pop() + stack.pop()); // 先弹出的被减
 9            } else if ("/".equals(s)) {
10                int temp1 = stack.pop();
11                int temp2 = stack.pop();
12                stack.push(temp2/temp1); // 先弹出的被/
13            } else if ("*".equals(s)){
14                stack.push(stack.pop() * stack.pop());
15            } else {
16                stack.push(Integer.valueof(s)); // Integer.parseInt(s)
17            }
18        }
19        return stack.pop();
20    }
21}