[关闭]
@Yano 2015-12-30T03:26:12.000000Z 字数 9527 阅读 6125

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 + 1" = 2
  2. " 2-1 + 2 " = 3
  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弹出栈,并计算结果
  1. public int calculate(String s) {
  2. if (s == null || s.length() == 0) {
  3. return 0;
  4. }
  5. Stack<Integer> stack = new Stack<Integer>();
  6. int sign = 1;// 符号位,1表示+,-1表示-
  7. int rt = 0;
  8. for (int i = 0; i < s.length(); i++) {
  9. char c = s.charAt(i);
  10. if (Character.isDigit(c)) {
  11. int val = c - '0';
  12. // 将数字取出
  13. while (i + 1 < s.length() && Character.isDigit(s.charAt(i + 1))) {
  14. val = val * 10 + s.charAt(++i) - '0';
  15. }
  16. rt += sign * val;
  17. } else if (c == '-') {
  18. sign = -1;
  19. } else if (c == '+') {
  20. sign = 1;
  21. } else if (c == '(') {
  22. // 按照数字、符号的顺序,压入栈
  23. stack.push(rt);
  24. stack.push(sign);
  25. rt = 0;
  26. sign = 1;
  27. } else if (c == ')') {
  28. rt = rt * stack.pop() + stack.pop();
  29. sign = 1;
  30. }
  31. }
  32. return rt;
  33. }

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:

  1. "3+2*2" = 7
  2. " 3/2 " = 1
  3. " 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.


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

  1. public int calculate(String s) {
  2. if (s == null || s.length() == 0) {
  3. return 0;
  4. }
  5. Stack<Integer> stack = new Stack<Integer>();
  6. for (int i = 0; i < s.length(); i++) {
  7. char c = s.charAt(i);
  8. if (Character.isDigit(c)) {
  9. int val = c - '0';
  10. // 将数字取出
  11. while (i + 1 < s.length() && Character.isDigit(s.charAt(i + 1))) {
  12. val = val * 10 + s.charAt(++i) - '0';
  13. }
  14. // 栈顶是 * / 运算符,计算
  15. if (!stack.isEmpty()
  16. && (stack.peek() == 2 || stack.peek() == 3)) {
  17. int sign = stack.pop();
  18. int op = stack.pop();
  19. int rt = 0;
  20. if (sign == 2) {
  21. rt = op * val;
  22. } else {
  23. rt = op / val;
  24. }
  25. stack.push(rt);
  26. } else {
  27. stack.push(val);
  28. }
  29. } else if (c == ' ') {
  30. continue;
  31. } else {
  32. switch (c) {
  33. case '+':
  34. stack.push(0);
  35. break;
  36. case '-':
  37. stack.push(1);
  38. break;
  39. case '*':
  40. stack.push(2);
  41. break;
  42. case '/':
  43. stack.push(3);
  44. break;
  45. }
  46. }
  47. }
  48. if (stack.isEmpty()) {
  49. return 0;
  50. }
  51. // 因为要从左向右计算,所以要reverse
  52. Collections.reverse(stack);
  53. // 计算+-
  54. int rt = stack.pop();
  55. while (!stack.isEmpty()) {
  56. int sign = stack.pop();
  57. int op = stack.pop();
  58. if (sign == 0) {
  59. rt += op;
  60. } else {
  61. rt -= op;
  62. }
  63. }
  64. return rt;
  65. }

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:

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

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

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

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

逆波兰表达式

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

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

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

优势

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

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

  1. public int evalRPN(String[] tokens) {
  2. Stack<Integer> stack = new Stack<Integer>();
  3. for (String s : tokens) {
  4. if ("*".equals(s)) {
  5. int n2 = stack.pop();
  6. int n1 = stack.pop();
  7. stack.push(n1 * n2);
  8. } else if ("/".equals(s)) {
  9. int n2 = stack.pop();
  10. int n1 = stack.pop();
  11. stack.push(n1 / n2);
  12. } else if ("+".equals(s)) {
  13. int n2 = stack.pop();
  14. int n1 = stack.pop();
  15. stack.push(n1 + n2);
  16. } else if ("-".equals(s)) {
  17. int n2 = stack.pop();
  18. int n1 = stack.pop();
  19. stack.push(n1 - n2);
  20. } else {
  21. stack.push(Integer.valueOf(s));
  22. }
  23. }
  24. return stack.pop();
  25. }

Implement Queue using Stacks

Implement the following operations of a queue using stacks.

Notes:


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

  1. push向stack1
  2. pop从stack2,如果stack2为空,先将stack1的元素放入stack2
  1. class MyQueue {
  2. Stack<Integer> stack1 = new Stack<Integer>();
  3. Stack<Integer> stack2 = new Stack<Integer>();
  4. // Push element x to the back of queue.
  5. public void push(int x) {
  6. stack1.push(x);
  7. }
  8. // Removes the element from in front of queue.
  9. public void pop() {
  10. if (stack2.isEmpty()) {
  11. if (stack1.isEmpty()) {
  12. throw new IllegalStateException();
  13. }
  14. while (!stack1.isEmpty()) {
  15. stack2.push(stack1.pop());
  16. }
  17. }
  18. stack2.pop();
  19. }
  20. // Get the front element.
  21. public int peek() {
  22. if (stack2.isEmpty()) {
  23. if (stack1.isEmpty()) {
  24. throw new IllegalStateException();
  25. }
  26. while (!stack1.isEmpty()) {
  27. stack2.push(stack1.pop());
  28. }
  29. }
  30. return stack2.peek();
  31. }
  32. // Return whether the queue is empty.
  33. public boolean empty() {
  34. if (stack1.isEmpty() && stack2.isEmpty()) {
  35. return true;
  36. }
  37. return false;
  38. }
  39. }

Implement Stack using Queues

Implement the following operations of a stack using queues.

Notes:

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就把非空队列元素,依次放到另一个空队列中,只是最后一个元素弹出
  1. class MyStack {
  2. Queue<Integer> q1 = new LinkedList<Integer>();
  3. Queue<Integer> q2 = new LinkedList<Integer>();
  4. // Push element x onto stack.
  5. public void push(int x) {
  6. if (q1.isEmpty() && q2.isEmpty()) {
  7. q1.add(x);
  8. } else if (!q1.isEmpty()) {
  9. q1.add(x);
  10. } else {
  11. q2.add(x);
  12. }
  13. }
  14. // Removes the element on top of the stack.
  15. public void pop() {
  16. if (empty()) {
  17. throw new IllegalStateException();
  18. }
  19. // q1、q2必有一个为空
  20. if (q2.isEmpty()) {
  21. while (!q1.isEmpty()) {
  22. int x = q1.remove();
  23. if (!q1.isEmpty()) {
  24. q2.add(x);
  25. }
  26. }
  27. } else if (q1.isEmpty()) {
  28. while (!q2.isEmpty()) {
  29. int x = q2.remove();
  30. if (!q2.isEmpty()) {
  31. q1.add(x);
  32. }
  33. }
  34. }
  35. }
  36. // Get the top element.
  37. public int top() {
  38. if (empty()) {
  39. throw new IllegalStateException();
  40. }
  41. int x = 0;
  42. // q1、q2必有一个为空
  43. if (q2.isEmpty()) {
  44. while (!q1.isEmpty()) {
  45. x = q1.remove();
  46. q2.add(x);
  47. }
  48. } else if (q1.isEmpty()) {
  49. while (!q2.isEmpty()) {
  50. x = q2.remove();
  51. q1.add(x);
  52. }
  53. }
  54. return x;
  55. }
  56. // Return whether the stack is empty.
  57. public boolean empty() {
  58. if (q1.isEmpty() && q2.isEmpty()) {
  59. return true;
  60. }
  61. return false;
  62. }
  63. }

Min Stack

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


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

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

  1. class MinStack {
  2. Stack<Integer> stack = new Stack<Integer>();
  3. Stack<Integer> min = new Stack<Integer>();
  4. public void push(int x) {
  5. if (stack.isEmpty()) {
  6. stack.push(x);
  7. min.push(x);
  8. } else {
  9. stack.push(x);
  10. min.push(Math.min(stack.peek(), min.peek()));
  11. }
  12. }
  13. public void pop() {
  14. if (!stack.isEmpty()) {
  15. stack.pop();
  16. min.pop();
  17. }
  18. }
  19. public int top() {
  20. if (!stack.isEmpty()) {
  21. return stack.peek();
  22. }
  23. throw new IllegalStateException();
  24. }
  25. public int getMin() {
  26. if (!min.isEmpty()) {
  27. return min.peek();
  28. }
  29. throw new IllegalStateException();
  30. }
  31. }

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:


  1. public String simplifyPath(String path) {
  2. if (path == null) {
  3. return null;
  4. }
  5. String[] names = path.split("/");
  6. int eat = 0;
  7. LinkedList<String> stack = new LinkedList<String>();
  8. for (int i = names.length - 1; i >= 0; i--) {
  9. String token = names[i];
  10. // token是"..", 表示上级路径,前一个路径不打印
  11. // token是".", 表示当前路径,自身不打印
  12. // token是"", 表示为两个"/"相连,不做操作
  13. // eat>0,表示左边不打印
  14. // 否则,将token入栈
  15. if (token.equals("..")) {
  16. eat++;
  17. } else if (token.equals(".")) {
  18. // do nothing
  19. } else if (token.equals("")) {
  20. // do nothing
  21. } else {
  22. if (eat > 0) {
  23. eat--;
  24. } else {
  25. stack.push(token);
  26. }
  27. }
  28. }
  29. StringBuilder s = new StringBuilder();
  30. s.append("/");
  31. // 最后一个不加"/",所以while判断条件是>1
  32. while (stack.size() > 1) {
  33. s.append(stack.pop());
  34. s.append("/");
  35. }
  36. // 最后一个不加"/"
  37. if (!stack.isEmpty()) {
  38. s.append(stack.pop());
  39. }
  40. return s.toString();
  41. }

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.


  1. public boolean isValid(String s) {
  2. if (s == null || s.length() % 2 == 1) {
  3. return false;
  4. }
  5. HashMap<Character, Character> map = new HashMap<Character, Character>();
  6. map.put('(', ')');
  7. map.put('[', ']');
  8. map.put('{', '}');
  9. Stack<Character> stack = new Stack<Character>();
  10. for (int i = 0; i < s.length(); i++) {
  11. char c = s.charAt(i);
  12. if (map.keySet().contains(c)) {
  13. stack.push(c);
  14. } else if (map.values().contains(c)) {
  15. if (!stack.empty() && map.get(stack.peek()) == c) {
  16. stack.pop();
  17. } else {
  18. return false;
  19. }
  20. }
  21. }
  22. return stack.empty();
  23. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注