Java教程

Day04_剑指Offer

本文主要是介绍Day04_剑指Offer,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

Day04_剑指Offer

得到一点小启发,顺序的就会想到二分 树的就想到递归 倒序的就想到栈。

通过每天做做题,第二天重新思考前一天学的算法题,每天都有进步。加油

分享一句话:路都是一步一个脚印走出来的,没有人可以突然暴富,只有厚积薄发才能走得更远。加油!!

今天的三道题都用到二分法

package com.sorrymaker.day2804;

import org.junit.Test;

/**
 * 找出一个长度为n数组nums里面的 重复数字,只要重复了就拿出来。
 *
 * 在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。
 * 数组中某些数字是重复的,但不知道有几个数字重复了,
 * 也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
 * @Author nextGame
 * @Date 2021/8/15 15:32
 * @Version 1.0
 */
public class findRepeatNumber {


    @Test
    public void test(){
        int[] nums ={3, 4, 2, 1, 0, 1};
        System.out.println(findRepeatNumber(nums));
    }

    public int findRepeatNumber(int[] nums) {
        //这个是索引,从0,开始
        int i = 0;
        while(i < nums.length) {
            //假如数组中的数据nums[i] == i ; 即是nums[1] = 1的时候
            if(nums[i] == i) {
                //索引加1,继续遍历循环。因为true的话,说明,现在的索引和对应的值是对应的。
                i++;
                continue;
            }
            //这里就要拆封一下了。我们首先来看,
            //当nums[i] = i ; nums[num[i]] ==>> nums[i]  == nums[i]这里就会成立。
            //为什么这里会返回呢?因为我们上面的if语句已经判断过了,假如索引 == num[i] ,我们就会i++,并继续循环。
            // 即是出现重复的值,我们就返回这个值出来。
            //因为索引是从0开始的
            if(nums[nums[i]] == nums[i]) {
                return nums[i];
            }

            //这里下面就是帮助我们排序数组把,把

            //存放nums数组 的 i索引的数字。
            int tmp = nums[i];
            //将nums索引位temp 的数值 赋值给 nums 索引为 i的 。
            nums[i] = nums[tmp];
            //这里就是把对应位置的num[tmp] = tmp
            nums[tmp] = tmp;
        }
        return -1;
    }
}


    /**
     *        太慢太垃圾了,更新一个又快又猛的。
     *         int count=0;
     *         for (int i = 0; i < nums.length; i++) {
     *             for (int j = i+1;j<nums.length;j++){
     *                 if(nums[i] == nums[j]){
     *                     return count = nums[j];
     *                 }
     *
     *             }
     *         }
     *         return count;
  
  */

https://pic.leetcode-cn.com/45a6303cd3ab50036a99ae89e2b0458f9b4885bb9d089997dfc0e5851a6a6300-Picture7.png

package com.sorrymaker.day2804;


/**
 * 排序数组中的搜索问题,首先想到 二分法 解决
 * @Author nextGame
 * @Date 2021/8/15 17:28
 * @Version 1.0
 */
public class MissingNumber {

    public int missingNumber(int[] nums) {
        //左边界 i ,右边界 j
        int i = 0, j = nums.length - 1;
        while (i <= j) {
            //二分法
            int m = (i + j) / 2;
            if (nums[m] == m) {
                i = m + 1;
            } else {
                j = m - 1;
            }
        }
        return i;
    }
}

https://pic.leetcode-cn.com/515ad046b4363de9324acc0ce74d9fa9048d5526c66a91539b99c26fbe4a49cb-Picture2.png

package com.sorrymaker.day2804;

import org.junit.Test;

/**
 * 排序数组记得用二分法,记得用二分法,记得,记得噢噢噢噢
 * 二分法,就是找到想要找到的数字的左边和右边,右边-左边-1就是target出现的频率了。
 * 这道题用的是优化的二分法,由于是排序数组,只需要找到有边界,和target-1的右边界,就是出现的次数了。
 * 例如 target = 8, target-1 = 7 。  target的右边界为9,target-1 的有边界为8,
 * 然后重复次数 =  target右边界 - target-1的右边界 。
 * @Author nextGame
 * @Date 2021/8/15 16:42
 * @Version 1.0
 */
public class Search {

    @Test
    public void test() {
        int[] nums = {10, 11, 12, 13, 14, 15};
        int target = 10;
        System.out.println(search(nums, target));
    }

    public int search(int[] nums, int target) {
        return count(nums,target)-count(nums,target-1);
    }

    int count(int[] nums, int target) {
        //i 和 j分别是数组的起始索引和结尾索引。
        int i = 0, j = nums.length - 1;
        //这里的i和j分别是左右边界,左边始终小于等于右边
        while(i <= j) {
            // 二分得到的值。
            int m = (i + j) / 2;
            //当数组在m索引的值 <=目标值,说明,左边还可以在缩小一格,即i= m+1
            if(nums[m] <= target) {
                i = m + 1;
            } else {
            //当出先数组在m索引的值 >目标值,说明,右边可以在缩小一点,即j=m-1。
                j = m - 1;
            }
        }
        return i;
    }

}

/**
 * 弱智写法
 * int count=0;
 * for(int n:nums){
 * if(n==target){
 * count++;
 * }
 * }
 * return count;
 * }
 */
这篇关于Day04_剑指Offer的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!