代码随想录算法训练营第十天 | LeetCode 20(有效的括号) LeetCode 1047(删除字符串中的所有相邻重复项) LeetCode 150(逆波兰表达式求值)

20:有效的括号

LeetCode 20(有效的括号)

方法一

import java.util.Stack;
class Solution {
    public boolean isValid(String s) {
        int len = s.length();
        if(len % 2 == 1){
            return false;
        }
        Stack<Character> stack = new Stack<Character>();
        for(int i = 0; i < len; i++){
            if(stack.isEmpty()){
                stack.add(s.charAt(i));
            }else{
                char temp = s.charAt(i);
                char stackChar = stack.peek();
                if(stackChar == '(' && temp == ')'){
                    stack.pop();
                }else if(stackChar == '{' && temp == '}'){
                    stack.pop();
                }else if(stackChar == '[' && temp == ']'){
                    stack.pop();
                }else{
                    stack.add(temp);
                }
            }
        }
        return stack.isEmpty();
    }
}

047:删除字符串中的所有相邻重复项

LeetCode 1047(删除字符串中的所有相邻重复项)

方法一

import java.util.Stack;
class Solution {
    public String removeDuplicates(String s) {
        Stack<Character> stack = new Stack<Character>();
        StringBuilder sb;
        while(true){
            stack.clear();
            sb = new StringBuilder();
            int k = 0;
            for ( ;k < s.length(); k++) {
                char c = s.charAt(k);
                if(!stack.isEmpty() && stack.peek() == c){
                    stack.pop();
                    continue;
                }else{
                    stack.push(c);
                }
            }
            if(stack.size() == k){
                break;
            }
            int size = stack.size();
            for(int i = 0; i < size; i++){
                sb.append(stack.pop());
            }
            s = sb.reverse().toString();
        }
        return s;
    }
}

方法二 优化

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;
    }
}

方法三 字符串本身当栈

class Solution {
    public String removeDuplicates(String s) {
        //直接当栈
        StringBuffer res = new StringBuffer();
        // top为 res 的长度
        int top = -1;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // 当 top > 0,即栈中有字符时，当前字符如果和栈中字符相等，弹出栈顶字符，同时 top--
            if (top >= 0 && res.charAt(top) == c) {
                res.deleteCharAt(top);
                top--;
            // 否则，将该字符 入栈，同时top++
            } else {
                res.append(c);
                top++;
            }
        }
        return res.toString();
    }
}

150:逆波兰表达式求值

LeetCode 150(逆波兰表达式求值)

方法一

import java.util.Stack;
class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<Integer>();
        for (String token : tokens){
            int i;
            switch (token) {
                case "+":
                    stack.push(stack.pop() + stack.pop());
                    break;
                case "-":
                    i = stack.pop();
                    stack.push(stack.pop() - i);
                    break;
                case "*":
                    stack.push(stack.pop() * stack.pop());
                    break;
                case "/":
                    i = stack.pop();
                    stack.push(stack.pop() / i);
                    break;        
                default:
                    stack.push(Integer.valueOf(token));
                    break;
            }
        }
        return stack.pop();
    }
}