算法题目部分四：
本期来体验一下栈的理解和简单回溯等问题
题目16《包含min函数的栈》：题目地址
题解：
import java.util.Stack;
//https://www.nowcoder.com/practice/4c776177d2c04c2494f2555c9fcc1e49?
/*
栈的操作，辅助栈的加入，可以保证出栈后，辅助栈顶仍然保存的是栈内元素的最小
*/
public class 包含min函数的栈 {
Stack
Stack
public void push(int node) {
stack1.push(node);
if (stack2.isEmpty() || node < stack2.peek()){
stack2.push(node);
}else {
//此时说明栈不为空，且新添加元素值比最小值大
stack2.push(stack2.peek());
}
}
public void pop() {
//取出一个节点
stack1.pop();
stack2.pop();
}
public int top() {
//展示栈顶不删
return stack1.peek();
}
public int min() {
return stack2.peek();
}
}
题目17《栈的压入、弹出序列》：题目地址
模拟栈的压入和弹出完成判断
题解：
import java.util.Stack;
//https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?
/*
模拟一下入栈过程，期间配合出战顺序操作，观察是否可以按这个顺序完成
*/
public class 栈的压入弹出序列 {
public boolean IsPopOrder(int [] pushA,int [] popA) {
//合法性判断
if (pushA == null || popA == null || popA.length == 0 || pushA.length == 0){
return false;
}
//新建一个栈用来帮助判断
Stack
//循环判断出栈顺序
int j = 0;
for (int i = 0; i < pushA.length; i++) {
//把值按顺序压入栈
stack.push(pushA[i]);
//如果此时栈顶和出栈顺序相同说明这里开始有出栈操作了，我们出栈后再进行对比
while (!stack.isEmpty() && popA[j] == stack.peek()){
stack.pop();
j++;
}
//栈空了就跳出继续重新入剩下的栈，栈顶不相等说明这里没有继续出栈了，我们让他继续入剩下的
}
//循环走完，所有入栈元素都入了，如果栈不空说明出栈时顺序不对剩余元素无法按这个顺序出，有的元素出得早了
return stack.isEmpty();
}
}
题目18《从上往下打印二叉树》：题目地址
题解：
注意这里并没有选择用递归处理，所以当前节点不是root哦
package demo4;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.concurrent.ConcurrentLinkedQueue;
//https://www.nowcoder.com/practice/7fe2212963db4790b57431d9ed259701?
/*
先把根放进队列，然后出队时把他添加到数组，再判断根是否有左右子树进行操作
*/
public class 从上往下打印二叉树 {
public ArrayList
//合法性判断
if (root == null){
return new ArrayList<>();
}
//定义一个新的动态数组存放层序遍历的节点
ArrayList
//定义一个新的队列操作
Queue
queue.offer(root);
while (!queue.isEmpty()){
//把当前节点值插入到数组
TreeNode cur = queue.poll();
arrayList.add(cur.val);
//判断当前节点是否有左右子树,注意这里是当前节点，用的不是递归所以上面要重新把当接节点放在cur
if (cur.left != null){
queue.offer(cur.left);
}
if (cur.right != null){
queue.offer(cur.right);
}
}
//队列空了说明所有元素添加成功了返回就好了
return arrayList;
}
//题目给定二叉树
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
}
题目19《二叉搜索树的后序遍历序列》：题目地址
题解：
二叉搜索树其左子树全部小于根，又子树全部大于根
//https://www.nowcoder.com/practice/a861533d45854474ac791d90e447bafd?
/*
注意边界值处理
*/
public class 二叉搜索树的后序遍历序列 {
public boolean VerifySquenceOfBST(int [] sequence) {
//合法性判断
if (sequence.length == 0){
return false;
}
return help(sequence , 0 , sequence.length - 1);
}
//给定数组及其边界判断是否满足后序遍历结果
public boolean help(int[] arr , int start , int end){
//当区间空了时说明所有之前我们处理的数据都满足二叉搜索树结果，当然也是判出条件
if (start >= end){
return true;
}
//后序遍历最后一个就是树根
int root = arr[end];
//处理左子树情况
int i = start;
while (i < end && arr[i] < root){
i ++;
}
//此时说明遇到了大于root的值，该开始处理又子树了
for (int j = i; j < end ; j++) {
if (arr[j] < root)
return false;
}
//走到这里说明这个大树满足二叉搜索树条件，继续递归判断其左右子树是否也满足条件就好了
//左：start ～ i - 1；右：i ～ end - 1
return help(arr , start , i - 1) && help(arr , i , end - 1);
}
}
题目20《把数组排成最小的数》：题目地址
题解：
compare相关的操作后序将更新链接
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
//https://www.nowcoder.com/practice/8fecd3f8ba334add803bf2a06af1b993?
/*
使用sort重新定义排序方式
*/
public class 把数组排成最小的数 {
public String PrintMinNumber(int [] numbers) {
//合法性判断
if (numbers.length == 0){
return new String();
}
//定一个动态数组方便比较里面的值并把所有numbers的值添加到arr
ArrayList
for (int a : numbers
) {
arr.add(a);
}
//对list进行排序
Collections.sort(arr, new Comparator
@Override
public int compare(Integer o1, Integer o2) {
String s1 = o1 + "" + o2;
String s2 = o2 + "" + o1;
return s1.compareTo(s2);
}
});
//把arr添加到String
String str = new String();
for (int a : arr
) {
str += a;
}
return str;
}
}
相关文章
发表评论