剑指offer 09 用两个栈实现队列

class CQueue {
    // stack 的声明必须是公共的，否则后续方法无法调用
    Stack<Integer> stack1;
    Stack<Integer> stack2;

    //CQueue 就是为了新建对象
    public CQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }
    
    public void appendTail(int value) {
        stack1.push(value);
    }
    
    public int deleteHead() {
        //当stack2时空，先判断stack1是否空，是 -> 返回-1 
        //                              否 ->  开始转移
        if(stack2.isEmpty()){

            if(stack1.isEmpty()){
                return -1;
            }

            while(!stack1.isEmpty()){
            int temp = stack1.pop();
            stack2.push(temp);
            }
        }
        return stack2.pop();
        
    }
}

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

剑指offer 30 包含min函数的栈

最小栈

class MinStack {
    Stack<Integer> stack1;
    Stack<Integer> stack2;
    /** initialize your data structure here. */
    public MinStack() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }
    
    public void push(int x) {
        stack1.push(x);
        // 要 >=, 例如，push进的两个2都为最小，stack2若不同步，则在后续min操作会输出错误结果
        if(stack2.isEmpty()||stack2.peek() >= x){
            stack2.push(x);
        }
    }
    
    //如果stack1 顶端pop的恰好是最小值，stack2 要同步
    public void pop() {
        // stack1.pop(); 这里无序加，因为在下面判断中，stack1已经删除顶端了
        // 必须用equals
        if(stack2.peek().equals(stack1.pop())){
            stack2.pop();
        }
    }
    
    public int top() {
        int top = stack1.peek();
        return top;
    }
    
    public int min() {
        return stack2.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();
 */

剑指offer 31 栈的压入，弹出序列
这是第一次自己的想法做出的中等难度的题，希望越来越好了 :)

栈的压入，弹出序列

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        if(pushed.length != popped.length) return false;
        Stack<Integer> stack1 = new Stack<>();

        // 把pushed每一个元素都push进stack1中，过程中如果遇到poped首个元素，则pop掉
        // 对照最后stack1是否为空且j指针完全遍历
        int j = 0;
        for(int i: pushed){
            stack1.push(i);
            while(stack1.peek().equals(popped[j])){
                stack1.pop();
                j++;
                //勿忘break
                if(stack1.isEmpty()) break;
                }
        }
        if(stack1.isEmpty() && j == popped.length) return true;
        return false;
    }
}

剑指offer 58-i 翻转单词顺序
String.trim(); 去除前后的空格
对于.equals 和 == 之间区别的讨论
String和StringBuilder和StringBuffer之间的区别

class Solution {
    public String reverseWords(String s) {
        String[] words = s.split(" ");
        StringBuilder ans = new StringBuilder();
        for(int i = words.length-1; i>=0; i--){
            //要用equals
            if(!words[i].equals("")){
                ans.append(words[i]);
                ans.append(" ");
            }
        }
        return ans.toString().trim();
    }
}

剑指offer 59-i 滑动窗口最大值

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums == null) return new int[0];
        if(nums.length == 0 || k == 1) return nums;
        int[] ans = new int[nums.length - k + 1];

        //取前k个最大值
        int curMax = Integer.MIN_VALUE;
        for(int i=0; i<k; i++){
            if(curMax < nums[i]) curMax = nums[i];
        }
        ans[0] = curMax;

        for(int i=k; i < nums.length; i++){
            /*如果取走的是最大值 

              0 1 2 3 4 5 6 7   <- i index 
             [1,3,4,2,1,9,4,10] k=3 len=8
              |     |
              | ans[i-k+1] = ans[1] 第一次移动
            nums[i-k] = nums[0]
            
            */ 
            if(curMax == nums[i-k]){
                curMax = nums[i-k+1];
                //重新在窗口中找最大值
                for(int j=i-k+1; j<=i; j++){
                    curMax = Math.max(curMax,nums[j]);
                }
            }
            if(curMax < nums[i]) curMax = nums[i];
            ans[i-k+1] = curMax;
        }
        return ans;

    }
}