@Yano 2015-12-30T03:26:12.000000Z 字数 9527 阅读 7030

# LeetCode之Stack题目汇总

LeetCode

LeetCode 题目汇总

# 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.

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

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 toppeek/pop from topsize, 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 backpeek/pop from frontsize, 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.

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

• 私有
• 公开
• 删除