牛客网——刷题篇

今天药忘吃喽~ 2023-10-10 14:51 55阅读 0赞

![ced485cbb11e458d81a746890b32cf3f.gif][]

> 作者：敲代码の流川枫
> 
> 博客主页：[流川枫的博客][Link 1]
> 
> 专栏：[和我一起学java][java]
> 
> 语录：Stay hungry stay foolish
> 
> 工欲善其事必先利其器，给大家介绍一款超牛的斩获大厂offer利器——牛客网
> 
> [点击免费注册和我一起刷题吧][Link 2]

![885eec0aceee462b84c51806036354ca.png][]

**文章目录**

比较版本号

二叉树的中序遍历

数组中只出现一次的两个数字

合并区间

--------------------

## 比较版本号 ##

> 描述
> 
> 牛客项目发布项目版本时会有版本号，比如1.02.11，2.14.4等等
> 
> 现在给你2个版本号version1和version2，请你比较他们的大小
> 
> 版本号是由修订号组成，修订号与修订号之间由一个"."连接。1个修订号可能有多位数字组成，修订号可能包含前导0，且是合法的。例如，1.02.11，0.1，0.2都是合法的版本号
> 
> 每个版本号至少包含1个修订号。
> 
> 修订号从左到右编号，下标从0开始，最左边的修订号下标为0，下一个修订号下标为1，以此类推。
> 
> 比较规则：
> 
> 一. 比较版本号时，请按从左到右的顺序依次比较它们的修订号。比较修订号时，只需比较忽略任何前导零后的整数值。比如"0.1"和"0.01"的版本号是相等的
> 
> 二. 如果版本号没有指定某个下标处的修订号，则该修订号视为0。例如，"1.1"的版本号小于"1.1.1"。因为"1.1"的版本号相当于"1.1.0"，第3位修订号的下标为0，小于1
> 
> 三. version1 > version2 返回1，如果 version1 < version2 返回-1，不然返回0.
> 
> 数据范围：
> 
> 1 <= version1.length, version2.length <= 10001<=version1.length,version2.length<=1000
> 
> version1 和 version2 的修订号不会超过int的表达范围，即不超过 32 位整数 的范围  
> 进阶： 时间复杂度 O(n)O(n)

![716cf01d9b5141dbbe0796dc79379a8c.png][]

知识点：字符串，双指针

题解：

import java.util.*;
    
    public class Solution {
        
        public int compare (String version1, String version2) {
            // write code here
            String[] numsOfV1 = version1.split("\\."); // 记得这里分割的时候需要加两个斜杠
            String[] numsOfV2 = version2.split("\\.");
            
            int index = 0;
            
            while (index < numsOfV1.length && index < numsOfV2.length) {
                int num1 = Integer.parseInt(numsOfV1[index]);
                int num2 = Integer.parseInt(numsOfV2[index]);
                if (num1 > num2) {
                    return 1;
                } else if (num1 < num2) {
                    return -1;
                }
                index ++;
            }
            
            while (index < numsOfV1.length) {
                int num1 = Integer.parseInt(numsOfV1[index]);
                if (num1 > 0) {
                    return 1;
                }
                index ++;
            }
            
            while (index < numsOfV2.length) {
                int num2 = Integer.parseInt(numsOfV2[index]);
                if (num2 > 0) {
                    return -1;
                }
                index ++;
            }
            
            return 0;
        }
    }

## 二叉树的中序遍历 ##

> 描述
> 
> 给定一个二叉树的根节点root，返回它的中序遍历结果。
> 
> 数据范围：树上节点数满足 0 \\le n \\le 10000≤n≤1000，树上每个节点的值满足 0 \\le val \\le 10000≤val≤1000  
> 进阶：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)

![e7d76500047e47f58e023e629c594e29.png][]

知识点：树，递归，广度优先搜索(BFS)

题解：

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 {
        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         *
         * 
         * @param root TreeNode类 
         * @return int整型一维数组
         */
        public int[] inorderTraversal (TreeNode root) {
            // write code here
            if(root == null)return new int[0];
            ArrayList<Integer> ans = new ArrayList<>();
            inOrder(root, ans);
            int[] res = new int[ans.size()];
            int i=0;
            for(int n: ans){
                res[i++] = n;
            }
            return res;
        }
        public void inOrder(TreeNode node, ArrayList<Integer> ans){
            if(node == null)return;
            inOrder(node.left, ans);
            ans.add(node.val);
            inOrder(node.right, ans);
        }
    }

## 数组中只出现一次的两个数字 ##

> 描述
> 
> 一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
> 
> 数据范围：数组长度 2\\le n \\le 10002≤n≤1000，数组中每个数的大小 0 < val \\le 10000000<val≤1000000  
> 要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
> 
> 提示：输出时按非降序排列。

![d46ca4f3a18145969a730c66a4304353.png][]

知识点：位运算，哈希

题解：

import java.util.*;
    
    
    public class Solution {
        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         *
         * 
         * @param array int整型一维数组 
         * @return int整型一维数组
         */
        public int[] FindNumsAppearOnce (int[] array) {
            // write code here
            int tmp = 0, n = array.length;
            for(int i=0; i<n; i++){
                tmp ^= array[i];
            }
            int div = 1;
            while(tmp != 0){
                if((tmp & 1) == 1) div <<= 1;
                tmp >>= 1;
            }
            int a = 0, b = 0;
            for(int i=0; i<n; i++){
                if((array[i] & div) != 0) a ^= array[i];
                else b ^= array[i];
            }
            return new int[]{b, a};
        }
    }

## 合并区间 ##

> 描述
> 
> 给出一组区间，请合并所有重叠的区间。
> 
> 请保证合并后的区间按区间起点升序排列。
> 
> 数据范围：区间组数 0 \\le n \\le 2 \\times 10^50≤n≤2×105，区间内 的值都满足 0 \\le val \\le 2 \\times 10^50≤val≤2×105
> 
> 要求：空间复杂度 O(n)O(n)，时间复杂度 O(nlogn)O(nlogn)
> 
> 进阶：空间复杂度 O(val)O(val)，时间复杂度O(val)O(val)

![55280c61839f48dbbd2122d5305903fe.png][]

知识点：排序，数组

题解：

import java.util.*;
    /**
     * Definition for an interval.
     * public class Interval {
     *     int start;
     *     int end;
     *     Interval() { start = 0; end = 0; }
     *     Interval(int s, int e) { start = s; end = e; }
     * }
     */
    public class Solution {
        public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
            if (intervals.size() == 0) {
                return new ArrayList<>();
            }
            Collections.sort(intervals, new Comparator<Interval>() {
                public int compare(Interval o1, Interval o2) {
                    if (o1.start != o2.start) {
                        return o1.start - o2.start;
                    } else {
                        return o1.end - o2.end;
                    }
                }
            });
            
            ArrayList<Interval> result = new ArrayList<>();
            result.add(intervals.get(0));
            int count = 0;
            for (int i = 1; i < intervals.size(); i++) {
                Interval o1 = intervals.get(i);
                Interval origin = result.get(count);
                if (o1.start > origin.end) {
                    result.add(o1);
                    count++;
                } else {
                    result.remove(count);
                    Interval s = new Interval(origin.start, o1.end);
                    if (o1.end < origin.end) {
                        s.end = origin.end;
                    }
                    result.add(s);
                }
            }
            return result;
            
        }
    }

> “ 本期的分享就到这里了， 记得给博主一个三连哈，你的支持是我创作的最大动力！

![ced485cbb11e458d81a746890b32cf3f.gif][]

[ced485cbb11e458d81a746890b32cf3f.gif]: https://img-blog.csdnimg.cn/ced485cbb11e458d81a746890b32cf3f.gif
[Link 1]: https://blog.csdn.net/chenchenchencl?spm=1011.2421.3001.5343
[java]: https://blog.csdn.net/chenchenchencl/category_11932758.html
[Link 2]: https://www.nowcoder.com/link/pc_csdncpt_qdmdlcf_c
[885eec0aceee462b84c51806036354ca.png]: https://img-blog.csdnimg.cn/885eec0aceee462b84c51806036354ca.png
[716cf01d9b5141dbbe0796dc79379a8c.png]: https://img-blog.csdnimg.cn/716cf01d9b5141dbbe0796dc79379a8c.png
[e7d76500047e47f58e023e629c594e29.png]: https://img-blog.csdnimg.cn/e7d76500047e47f58e023e629c594e29.png
[d46ca4f3a18145969a730c66a4304353.png]: https://img-blog.csdnimg.cn/d46ca4f3a18145969a730c66a4304353.png
[55280c61839f48dbbd2122d5305903fe.png]: https://img-blog.csdnimg.cn/55280c61839f48dbbd2122d5305903fe.png