栈 算法专题

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

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

class Solution {
    public String removeDuplicates(String s) {
        StringBuffer ret = new StringBuffer();
        char[] ss = s.toCharArray();
        for (int i = 0; i < ss.length; i++) {
            int len = ret.length();
            if (len > 0 && ss[i] == ret.charAt(len - 1)) {
                ret.deleteCharAt(len - 1);
            } else {
                ret.append(ss[i]);
            }
        }
        return ret.toString();
    }
}

二. 比较含退格的字符串

比较含退格的字符串

class Solution {
    public boolean backspaceCompare(String s, String t) {
        return changeStr(s).equals(changeStr(t));
    }

    public String changeStr(String s){
        StringBuffer ret = new StringBuffer();
        char[] ss = s.toCharArray();
        for(char x : ss){
            int len = ret.length();
            if(x == '#'){
                if(len > 0){
                ret.deleteCharAt(len - 1);
                }
            }else{
                ret.append(x);
            }
        }
        return ret.toString();
    }
}

三. 基本计算器II

基本计算器II

属于表达式求值的问题, 解法都是用栈模拟计算过程

class Solution {
    public int calculate(String s) {
        Deque<Integer> ret = new ArrayDeque<>();
        char[] ss = s.toCharArray();
        int n = ss.length;
        int i = 0;
        char op = '+';
        while(i < n){
            //判断空格
            if(ss[i] == ' '){
                i++;
            }else if(ss[i] >= '0' && ss[i] <= '9'){//如果是数字
                int tmp = 0;
                while(i < n && ss[i] >= '0' && ss[i] <= '9'){//把数字提出来
                    tmp = tmp * 10 + (ss[i]-'0');
                    i++;
                }
                //如果+-就入栈, 如果*/ 就先与栈顶元素计算后入栈
                if(op == '+') ret.push(tmp);
                if(op == '-') ret.push(-tmp);
                if(op == '*') ret.push(ret.poll() * tmp);
                if(op == '/') ret.push(ret.poll() / tmp);
            }else{//如果是符号
                op = ss[i];
                i++;
            }
        }
        //将栈中的元素全部相加
        int sum = 0;
        while(!ret.isEmpty()){
            sum += ret.poll();
        }
        return sum;
    }
}

四. 字符串解码

字符串解码

class Solution {
    public String decodeString(String s) {
        //一个存放字符串, 一个存放数字
        Stack<StringBuffer> st = new Stack<>();
        Stack<Integer> nums = new Stack<>();
        //细节: 先放入一个空串
        st.push(new StringBuffer());
        int i = 0;
        char[] ss = s.toCharArray();
        int n = ss.length;
        while(i < n){
            //如果是数字, 就把这个数提出来, 放到数字栈
            if(ss[i] >= '0' && ss[i] <= '9'){
                int tmp = 0;
                while(i < n && ss[i] >= '0' && ss[i] <= '9'){
                    tmp = tmp * 10 + (ss[i] - '0');
                    i++;
                }
                nums.push(tmp);
            }else if(ss[i] == '['){//如果是[, 就把后面的字符串提出来, 放到字符串栈
                i++;
                StringBuffer tmp = new StringBuffer();
                while(i < n && ss[i] >= 'a' && ss[i] <= 'z'){
                    tmp.append(ss[i]);
                    i++;
                }
                st.push(tmp);
            }else if(ss[i] ==']'){//如果是], 就进行解析, 取两个栈的栈顶元素, 添加到字符串栈栈顶的后面
                StringBuffer str = st.pop();
                int num = nums.pop();
                while(num-- != 0){
                    st.peek().append(str);
                }
                i++;
            }else{//如果是不在[]中的字符串, 就直接添加到字符串栈栈顶的后面
                 StringBuffer tmp = new StringBuffer();
                while(i < n && ss[i] >= 'a' && ss[i] <= 'z'){
                    tmp.append(ss[i]);
                    i++;
                }
                    st.peek().append(tmp);
            }
        }
        return st.pop().toString();
    }
}

五. 验证栈序列

验证栈序列

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> st = new Stack<>();
        int j = 0;
        for(int i = 0; i < pushed.length; i++){
            st.push(pushed[i]);
            while(!st.isEmpty() && popped[j] == st.peek()){
                st.pop();
                j++;
            }
        }
        if(st.isEmpty()){
            return true;
        }
        return false;
    }
}