算法|栈、队列

71. 简化路径

class Solution {
    public String simplifyPath(String path) {
        String[] paths = path.split("/");
        Deque<String> deque = new LinkedList<>();
        for (String p:paths) {
            if (p == null || ".".equals(p) || "".equals(p)) continue;
            if ("..".equals(p)) {
                if (!deque.isEmpty()) {
                    deque.pollLast();
                }
            } else {
                deque.offerLast(p);
            }
        }
        
        if (deque.isEmpty()) {
            return "/";
        }
        StringBuilder stringBuilder = new StringBuilder();
        while (!deque.isEmpty()) {
            stringBuilder.append("/");
            stringBuilder.append(deque.pollFirst());
        }
        return stringBuilder.toString();
    }
}

155. 最小栈

class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> min;
    public MinStack() {
        stack = new Stack<>();
        min = new Stack<>();
    }
    
    public void push(int val) {
        if (min.isEmpty()) {
            min.push(val);
        } else {
            if (val <= min.peek()) {
                min.push(val);
            }
        }
        stack.push(val);
    }
    
    public void pop() {
        int val = stack.pop();
        if (val == min.peek()) {
            min.pop();
        }
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return min.isEmpty() ? 0 : min.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

class MinStack {
    public class ListNode {
         int val;
         int minVal;
         ListNode next;
         public ListNode(int val, int minVal, ListNode next) {
             this.val = val;
             this.minVal = minVal;
             this.next = next;
         }
    }
    private ListNode head;
    public MinStack() {

    }
    
    public void push(int val) {
        if (head == null) {
            head = new ListNode(val, val, null);
        } else {
            head = new ListNode(val, Math.min(val, head.minVal), head);
        }
    }
    
    public void pop() {
        if (head != null) {
            head = head.next;
        }
    }
    
    public int top() {
        if (head != null) {
            return head.val;
        }
        return -1;
    }
    
    public int getMin() {
        if (head != null) return head.minVal;
        return -1;
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

946. 验证栈序列

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

224. 基本计算器

class Solution {
    public int calculate(String s) {
        if (s == null || s.length() == 0) return -1;
        int len = s.length();
        int result = 0;
        int sign = 1;
        Stack<Integer> stack = new Stack<>();
        stack.push(sign);
        int i = 0;
        while (i < len) {
            char c = s.charAt(i);
            if (' ' == c) {
                i++;
            } else if ('+' == c) {
                sign = stack.peek();
                i++;
            } else if ('-' == c) {
                sign = -stack.peek();
                i++;
            } else if ('(' == c) {
                stack.push(sign);
                i++;
            } else if (')' == c) {
                stack.pop();
                i++;
            } else {
                long num = 0;
                while (i < len && Character.isDigit(s.charAt(i))) {
                    num = num * 10 + (s.charAt(i) - '0');
                    i++;
                }
                result += sign * num;
            }
        }

        return result;
    }
}

227. 基本计算器 II

class Solution {
    public int calculate(String s) {
        int num = 0;
        if (s == null || s.length() == 0) return -1;
        char preSign = '+';
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            //是数字
            if (c != ' ' && Character.isDigit(c)) {
                num = num * 10 + (c - '0');
            } 
            //不是数字 或者是最后一个
            if ((c != ' ' && !Character.isDigit(c)) || (i == s.length() - 1)) {
                if (preSign == '+') {
                    stack.push(num);
                } else if (preSign == '-') {
                    stack.push(-num);
                } else if (preSign == '*') {
                    stack.push(stack.pop() * num);
                } else if (preSign == '/') {
                    stack.push(stack.pop() / num);
                }
                preSign = c;      
                num = 0; 
            }
        }
        int result = 0;
        while (!stack.isEmpty()) {
            result += stack.pop();
        }
        return result;
    }
}

32. 最长有效括号

class Solution {
    public int longestValidParentheses(String s) {
        if (s == null || s.length() == 0) return 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int result = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    result = Math.max(result, i - stack.peek());
                }
            }
        }
        return result;
    }
}

726. 原子的数量

class Solution {
    int i = 0;
    int n = 0;
    public String countOfAtoms(String formula) {
        if (formula == null || formula.length() == 0) return "";
        n = formula.length();
        Stack<HashMap<String, Integer>> stack = new Stack<>();
        stack.push(new HashMap<>());
        while (i < n) {
            char c = formula.charAt(i);
            if (c == '(') {
                i++;
                stack.push(new HashMap<String, Integer>());
            } else if (c == ')') {
                i++;
                int v = parseNum(formula);
                HashMap<String, Integer> popMap = stack.pop();
                HashMap<String, Integer> topMap = stack.peek();
                for (Map.Entry<String, Integer> entry:popMap.entrySet()) {
                    String atom = entry.getKey();
                    int num = entry.getValue();
                    topMap.put(atom, topMap.getOrDefault(atom, 0) + v * num);
                }
            } else {
                String atom = parseAtom(formula);
                int num = parseNum(formula);
                Map<String, Integer> topMap = stack.peek();
                topMap.put(atom, topMap.getOrDefault(atom, 0) + num);
            }
        }
        TreeMap<String, Integer> treeMap = new TreeMap<>(stack.pop());
        StringBuilder result = new StringBuilder();
        for (Map.Entry<String, Integer> entry:treeMap.entrySet()) {
            String atom = entry.getKey();
            int num = entry.getValue();
            result.append(atom);
            if (num > 1) {
                result.append(num);
            }
        }
        return result.toString();
    }

    private int parseNum(String formula) {
        //没有了 或者不是数字
        if (i == n || !Character.isDigit(formula.charAt(i))) {
            return 1;
        }
    
        int num = 0;
        while (i < n && Character.isDigit(formula.charAt(i))) {
            num = num * 10 + (formula.charAt(i++) - '0');
        }
        return num;
    }
    private String parseAtom(String formula) {
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append(formula.charAt(i++));
        while (i < n && Character.isLowerCase(formula.charAt(i))) {
            stringBuilder.append(formula.charAt(i++));
        }
        return stringBuilder.toString();
    }
}

402. 移掉 K 位数字

class Solution {
    public String removeKdigits(String num, int k) {
        int length = num.length();
        Deque<Integer> deque = new LinkedList<>();
        for (int i = 0; i < length; i++) {
            int val = num.charAt(i) - '0';
            while (!deque.isEmpty() && k > 0 && deque.peekLast() > val) {
                deque.pollLast();
                k--;
            }
            deque.offerLast(val);
        }

        while (k > 0 && !deque.isEmpty()) {
            deque.pollLast();
            k--;
        }
        StringBuilder result = new StringBuilder();
        boolean isFirst = true;
        while (!deque.isEmpty()) {
            int val = deque.pollFirst();
            if (isFirst && val == 0) continue;
            isFirst = false;
            result.append(val);
        }
        
        return result.length() == 0 ? "0" : result.toString();
    }
}

678. 有效的括号字符串

class Solution {
    public boolean checkValidString(String s) {
        if (s == null) return true;
        Stack<Integer> leftStack = new Stack<>();
        Stack<Integer> starStack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                leftStack.push(i);
            }  else if (c == '*') {
                starStack.push(i);
            } else {
                if (!leftStack.isEmpty()) {
                    leftStack.pop();
                } else if (!starStack.isEmpty()) {
                    starStack.pop();
                } else return false;
            }
        }
        while (!leftStack.isEmpty() && !starStack.isEmpty()) {
            int left = leftStack.pop();
            int star = starStack.pop();
            if (left > star) return false;
        }
        return leftStack.isEmpty();
    }
}

394. 字符串解码

class Solution {
    public String decodeString(String s) {
        if (s == null) return null;
        int len = s.length();
        int i = 0;
        Deque<Integer> digitDeque = new LinkedList<>();
        Deque<String> letterDeque = new LinkedList<>();
        while (i < len) {
            char c = s.charAt(i); 
            //是数字
            if (Character.isDigit(c)) {
                int num = 0;
                while (i < len && Character.isDigit(s.charAt(i))) {
                    num  = num * 10 + (s.charAt(i) - '0');
                    i++;
                }
                digitDeque.offerLast(num);
                System.out.println(num);
            } else {
                //是字母或者括号
                if (c == ']') {
                    //弹出数字栈
                    int num = digitDeque.pollLast();
                    String letter = "";
                    while(!letterDeque.isEmpty() && !"[".equals(letterDeque.peekLast())) {
                        letter = letterDeque.pollLast() + letter;
                    }
                    //弹出最后一个[括号
                    letterDeque.pollLast();
                    StringBuilder letterBuilder = new StringBuilder();
                    while (num-- > 0) {
                        letterBuilder.append(letter);
                    }
                    //入栈
                    letterDeque.offerLast(letterBuilder.toString());
                    i++;
                } else {
                    letterDeque.offerLast(new String(new char[]{c}));
                    i++;
                }
            }
        }
        //字母
        StringBuilder result = new StringBuilder();
        while (!letterDeque.isEmpty()) {
            result.append(letterDeque.pollFirst());
        }
        return  result.toString();
    }
}