小试牛刀——牛客篇

青旅半醒 2023-09-27 08:39 125阅读 0赞

![在这里插入图片描述][b58e14a606c14e76832adc977e9ba0ba.gif_pic_center]

>  个人主页：[熬夜磕代码丶][Link 1]  
>  作品专栏: [java se][]  
>  我变秃了，也变强了  
> 给大家介绍一款程序员必备刷题平台——牛客网  
> [点击注册一起刷题收获大厂offer吧][offer]  
> ![在这里插入图片描述][45806c90199243eab295ada6d8239e84.png]

#### 文章目录 ####

*  一、消失的数字
 *  二、轮转数组
 *  三、存在重复元素
 *  四、寻找峰值
 *  五、珠玑妙算游戏

## 一、消失的数字 ##

数组 nums 包含从 0 到 n 的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。在 O(n)时间内完成  
![在这里插入图片描述][9b12328b860943beb371f8b5dcd6136a.png]  
**1.异或运算:**

public int missingNumber(int[] nums) {
        
            int[] arr = new int[nums.length + 1];
            int sum = 0;
            for (int i = 0; i < arr.length; i++) {
        
                sum ^= i;
            }
            for (int i = 0; i < nums.length ; i++) {
        
                sum ^= nums[i];
            }
            return sum;
        }

**2.空间换时间:**

public int missingNumber1(int[] nums) {
        
            int[] arr = new int[nums.length+1];
            for (int i = 0; i < nums.length; i++) {
        
                arr[nums[i]] = 1;
            }
            for (int i = 0; i < arr.length; i++) {
        
                if(arr[i] != 1) {
        
                    return i;
                }
            }
            return -1;
        }

## 二、轮转数组 ##

给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数  
![在这里插入图片描述][a644cedcd7134da68d48f46ebc841499.png]  
这是之前写过一篇专门是旋转数组的:[旋转数组三种方式][Link 2]  
上面的思路是针对于左旋数组，对右旋数组只需要稍加修改即可

public static void reverse(int[] arr,int left,int right) {
        
            while(left < right) {
        
                int ret = arr[left];
                arr[left] = arr[right];
                arr[right] = ret;
                left++;
                right--;
            }
        }
        public static void rotate(int[] nums, int k) {
        
            k = k % nums.length;
            reverse(nums,0,nums.length-1);
            reverse(nums,0,k-1);
            reverse(nums,k,nums.length-1);
    
            System.out.println(Arrays.toString(nums));
        }

## 三、存在重复元素 ##

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false

public boolean containsDuplicate(int[] nums) {
        
            HashMap<Integer,Integer> map = new HashMap<>();
            for (int i = 0; i < nums.length; i++) {
        
                if(map.containsKey(nums[i])) {
        
                    return true;
                }
                map.put(nums[i],i);
            }
            return false;
        }

## 四、寻找峰值 ##

给定一个长度为n的数组nums，请你找到峰值并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个所在位置即可。  
1.峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于  
2.假设 nums\[-1\] = nums\[n\] = -\\infty−∞  
3.对于所有有效的 i 都有 nums\[i\] != nums\[i + 1\]  
4.你可以使用O(logN)的时间复杂度实现此问题吗？  
![在这里插入图片描述][ca08613bb4934864ba90cad37b8f1b6f.png]  
![在这里插入图片描述][780fb66e94994e44971e777950f1a8eb.png]  
![在这里插入图片描述][56b1cd34a4b447c78c2723d9e685c71e.png]

public static int findPeakElement (int[] nums) {
        
            if(nums == null || nums.length == 0) {
        
                return -1;
            }
            if(nums.length == 1) {
        
                return 0;
            }
            if(nums[0] > nums[1]) {
        
                return 0;
            }
            if(nums[nums.length-1] > nums[nums.length-2]) {
        
                return nums.length - 1;
            }
            int left = 0;
            int right = nums.length - 1;
            while(left < right) {
        
                int mid = (left + right) / 2;
                if(nums[mid] < nums[mid+1]) {
        
                    left = mid + 1;
                }else {
        
                    right = mid;
                }
            }
            return left;
        }

## 五、珠玑妙算游戏 ##

计算机有4个槽，每个槽放一个球，颜色可能是红色（R）、黄色（Y）、绿色（G）或蓝色（B）。例如，计算机可能有RGGB 4种（槽1为红色，槽2、3为绿色，槽4为蓝色）。作为用户，你试图猜出颜色组合。打个比方，你可能会猜YRGB。要是猜对某个槽的颜色，则算一次“猜中”；要是只猜对颜色但槽位猜错了，则算一次“伪猜中”。注意，“猜中”不能算入“伪猜中”。  
给定一种颜色组合solution和一个猜测guess，编写一个方法，返回猜中和伪猜中的次数answer，其中answer\[0\]为猜中的次数，answer\[1\]为伪猜中的次数。

public static int[] masterMind(String solution, String guess) {
        
            int[] arr = new int[2];
            char[] ch = solution.toCharArray();
            char[] c = guess.toCharArray();
            for (int i = 0; i < c.length; i++) {
        
                if(c[i] == ch[i]) {
        
                    arr[0]++;
                    ch[i] = 0;
                    c[i] = 1;
                }
                }
            for (int i = 0; i < c.length; i++) {
        
                for (int j = 0; j < guess.length(); j++) {
        
                    if(c[i] == ch[j]) {
        
                        ch[j] = 0;
                        arr[1]++;
                        break;
                    }
                }
            }
            return arr;
        }

[b58e14a606c14e76832adc977e9ba0ba.gif_pic_center]: https://img-blog.csdnimg.cn/b58e14a606c14e76832adc977e9ba0ba.gif#pic_center
[Link 1]: https://blog.csdn.net/buhuisuanfa?spm=1018.2226.3001.5343
[java se]: https://blog.csdn.net/buhuisuanfa/category_11932688.html?spm=1001.2014.3001.5482
[offer]: https://www.nowcoder.com/link/pc_csdncpt_bhsf_jzsf
[45806c90199243eab295ada6d8239e84.png]: https://img-blog.csdnimg.cn/45806c90199243eab295ada6d8239e84.png
[9b12328b860943beb371f8b5dcd6136a.png]: https://img-blog.csdnimg.cn/9b12328b860943beb371f8b5dcd6136a.png
[a644cedcd7134da68d48f46ebc841499.png]: https://img-blog.csdnimg.cn/a644cedcd7134da68d48f46ebc841499.png
[Link 2]: http://t.csdn.cn/PBiCz
[ca08613bb4934864ba90cad37b8f1b6f.png]: https://img-blog.csdnimg.cn/ca08613bb4934864ba90cad37b8f1b6f.png
[780fb66e94994e44971e777950f1a8eb.png]: https://img-blog.csdnimg.cn/780fb66e94994e44971e777950f1a8eb.png
[56b1cd34a4b447c78c2723d9e685c71e.png]: https://img-blog.csdnimg.cn/56b1cd34a4b447c78c2723d9e685c71e.png