本文已收录于专栏

🌻

《刷题笔记》

前言

题目来源参考阿秀学长的刷题笔记，小戴只是把 C++的题解改成了 Java版本，并整理了其他思路，便于自己的学习~

如果解题有更好的方法，本文也会及时进行更新~

希望对你有帮助~ 一起加油哇~

🎨 1、包含min函数的栈

牛客原题链接

题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的 min 函数，输入操作时保证 pop、top 和 min 函数操作时，栈中一定有元素。

此栈包含的方法有：
push(value):将value压入栈中
pop():弹出栈顶元素
top():获取栈顶元素
min():获取栈中最小元素

思路（双栈法）

使用一个栈记录进入栈的元素，正常进行push、pop、top操作。使用另一个栈记录每次push进入的最小值。

每次push元素的时候与第二个栈的栈顶元素比较，若是较小，则进入第二个栈，若是较大，则第二个栈的栈顶元素再次入栈，因为即便加了一个元素，它依然是最小值。于是，每次访问最小值即访问第二个栈的栈顶。

import java.util.Stack;public class Solution {// 用于栈的 push和popStack<Integer> s1 = new Stack<Integer>();// 用来存最小minStack<Integer> s2 = new Stack<Integer>();public void push(int node) {s1.push(node);if(s2.isEmpty() || s2.peek()>node){s2.push(node);}else{s2.push(s2.peek());}}public void pop() {s1.pop();s2.pop();}public int top() {return s1.peek();}public int min() {return s2.peek();}
}

🎨 2、栈的压入弹出序列

牛客原题链接

题目描述

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

思路（辅助栈）

import java.util.*;public class Solution {public boolean IsPopOrder(int [] pushA,int [] popA) {int n = pushA.length;int popIndex = 0; //用于遍历popA// 辅助栈Stack<Integer> s = new Stack<Integer>();for(int i=0; i<n; i++){s.push(pushA[i]); // 先入栈while(popIndex<n && !s.empty() && s.peek()==popA[popIndex]){s.pop();popIndex++;}}return s.isEmpty();}
}

🎨 3、从上往下打印二叉树

牛客原题链接

题目描述

不分行从上往下打印出二叉树的每个节点，同层节点从左至右打印。例如输入

思路（层次遍历）

首先判断二叉树是否为空，空树没有遍历结果

建立辅助队列，根节点首先进入队列。不管层次怎么访问，根节点一定是第一个，那它肯定排在队伍的最前面

每次遍历队首节点，如果它们有子节点，依次加入队列排队等待访问

import java.util.*;
/
public class TreeNode {int val = 0;TreeNode left = null;TreeNode right = null;public TreeNode(int val) {this.val = val;}}
*/
public class Solution {public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {// 数组存储遍历结果ArrayList<Integer> res = new ArrayList<>();// 为空，返回空数组，返回null不通过if(root == null) return res;// 队列存储Queue<TreeNode> q = new LinkedList<>();q.add(root);while(!q.isEmpty()){TreeNode cur = q.poll();res.add(cur.val);// 若是左右孩子存在，则存入左右孩子作为下一个层次if(cur.left != null){q.add(cur.left);}if(cur.right != null){q.add(cur.right);}}return res;}
}

🎨 4、二叉搜索树的后序遍历序列

牛客原题链接

题目描述

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回 true ,否则返回 false 。假设输入的数组的任意两个数字都互不相同

思路（递归）

后续遍历是左节点-右节点-中节点，由此判断最后一个元素为根节点，

二叉搜索树是指父亲节点大于左子树中的全部节点，但是小于右子树中的全部节点的树，这样我们可以确定左右子树

先找到根节点，再从数组第一位从左往右遍历，找到第一个比根节点大的数，那么这个数之后就是根节点的右子树，

遍历右子树，若右子树中有比根节点小的数，这样是不符合二叉搜索树的定义的，所以返回false

最后，递归根节点的左右子树

public class Solution {public boolean VerifySquenceOfBST(int [] sequence) {if(sequence.length == 0) return false;return order(sequence,0,sequence.length-1);}public boolean order(int[] sequence,int l,int r){// 剩余一个节点或没有节点的时候，返回trueif(l >= r) return true;// 根节点int root = sequence[r];int p = l;// 从左向右遍历，找第一个比root大的元素while(root > sequence[p]) p++;// 在p到r-1这个左子树范围内判断是否存在比root小的树for(int i=p; i<r; i++){if(sequence[i] < root){return false;}}return order(sequence,l,p-1) && order(sequence,p,r-1);}
}