每日一题之《剑指offer》20,21,22题

简书原创文章，未经本人允许，不得转载

第二十题：包含min函数的栈

难易度：⭐

题目描述：
定义栈的数据结构
请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））
注意：保证测试中不会当栈为空的时候，对栈调用pop()或者min()或者top()方法

本题非常简单，在原有数据栈的基础上，再设计一个minStack，每次都随着数据栈对元素一同入栈或者出栈，不过，每次minStack都对当前的数据栈中最小的元素进行操作即可，代码及思路都非常简单，代码如下：

import java.util.Stack;

public class Solution {

    private Stack<Integer> userStack = new Stack<>();
    private Stack<Integer> minStack = new Stack<>();
    
    public void push(int node) {
        if(minStack.isEmpty()){
            minStack.push(node);
        }else{
            if(node < minStack.peek()){
                minStack.push(node);
            }else{
                minStack.push(minStack.peek());
            }
        }
        userStack.push(node);
    }
    
    public void pop() {
        if(!userStack.isEmpty()){
            userStack.pop();
            minStack.pop();
        }else{
            throw new RuntimeException("stack is empty");
        }
    }
    
    public int top() {
        if(!userStack.isEmpty()){
            return userStack.peek();
        }else{
            throw new RuntimeException("stack is empty");
        }
    }
    
    public int min() {
        if(!minStack.isEmpty()){
            return minStack.peek();
        }else{
            throw new RuntimeException("stack is empty");
        }
    }
}

第二十一题：栈的压入弹出序列

难易度：⭐⭐

输入两个整数序列
第一个序列表示栈的压入顺序
请判断第二个序列是否可能为该栈的弹出顺序
假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序;
序列4,5,3,2,1是该压栈序列对应的一个弹出序列;
序列4,3,5,2,1是该压栈序列对应的一个弹出序列;
但4,3,5,1,2就不可能是该压栈序列的弹出序列

拿栈的压入序列1,2,3,4,5 与弹出序列4,5,3,2,1举例说明

剑指offer原图

通过总结上述分析的过程，我们可以这样设计程序：
设计一个helpStack栈
对压入序列进行遍历，遍历的同时，压入到helpStack栈中，如果当前helpStack栈不为空，我们就看一看helpStack栈顶和弹出序列的索引指向的元素是否相等，如果相等，helpStack pop 并且弹出序列的索引++。直到对压入序列的遍历结束，我们只需要看一看helpStack是否为空即可，如果helpStack为空，则说明弹出序列正确，如果helpStack不为空，则弹出序列错误。如果不理解我这种思路，不妨动手举几个例子，画一画写一写感受一番；代码如下：

import java.util.Stack;

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        if(pushA == null || popA == null || pushA.length == 0 || popA.length == 0 || pushA.length != popA.length){
            return false;
        }
        Stack<Integer> helpStack = new Stack<>();
        int pushIndex = 0;
        int popIndex = 0;
        for(;pushIndex < pushA.length;pushIndex++){
            helpStack.push(pushA[pushIndex]);
            while(!helpStack.isEmpty() && helpStack.peek() == popA[popIndex]){
                popIndex++;
                helpStack.pop();
            }
        }
        return helpStack.isEmpty();
    }
}

第二十二题：从上往下打印二叉树

难易度：⭐

给出TreeNode类：
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}
要求：
从上往下打印出二叉树的每个节点，同层节点从左至右打印。

本题就是层序遍历二叉树，使用队列结构，真的没什么好说的... 这种关于二叉树的遍历问题，应该熟练到白板秒写的程度

啥也不说了，都在代码里了自己看吧

import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;

public class Solution {
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        if(root == null){
            return arrayList;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            root = queue.poll();
            arrayList.add(root.val);
            if(root.left != null){
                queue.offer(root.left);
            }
            if(root.right != null){
                queue.offer(root.right);
            }
        }
        return arrayList;
    }
}