继续学习栈和队列

20.有效的括号 (opens new window)

简单题，可以使用s.length()%2!=0剪枝

class Solution {

    public boolean isValid(String s) {
        if (s.length()%2!=0){
            return false;
        }
        Deque<Character> stack = new ArrayDeque<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(' || s.charAt(i) == '{' || s.charAt(i) == '['){
                stack.push(s.charAt(i));
            }else {
                    if (stack.isEmpty() || (s.charAt(i)==')' && stack.peek()!='(')
                        || (s.charAt(i)=='}' && stack.peek()!='{')
                        || (s.charAt(i)==']' && stack.peek()!='[')
                    ){
                        return false;
                    }
                stack.pop();
            }
        }
        return stack.isEmpty();
    }
}

1047.删除字符串中的所有相邻重复项 (opens new window)

使用双端队列，代替栈。然后利用栈的特性去删除重复项

class Solution {
    public String removeDuplicates(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        for (int i = 0; i < s.length(); i++) {
            if (stack.isEmpty() || stack.peek() != s.charAt(i)){
                stack.push(s.charAt(i));
            }else if (stack.peek() == s.charAt(i)){
                stack.pop();
            }
        }


        //输出
        char[] chars = new char[stack.size()];
        for (int i = stack.size()-1; i >=0; i--) {
            chars[i] = stack.pop();
        }

        return new String(chars);

    }
}

150.逆波兰表达式求值 (opens new window)

也就是后缀表达式，跟下面的二叉树章节有关。好久没听过这个了，都给忘了

这道题好像上学的时候做过，算是简单的。

class Solution {

    //["2","1","+","3","*"]
    public int evalRPN(String[] tokens) {
        Deque<String> stack1 = new ArrayDeque<>();  //临时结果栈
        Set<String> set = new HashSet<>();
        set.add("+");
        set.add("*");
        set.add("/");
        set.add("-");
        for (String token : tokens) {
            if (set.contains(token)){
                String a = stack1.pop();
                String b = stack1.pop();
                if (token.equals("+")){
                    stack1.push(String.valueOf(Integer.parseInt(b)+Integer.parseInt(a)));
                }else if (token.equals("-")){
                    stack1.push(String.valueOf(Integer.parseInt(b)-Integer.parseInt(a)));
                }else if (token.equals("/")){
                    stack1.push(String.valueOf(Integer.parseInt(b)/Integer.parseInt(a)));
                }else if (token.equals("*")){
                    stack1.push(String.valueOf(Integer.parseInt(b)*Integer.parseInt(a)));
                }
            }else {
                stack1.push(token);
            }


        }
        return Integer.parseInt(stack1.pop());
    }
}