LeetCode之Stack题目汇总

LeetCode

我的博客：http://blog.csdn.net/yano_nankai
LeetCode题解：https://github.com/LjyYano/LeetCode

LeetCode 题目汇总

LeetCode之Array题目汇总
LeetCode之Hash Table题目汇总
LeetCode之Linked List题目汇总
LeetCode之Math题目汇总
LeetCode之String题目汇总
LeetCode之Binary Search题目汇总
LeetCode之Divide and Conquer题目汇总
LeetCode之Dynamic Programming题目汇总
LeetCode之Backtracing题目汇总
LeetCode之Stack题目汇总
LeetCode之Sort题目汇总
LeetCode之Bit Manipulation题目汇总
LeetCode之Tree题目汇总
LeetCode之Depth-first Search题目汇总
LeetCode之Breadth-first Search题目汇总
LeetCode之Graph题目汇总
LeetCode之Trie题目汇总
LeetCode之Design题目汇总

文章目录：

Basic Calculator

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

You may assume that the given expression is always valid.

Some examples:

"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23

Note: Do not use the eval built-in library function.

题目中只有+ - ( )。遍历字符串，对于每个字符c：

1. 如果是数字，则一直遍历到非数字字符，把数字找出，并与结果相加
2. 如果是+-符号，将sign设置成对应的值
3. 如果是(，将rt和sign压入栈中，重置rt和sign
4. 如果是)，将sign和rt弹出栈，并计算结果

    public int calculate(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        Stack<Integer> stack = new Stack<Integer>();
        int sign = 1;// 符号位，1表示+，-1表示-
        int rt = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                int val = c - '0';
                // 将数字取出
                while (i + 1 < s.length() && Character.isDigit(s.charAt(i + 1))) {
                    val = val * 10 + s.charAt(++i) - '0';
                }
                rt += sign * val;
            } else if (c == '-') {
                sign = -1;
            } else if (c == '+') {
                sign = 1;
            } else if (c == '(') {
                // 按照数字、符号的顺序，压入栈
                stack.push(rt);
                stack.push(sign);
                rt = 0;
                sign = 1;
            } else if (c == ')') {
                rt = rt * stack.pop() + stack.pop();
                sign = 1;
            }
        }
        return rt;
    }

Basic Calculator II

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid.

Some examples:

"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5

Note: Do not use the eval built-in library function.

Credits: 
Special thanks to @ts for adding this problem and creating all test cases.

分两次遍历，第一次遍历时，遇到乘除符号就计算；第二次遍历，计算加减符号。

    public int calculate(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        Stack<Integer> stack = new Stack<Integer>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                int val = c - '0';
                // 将数字取出
                while (i + 1 < s.length() && Character.isDigit(s.charAt(i + 1))) {
                    val = val * 10 + s.charAt(++i) - '0';
                }
                // 栈顶是 * / 运算符，计算
                if (!stack.isEmpty()
                        && (stack.peek() == 2 || stack.peek() == 3)) {
                    int sign = stack.pop();
                    int op = stack.pop();
                    int rt = 0;
                    if (sign == 2) {
                        rt = op * val;
                    } else {
                        rt = op / val;
                    }
                    stack.push(rt);
                } else {
                    stack.push(val);
                }
            } else if (c == ' ') {
                continue;
            } else {
                switch (c) {
                case '+':
                    stack.push(0);
                    break;
                case '-':
                    stack.push(1);
                    break;
                case '*':
                    stack.push(2);
                    break;
                case '/':
                    stack.push(3);
                    break;
                }
            }
        }
        if (stack.isEmpty()) {
            return 0;
        }
        // 因为要从左向右计算，所以要reverse
        Collections.reverse(stack);
        // 计算+-
        int rt = stack.pop();
        while (!stack.isEmpty()) {
            int sign = stack.pop();
            int op = stack.pop();
            if (sign == 0) {
                rt += op;
            } else {
                rt -= op;
            }
        }
        return rt;
    }

Evaluate Reverse Polish Notation

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Some examples:

["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

这道题是给定了合法的逆波兰表达式，要求根据给定的逆波兰表达式，求出最终结果。

只需要定义一个stack，如果是+, -, *, /四个运算符，就取出栈顶的两个数，进行相应操作。之后将计算得到的结果压入栈中。如果是数字，就直接入栈。

最终stack只剩下一个元素，这个元素就是逆波兰表达式的值。

逆波兰表达式

逆波兰表达式又叫做后缀表达式。下面是一些例子：

正常的表达式 逆波兰表达式

a+b —> a,b,+ 
a+(b-c) —> a,b,c,-,+ 
a+(b-c)_d —> a,b,c,-,d,_,+ 
a+d*(b-c)—>a,d,b,c,-,*,+ 
a=1+3 —> a=1,3 +

优势

它的优势在于只用两种简单操作，入栈和出栈就可以搞定任何普通表达式的运算。其运算方式如下：

如果当前字符为变量或者为数字，则压栈，如果是运算符，则将栈顶两个元素弹出作相应运算，结果再入栈，最后当表达式扫描完后，栈里的就是结果。

    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<Integer>();
        for (String s : tokens) {
            if ("*".equals(s)) {
                int n2 = stack.pop();
                int n1 = stack.pop();
                stack.push(n1 * n2);
            } else if ("/".equals(s)) {
                int n2 = stack.pop();
                int n1 = stack.pop();
                stack.push(n1 / n2);
            } else if ("+".equals(s)) {
                int n2 = stack.pop();
                int n1 = stack.pop();
                stack.push(n1 + n2);
            } else if ("-".equals(s)) {
                int n2 = stack.pop();
                int n1 = stack.pop();
                stack.push(n1 - n2);
            } else {
                stack.push(Integer.valueOf(s));
            }
        }
        return stack.pop();
    }

Implement Queue using Stacks

Implement the following operations of a queue using stacks.

• push(x) -- Push element x to the back of queue.
• pop() -- Removes the element from in front of queue.
• peek() -- Get the front element.
• empty() -- Return whether the queue is empty.

Notes:

• You must use only standard operations of a stack -- which means only push to top, peek/pop from top, size, and is empty operations are valid.
• Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
• You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

非常经典的题目，定义两个栈模拟队列。

1. push向stack1
2. pop从stack2，如果stack2为空，先将stack1的元素放入stack2

    class MyQueue {
        Stack<Integer> stack1 = new Stack<Integer>();
        Stack<Integer> stack2 = new Stack<Integer>();
        // Push element x to the back of queue.
        public void push(int x) {
            stack1.push(x);
        }
        // Removes the element from in front of queue.
        public void pop() {
            if (stack2.isEmpty()) {
                if (stack1.isEmpty()) {
                    throw new IllegalStateException();
                }
                while (!stack1.isEmpty()) {
                    stack2.push(stack1.pop());
                }
            }
            stack2.pop();
        }
        // Get the front element.
        public int peek() {
            if (stack2.isEmpty()) {
                if (stack1.isEmpty()) {
                    throw new IllegalStateException();
                }
                while (!stack1.isEmpty()) {
                    stack2.push(stack1.pop());
                }
            }
            return stack2.peek();
        }
        // Return whether the queue is empty.
        public boolean empty() {
            if (stack1.isEmpty() && stack2.isEmpty()) {
                return true;
            }
            return false;
        }
    }

Implement Stack using Queues

Implement the following operations of a stack using queues.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• empty() -- Return whether the stack is empty.

Notes:

• You must use only standard operations of a queue -- which means only push to back, peek/pop from front, size, and is empty operations are valid.
• Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
• You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

Update (2015-06-11):
The class name of the Java function had been updated to MyStack instead of Stack.

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and all test cases.

非常经典的题目，定义两个队列模拟栈的操作。总保持一个队列为空：

1. push就插入到非空的队列中
2. pop就把非空队列元素，依次放到另一个空队列中，只是最后一个元素弹出

    class MyStack {
        Queue<Integer> q1 = new LinkedList<Integer>();
        Queue<Integer> q2 = new LinkedList<Integer>();
        // Push element x onto stack.
        public void push(int x) {
            if (q1.isEmpty() && q2.isEmpty()) {
                q1.add(x);
            } else if (!q1.isEmpty()) {
                q1.add(x);
            } else {
                q2.add(x);
            }
        }
        // Removes the element on top of the stack.
        public void pop() {
            if (empty()) {
                throw new IllegalStateException();
            }
            // q1、q2必有一个为空
            if (q2.isEmpty()) {
                while (!q1.isEmpty()) {
                    int x = q1.remove();
                    if (!q1.isEmpty()) {
                        q2.add(x);
                    }
                }
            } else if (q1.isEmpty()) {
                while (!q2.isEmpty()) {
                    int x = q2.remove();
                    if (!q2.isEmpty()) {
                        q1.add(x);
                    }
                }
            }
        }
        // Get the top element.
        public int top() {
            if (empty()) {
                throw new IllegalStateException();
            }
            int x = 0;
            // q1、q2必有一个为空
            if (q2.isEmpty()) {
                while (!q1.isEmpty()) {
                    x = q1.remove();
                    q2.add(x);
                }
            } else if (q1.isEmpty()) {
                while (!q2.isEmpty()) {
                    x = q2.remove();
                    q1.add(x);
                }
            }
            return x;
        }
        // Return whether the stack is empty.
        public boolean empty() {
            if (q1.isEmpty() && q2.isEmpty()) {
                return true;
            }
            return false;
        }
    }

Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• getMin() -- Retrieve the minimum element in the stack.

本题是一个栈的操作，但是要求getMin()在O(1)的时间复杂度。

考虑使用另一个辅助栈，用来存储[0..i]的最小值。

    class MinStack {
        Stack<Integer> stack = new Stack<Integer>();
        Stack<Integer> min = new Stack<Integer>();
        public void push(int x) {
            if (stack.isEmpty()) {
                stack.push(x);
                min.push(x);
            } else {
                stack.push(x);
                min.push(Math.min(stack.peek(), min.peek()));
            }
        }
        public void pop() {
            if (!stack.isEmpty()) {
                stack.pop();
                min.pop();
            }
        }
        public int top() {
            if (!stack.isEmpty()) {
                return stack.peek();
            }
            throw new IllegalStateException();
        }
        public int getMin() {
            if (!min.isEmpty()) {
                return min.peek();
            }
            throw new IllegalStateException();
        }
    }

Simplify Path

Given an absolute path for a file (Unix-style), simplify it.

For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"

click to show corner cases.

Corner Cases:

• Did you consider the case where path = "/../"?
  In this case, you should return "/".
• Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/".
  In this case, you should ignore redundant slashes and return "/home/foo".

    public String simplifyPath(String path) {
        if (path == null) {
            return null;
        }
        String[] names = path.split("/");
        int eat = 0;
        LinkedList<String> stack = new LinkedList<String>();
        for (int i = names.length - 1; i >= 0; i--) {
            String token = names[i];
            // token是".."， 表示上级路径，前一个路径不打印
            // token是"."， 表示当前路径，自身不打印
            // token是"", 表示为两个"/"相连，不做操作
            // eat>0，表示左边不打印
            // 否则，将token入栈
            if (token.equals("..")) {
                eat++;
            } else if (token.equals(".")) {
                // do nothing
            } else if (token.equals("")) {
                // do nothing
            } else {
                if (eat > 0) {
                    eat--;
                } else {
                    stack.push(token);
                }
            }
        }
        StringBuilder s = new StringBuilder();
        s.append("/");
        // 最后一个不加"/"，所以while判断条件是>1
        while (stack.size() > 1) {
            s.append(stack.pop());
            s.append("/");
        }
        // 最后一个不加"/"
        if (!stack.isEmpty()) {
            s.append(stack.pop());
        }
        return s.toString();
    }

Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

    public boolean isValid(String s) {
        if (s == null || s.length() % 2 == 1) {
            return false;
        }
        HashMap<Character, Character> map = new HashMap<Character, Character>();
        map.put('(', ')');
        map.put('[', ']');
        map.put('{', '}');
        Stack<Character> stack = new Stack<Character>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (map.keySet().contains(c)) {
                stack.push(c);
            } else if (map.values().contains(c)) {
                if (!stack.empty() && map.get(stack.peek()) == c) {
                    stack.pop();
                } else {
                    return false;
                }
            }
        }
        return stack.empty();
    }