Stack And String LEETCODE-100-DAY5

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

Example 1:

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

Constraints:

• Methods pop, top and getMin operations will always be called on non-empty stacks.

  /*
   * @lc app=leetcode.cn id=155 lang=java
   *
   * [155] 最小栈
   */
  
  // @lc code=start
  class MinStack {
      Stack<Integer> stack;
      int min;//Integer比较的是范围，是地址，Interger类型之间的比较应该用equals()
      /** initialize your data structure here. */
      public MinStack() {
          stack = new Stack<>();
          min = Integer.MAX_VALUE;//初始化Min
      }
      
      public void push(int x) {
          if (x <= min) {
              stack.push(min);
              min = x;
          }
              stack.push(x);
      }
      
      public void pop() {
          if (stack.pop() == min) {
              min = stack.pop();
          }
      }
      
      public int top() {
          return stack.peek();
      }
      
      public int getMin() {
          return min;
      }
  }
  
  /**
   * Your MinStack object will be instantiated and called as such:
   * MinStack obj = new MinStack();
   * obj.push(x);
   * obj.pop();
   * int param_3 = obj.top();
   * int param_4 = obj.getMin();
   */
  // @lc code=end
  
  // class MinStack {
  //     private Stack<Integer> stack;
  //     private Stack<Integer> minStack;
  //     /** initialize your data structure here. */
  //     public MinStack() {
  //         stack = new Stack<>();
  //         minStack = new Stack<>();
  //     }
      
  //     public void push(int x) {
  //         stack.push(x);
  //         if(!minStack.isEmpty()) {
  //             int min = minStack.peek();
  //             if(x <= min) {
  //                 minStack.push(x); 
  //             }
  //         } else {
  //             minStack.push(x);
  //         }
  //     }
      
  //     public void pop() {
  //         int x = stack.pop();
  //         if(!minStack.isEmpty()) {
  //             if(x == minStack.peek()) {
  //                 minStack.pop();
  //             }
  //         }
  //     }
      
  //     public int top() {
  //         return stack.peek();
  //     }
      
  //     public int getMin() {
  //         return minStack.peek();
  //     }
  // }

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

Example:

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);  
queue.peek();  // returns 1
queue.pop();   // returns 1
queue.empty(); // returns false

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

没有的注释的为O(1)
/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

class MyQueue1 {
    Stack<Integer> s1;
    Stack<Integer> s2;
    /** Initialize your data structure here. */
    public MyQueue() {
        s1 = new Stack();
        s2 = new Stack();
    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {
        s1.push(x);
    }
    //O(n)
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        //s1代表没进行过处理的,queue的反方向，则S2代表处理过的。
        if(!s2.isEmpty()) return s2.pop();
        else {
            while (!s1.isEmpty()) s2.push(s1.pop());
            return s2.pop();
        }
    }
    //O(n)
    /** Get the front element. */
    public int peek() {
        if(!s2.isEmpty()) return s2.peek();
        else {
            while(!s1.isEmpty()) s2.push(s1.pop());
            return s2.peek();
        }
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return s1.isEmpty() && s2.isEmpty();
    }
}


//Methods 2
class MyQueue2 {
    Stack<Integer> s1;
    Stack<Integer> s2;
    private int front;
    /** Initialize your data structure here. */
    public MyQueue() {
        s1 = new Stack();
        s2 = new Stack();
    }
    
    /** Push element x to the back of queue. */
    //O(n)
    public void push(int x) {
        if (s1.isEmpty()) {
            front = x;
        }
        while (!s1.isEmpty()) {
            s2.push(s1.pop());
        }
        s2.push(x);
        while (!s2.isEmpty()) {
            s1.push(s2.pop());
        }
    }
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        //s1代表没进行过处理的,queue的反方向，则S2代表处理过的。
        int res = s1.pop();
        if(!s1.isEmpty()) {
            front = s1.peek();
        } 
        return res;
    }
    /** Get the front element. */
    public int peek() {
        return front;
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return s1.isEmpty();
    }
}

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

Example:

MyStack stack = new MyStack();

stack.push(1);
stack.push(2);  
stack.top();   // returns 2
stack.pop();   // returns 2
stack.empty(); // returns false

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

/*
 * @lc app=leetcode.cn id=225 lang=java
 *
 * [225] 用队列实现栈
 */

// @lc code=start
import java.util.Queue;
import java.util.LinkedList;

class MyStack {
    //queue 4321
    //stack 1234
    /** Initialize your data structure here. */
    Queue<Integer> queue;
    public MyStack() {
        //前后开口，所以一个queue就可以实现
        queue = new LinkedList<>();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        queue.add(x);
        for (int i = 0; i < queue.size() - 1; i++) {
            queue.add(queue.poll());
        }
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return queue.poll();
    }
    
    /** Get the top element. */
    public int top() {
        return queue.peek();
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return queue.isEmpty();
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */
// @lc code=end

20. Valid Parentheses

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

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

Example 1:

Input: "()"
Output: true

Example 2:

Input: "()[]{}"
Output: true

Example 3:

Input: "(]"
Output: false

Example 4:

Input: "([)]"
Output: false

Example 5:

Input: "{[]}"
Output: true

/*
 * @lc app=leetcode.cn id=20 lang=java
 *
 * [20] 有效的括号
 */

// @lc code=start
//case1 ()[]{}
//stack: pop value is )

class Solution {
    public boolean isValid(String s) {
        if (s.isEmpty())
            return true;
        Stack<Character> stack  = new Stack<Character>();
        for (char c:s.toCharArray()) {
            if (c == '(')
                stack.push(')');
            else if (c == '{')
                stack.push('}');
            else if (c== '[') 
                stack.push(']');
            else if(stack.isEmpty() || c != stack.pop())//当不为左括号时候，说明c是右括号，
            //stack.pop弹出栈元素中存储的右括号元素，比较这两个右括号是否相等。
                return false;
        }
        if (stack.isEmpty())//判断相对情况下的第一个字符是否为’），｝，】‘这种类型的。
        //当stack为空时输入一个c=）时，stack内没有（与之对应，则认为false
            return true;
        return false;
    }
}

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

Note:

• Division between two integers should truncate toward zero.
• The given RPN expression is always valid. That means the expression would always evaluate to a result and there won’t be any divide by zero operation.

Example 1:

Input: ["2", "1", "+", "3", "*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Example 2:

Input: ["4", "13", "5", "/", "+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

Example 3:

Input: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
Output: 22
Explanation: 
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

逆波兰表达式：

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

• 平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
• 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点：

• 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + *也可以依据次序计算出正确结果。

• 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。

  /*
   * @lc app=leetcode.cn id=150 lang=java
   *
   * [150] 逆波兰表达式求值
   */
  
  // @lc code=start
  class Solution {
      public int evalRPN(String[] tokens) {
          Stack<Integer> stack = new Stack<>();
          for (String s : tokens) {
              if(s.equals("+")) {
                  stack.push(stack.pop() + stack.pop());
              } else if (s.equals("-")) {
                  int a = stack.pop();//先pop出来的数是减数
                  int b = stack.pop();
                  stack.push(b - a);
              } else if (s.equals("*")) {
                  stack.push(stack.pop() * stack.pop());
              } else if (s.equals("/")) {
                  int a = stack.pop();
                  int b = stack.pop();
                  stack.push(b / a);
              } else {
                  stack.push(Integer.parseInt(s));//从String转为Int
              }
          }
          return stack.pop();
      }
  }
  // @lc code=end

224. Basic Calculator

Share

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 .

Example 1:

Input: "1 + 1"
Output: 2

Example 2:

Input: " 2-1 + 2 "
Output: 3

Example 3:

Input: "(1+(4+5+2)-3)+(6+8)"
Output: 23

Note:

• You may assume that the given expression is always valid.
• Do not use the eval built-in library function.

/*
 * @lc app=leetcode.cn id=224 lang=java
 *
 * [224] 基本计算器
 */

// @lc code=start
class Solution {
    public int calculate(String s) {
        Stack<Integer> stack  = new Stack<>();
        int sign = 1;
        int res = 0;
        for (int i = 0; i < s.length(); i++) {
            //判断当前是否为数字
            if (Character.isDigit(s.charAt(i))) {
                int num = s.charAt(i) - '0';
                //判断下一位是不是还是数字，case:123
                while (i + 1 < s.length() && Character.isDigit(s.charAt(i + 1))) {
                    num = num * 10 + s.charAt(i + 1) - '0';
                    i++;
                }
                res += num * sign;
            } else if (s.charAt(i) == '+') {
                sign = 1;
            } else if (s.charAt(i) == '-') {
                sign = -1;
            } else if (s.charAt(i) == '(') {
                //1 - 2可以看成 1 + (-2)
                stack.push(res);
                stack.push(sign);//sign会先Pop出来
                //恢复到初始化状态
                res = 0;
                sign = 1;
            } else if (s.charAt(i) == ')') {
                res = res * stack.pop() + stack.pop();
            }
        }
        return res;
    }
}
// @lc code=end

161. One Edit Distance

字符串S和T只差一个距离,返回True, 否则返回False

case1:abcre Abere

case2:abdc abc

case:3 abc abdc
//TIME O(n) Math.min(s,length(), t.length());
//Space:O(1) 因为substring虽然是O(n)，但是只在return时候调用一次。

public static boolean isOneEditDistance(String s, String t) {
  //case 1:找到第一个不同，让越过去，判断后面是否相同
  //如果两个长度不等，取长的会越界，所以用Math.min()
  for (int i = 0; i < Math.min(s,length(), t.length()); i++) {
    if (s.charAt(i) != t.charAt(i)) {
      if (s.length() == t.length()) {
        return s.substring(i + 1).equals(t.substring(i + 1));
      } else if (s.length() > t.length()) {
        return s.substring(i + 1).equals(t.substring(i));
      } else {
        return t.substring(i + 1).equals(s.substring(i));
      }
    }
    // abc和abcdef,在这里判断是不是只多1个，还是多了几个
    return Math.abs(s.length() - t.length()) == 1;
  }
}

168. Excel Sheet Column Title

Given a positive integer, return its corresponding column title as appear in an Excel sheet.

For example:

1 -> A
2 -> B
3 -> C
...
26 -> Z
27 -> AA
28 -> AB 
...

Example 1:

Input: 1
Output: "A"

Example 2:

Input: 28
Output: "AB"

Example 3:

Input: 701
Output: "ZY"

/*
 * @lc app=leetcode.cn id=168 lang=java
 *
 * [168] Excel表列名称
 */

// @lc code=start
// 26Z 27AA 28AB,这里是对26的一个循环， 用%26+ 'A'算, 在26之后用/的方法
//time O(n) logN因为是/26
// Space O(n) 对应n，每次加一个字母

class Solution {
    public String convertToTitle(int n) {
        StringBuilder sb = new StringBuilder();
        while (n > 0) {
            n--;//28 % 26 =  2 + 'A' = 2 + 1 = 3 = 'C',所以Index要从0开始，但是这里对应的是A=1
            sb.append((char)('A' + n % 26));
            n /= 26;
        }
        return sb.reverse().toString();//得到的结果是反过来的
    }
}
// @lc code=end

171. Excel Sheet Column Number

Given a column title as appear in an Excel sheet, return its corresponding column number.

For example:

A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28 
...

Example 1:

Input: "A"
Output: 1

Example 2:

Input: "AB"
Output: 28

Example 3:

Input: "ZY"
Output: 701

/*
 * @lc app=leetcode.cn id=171 lang=java
 *
 * [171] Excel表列序号
 */

// @lc code=start
class Solution {
    public int titleToNumber(String s) {
        int res = 0;
        for (int i = 0; i < s.length(); i++) {
            res = res * 26 + (s.charAt(i) - 'A' + 1);//A对应的是1
        }
        return res;
    }
}
// @lc code=end

38. Count and Say

The count-and-say sequence is the sequence of integers with the first five terms as following:

1.     1
2.     11
3.     21
4.     1211
5.     111221

1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n where 1 ≤ n ≤ 30, generate the nth term of the count-and-say sequence. You can do so recursively, in other words from the previous member read off the digits, counting the number of digits in groups of the same digit.

Note: Each term of the sequence of integers will be represented as a string.

Example 1:

Input: 1
Output: "1"
Explanation: This is the base case.

Example 2:

Input: 4
Output: "1211"
Explanation: For n = 3 the term was "21" in which we have two groups "2" and "1", "2" can be read as "12" which means frequency = 1 and value = 2, the same way "1" is read as "11", so the answer is the concatenation of "12" and "11" which is "1211".

/*
 * @lc app=leetcode.cn id=38 lang=java
 *
 * [38] 外观数列
 */

// @lc code=start
class Solution {
    /**
     * 解题思路：
     * 本题的难点在于：报数的概念理解，至少我从题意中没有很清晰的理解，但是感觉像是个递推式
     * 从4->5分析，将4个每一位拆开看（个数+数字），4=1211 => 1=11，2=12，11=21，所以5=111221
     * 所以解题用循环，从1->n可求解出来
     *
     * @param n
     * @return
     */
    public String countAndSay(int n) {
        String str = "1";
        for (int i = 2; i <= n; i++) {
            StringBuilder builder = new StringBuilder();
            char pre = str.charAt(0);
            int count = 1;
            for (int j = 1; j < str.length(); j++) {
                char c = str.charAt(j);
                if (c == pre) {
                    count++;
                } else {
                    builder.append(count).append(pre);
                    pre = c;
                    count = 1;
                }
            }
            builder.append(count).append(pre);
            str = builder.toString();
        }

        return str;
    }
}
// @lc code=end