训练营day11：栈与队列2

20. 有效的括号

https://leetcode.cn/problems/valid-parentheses/
学生时代刷过的一道题，利用栈的特性判断是不是成对，刚开始的思路是封装个方法判断是不是成对，这种方法就是会多一些判断逻辑，不够巧思。
看了卡哥代码是将左括号转为右括号，下一个元素入栈判断是不是相同即可，同时需要注意下剪枝条件，如果此时栈内为空或者是弹出元素不相同就可以确定是无效了。

class Solution {
    public boolean isValid(String s) {
        if (s.length() % 2 == 1 || s.length() == 0) {
            return false;
        }
        Stack<Character> records = new Stack<>();
        char cur;
        for(int i = 0; i < s.length(); i++) {
            cur = s.charAt(i);
            // 如果是左括号的判断逻辑
            if (cur == '(') {
                records.push(')');
            } else if(cur == '{') {
                records.push('}');
            } else if(cur == '[') {
                records.push(']');
            } else { // 如果是右括号的判断
                if(records.empty()) {
                    return false;
                } else if(records.peek() != cur) {
                    return false;
                } else {
                    records.pop();
                }
            }
        }

        return records.empty();
    }
}

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

https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/description/
直接用的Stack

class Solution {
    public String removeDuplicates(String s) {
        Stack<Character> records = new Stack<>();
        for(int i = 0;i < s.length();i++) {
            char cur = s.charAt(i);
            if (records.empty() || records.peek() != cur) {
                records.push(cur);
            } else {
                records.pop();
            }
        }

        StringBuilder resultsb = new StringBuilder();
        while(!records.empty()) {
            resultsb.append(records.peek());
            records.pop();
        }
        resultsb.reverse();

        return resultsb.toString();
    }
}

卡哥用的解法

class Solution {
    public String removeDuplicates(String S) {
        //ArrayDeque会比LinkedList在除了删除元素这一点外会快一点
        //参考：https://stackoverflow.com/questions/6163166/why-is-arraydeque-better-than-linkedlist
        ArrayDeque<Character> deque = new ArrayDeque<>();
        char ch;
        for (int i = 0; i < S.length(); i++) {
            ch = S.charAt(i);
            if (deque.isEmpty() || deque.peek() != ch) {
                deque.push(ch);
            } else {
                deque.pop();
            }
        }
        String str = "";
        //剩余的元素即为不重复的元素
        while (!deque.isEmpty()) {
            str = deque.pop() + str;
        }
        return str;
    }
}

卡哥里的这个字符串赋值是有小巧思在的，不用reverse直接拼接的时候就反向拼接！

150. 逆波兰表达式求值

https://leetcode.cn/problems/evaluate-reverse-polish-notation/description/
利用栈来求解简直是数学里的美学，完美，逻辑也比较简单：碰到计算符号就弹出两个数算一下，然后压栈，注意减法和除法的计算顺序。
「逆波兰表达式」
逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。
平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> temp = new Stack<>();
        String cur;
        int caculteResult;
        for(int i = 0; i < tokens.length;i++) {
            cur = tokens[i];
            if (cur.equals("+")) {
                caculteResult = temp.pop() + temp.pop();
                temp.push(caculteResult);
            } else if(cur.equals("-")) {
                int right = temp.pop();
                int left = temp.pop();
                caculteResult = left - right;
                temp.push(caculteResult);
            } else if(cur.equals("*")) {
                caculteResult = temp.pop() * temp.pop();
                temp.push(caculteResult);
            } else if(cur.equals("/")) {
                int right = temp.pop();
                int left = temp.pop();
                caculteResult = left / right;
                temp.push(caculteResult);
            } else {
                temp.push(Integer.parseInt(cur));
            }
        }

        return temp.pop();
    }
}