牛客刷题——剑指offer(第7期）

💟💟前言
🥇作者简介：友友们大家好，我是你们的小王同学😗😗
​🥈个人主页：小王同学🚗
​🥉 系列专栏：牛客刷题专栏📖
​📑 推荐一款非常火的面试、刷题神器👉 牛客网
觉得小王写的不错的话 麻烦动动小手点赞👍 收藏⭐ 评论📄
今天给大家带来的刷题系列是：
​剑指offer 链接：👉 剑指offer

​ 里面有非常多的题库 跟面经知识 真的非常良心了！！

JZ33 二叉搜索树的后序遍历序列🎈

题目描述🎈

解题思路🎈

这道题目是输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回 true ,否则返回 false 。假设输入的数组的任意两个数字都互不相同
这道题就是中序跟后序遍历满足栈的压入弹出序列关系
如果把中序序列当做栈的压入序列，那么后序序列是该栈的一个弹出序列
而二叉搜索树的中序是排序数组

代码详解🎈

import java.util.*;
public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
       
        int arr[]=sequence.clone();
        Arrays.sort(arr);
        return IsPopOrder(arr,sequence);
        
    }
    boolean IsPopOrder(int []pushA,int []popA){
        if(pushA.length==0 || popA.length==0) return false;
        
        Stack<Integer> stack=new Stack<>();
        int popIndex=0; //用于标识弹出的序列的位置
        
        for(int x:pushA){
            stack.push(x);
            //如果栈不为空 并且栈顶元素等于弹出的序列
            while(stack.size()>0 && stack.peek()== popA[popIndex]){
                //出栈
                stack.pop();
                popIndex++;
                
            }
        }
        return stack.empty();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

JZ45 把数组排成最小的数🎈

题目描述🎈

解题思路🎈

这道题的核心思路 就是排序
只考虑首字符的大小不可靠，但是如果字符串a拼接b的得到的数字大于b拼接a，那么肯定b应该排在a的前面，我们要就按照这样的次序将排序的比较重载就可以了
还要特判 空数组的情况
最后返回的是字符串的类型
只考虑首字符的大小不可靠，但是如果字符串a拼接b的得到的数字大于b拼接a，那么肯定b应该排在a的前面，我们要就按照这样的次序将排序的比较重载就可以了。

代码详解：

import java.util.*;
import java.util.ArrayList;

public class Solution {
    public String PrintMinNumber(int [] numbers) {
        int len=numbers.length;
         //特判空数组的情况
        if(numbers==null || numbers.length==0) return "";
         String []str= new String[len];
        for(int i=0;i<len;i++){
            str[i]=numbers[i]+"";
        }  
        Arrays.sort(str,new Comparator<String>(){
            public int compare(String s1,String s2){
                return (s1+s2).compareTo(s2+s1);
            }
        });
        
        StringBuilder res=new StringBuilder();
        //字符串叠加
        for(int i=0;i<str.length;i++){
            res.append(str[i]);
           
        }
         return res.toString();
      
        
        
        
        
        
            

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

​​
牛客是一款不论是面试 还是刷题 都是非常有用的 还等什么注册其来吧👉👉 牛客网

​

​

​