Sword finger offer 09.30 Stack

subject 1:

20. Valid parenthesis https://leetcode-cn.com/problems/valid-parentheses/

Code :

class Solution {
    public boolean isValid(String s) {
        char[] ch = s.toCharArray();// Convert to character array 
        Stack<Character> st=new Stack<Character>();
        boolean flag=false;
        for(int i=0;i<ch.length;i++){
            if(st.empty()){
                // If the stack is empty   The stack 
                st.push(ch[i]);
            }else{
                // Determine whether the brackets match 
                flag=isMatching(st.peek(),ch[i]);
                if(flag){
                    // Parentheses matching 
                    st.pop();
                }else{
                    // Bracket mismatch 
                    st.push(ch[i]);
                }
            }
        }
        if(st.empty())
            return true;
        else
            return false;
    }
    boolean isMatching(char a,char b){
        if(a+1==b||a+2==b)
            return true;
        else
            return false;
    }
}

result :

subject 2:

The finger of the sword Offer 09. Queues are implemented with two stacks https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/

  Code :

class CQueue {
    Stack<Integer> st1;
    Stack<Integer> st2;
    public CQueue() {
        st1=new Stack<Integer>();
        st2=new Stack<Integer>();
    }
    
    public void appendTail(int value) {
        st1.push(value);
    }
    
    public int deleteHead() {
        if(st2.empty()){
            // If st2 It's empty.   Will s1 Some of them pour in 
            while(!st1.empty())
                st2.push(st1.pop());
        }
        if(!st2.empty())// If it's over 2 Non empty   be pop
            return st2.pop();
        else// If it's over 2 Or empty?   Then return to -1
            return -1;
    }
}

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.appendTail(value);
 * int param_2 = obj.deleteHead();
 */

result :

subject 3:

  The finger of the sword Offer 30. contain min Function of the stack https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/

  Code 1 :

class MinStack {
    Stack<Integer> st1;
    Stack<Integer> st2;
    int min=(int)-Math.pow(2,31)-1;
    /** initialize your data structure here. */
    public MinStack() {
        st1=new Stack<Integer>();
        st2=new Stack<Integer>();
    }
    
    public void push(int x) {
        // use st2 Synchronously maintain the minimum stack 
        min=min<x?min:x;
        st1.push(x);
        st2.push(min);
    }
    
    public void pop() {
        st1.pop();
        st2.pop();
        // Remember to update the minimum value synchronously when bouncing the stack 
        if(!st2.empty())
            min=st2.peek();
        else
            min=(int)-Math.pow(2,31)-1;
    }
    
    public int top() {
        return st1.peek();
    }
    
    public int min() {
        return st2.peek();
    }
}
/**
 * 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.min();
 */

Code 2 : Reference others Not through min Update minimum

class MinStack {
    Stack<Integer> A, B;
    public MinStack() {
        A = new Stack<>();
        B = new Stack<>();
    }
    public void push(int x) {
        A.push(x);
        if(B.empty() || B.peek() >= x)
            B.push(x);
    }
    public void pop() {
        if(A.pop().equals(B.peek()))
            B.pop();
    }
    public int top() {
        return A.peek();
    }
    public int min() {
        return B.peek();
    }
}

result :