算法刷题-Day01

• • • 1. 二分查找
    • 2. 第一个错误版本
    • 3. 搜素插入位置
    • 4. 使用到的判空类

1. 二分查找

题目描述

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

输入示例

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

思路讲解和代码实现

package com.why.day01;

import com.sun.media.sound.RIFFInvalidDataException;
import com.why.common.CheckEmpty;

/**
 * @ClassName：BinarySearch
 * @Description：todo 二分查找
 *
 * 题目：
 * 给定一个n个元素有序的（升序）整型数组nums 和一个目标值target ，
 * 写一个函数搜索nums中的 target，
 * 如果目标值存在返回下标，否则返回 -1。
 *
 * 测试用例：
 *  输入: nums = [-1,0,3,5,9,12], target = 9
 *  输出: 4
 *  解释: 9 出现在 nums 中并且下标为 4
 *
 * @Author: why
 * @DateTime：2021/10/29 17:21
 */
public class BinarySearch {

    /**
     * 思路：
     *  1. 确定中间值 mid
     *  2. target与 mid 比较
     *  3. 若 target == mid ，返回 mid 下标
     *  4. 若 target < mid ，左递归查找
     *  5. 若 target > mid ，有递归查找
     *  6. 若查找到边界则返回 -1 ，未找到
     * @param nums
     * @param target
     * @return
     */
    private static int binarySearch(int[] nums,int target,int left,int right){
        //检查 nums 的合法性
        CheckEmpty<int[]> checkEmpty = new CheckEmpty<>();
        if (checkEmpty.isEmpty(nums)){
            System.out.println("数组为空");
            return -1;
        }

        //中间位置
        int mid = (left + right) / 2;

        //目标值target与mid相比较
        //相等，返回
        if (nums[mid] == target){
            return mid;
        }else if (target < nums[mid] && left <= right){ //左递归
            right = mid - 1;
            return binarySearch(nums,target,left,right);
        }else if (target > nums[mid] && left <= right){ //右递归
            left = mid + 1;
            return binarySearch(nums,target,left,right);
        }else { //未找到
            System.out.println("未找到");
            return -1;
        }
    }

    /**
     * 对二分查找二次封装
     * 参数列表只封装数组和要查找的值
     * @param nums
     * @param target
     * @return
     */
    public static int binarySearch(int[] nums,int target){
        int left = 0;
        int right = nums.length -1;
        return binarySearch(nums, target, left, right);
    }

    public static void main(String[] args) {
        int[] nums = {-1,0,3,5,9,12};
        int target = 12;
        System.out.println(binarySearch(nums,target));
    }
}

2. 第一个错误版本

题目描述

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, …, n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

输入示例

输入：n = 5, bad = 4
输出：4
解释：
调用 isBadVersion(3) -> false 
调用 isBadVersion(5) -> true 
调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本

思路讲解和代码实现

package com.why.day01;

import com.why.common.CheckEmpty;

/**
 * @ClassName：FirstErrorVersion
 * @Description：todo 第一个错误版本
 *
 * 题目：
 *  你是产品经理，目前正在带领一个团队开发新的产品。
 *  不幸的是，你的产品的最新版本没有通过质量检测。
 *  由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
 *  假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。
 *  你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。
 *  实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
 *
 * 输入示例：
 *  输入：n = 5, bad = 4
 *  输出：4
 *
 * 解释：
 *  调用 isBadVersion(3) -> false
 *  调用 isBadVersion(5)-> true
 *  调用 isBadVersion(4)-> true
 *  所以，4 是第一个错误的版本
 *
 * @Author: why
 * @DateTime：2021/10/29 18:16
 */
public class VersionControl {

    /**
     * 查找第一个错误版本
     *
     * 思路：
     *  1. 使用二分查找
     *  2. 若找到错误版本并且前一版本也是错误版本则向前递归查找，若前一版本不是错误版本则此版本就是第一个错误版本
     *  3. 若未找到错误版本则向后递归查找
     * @param n
     * @return
     */
    public static int searchErrorVersion(int n){

        return binarySearch(n,1,n);
    }


    private static int binarySearch(int n,int left,int right){
        //中间位置
        int mid = left + (right -left) / 2;

        //目标值target与mid相比较
        if (!isBadVersion(mid -1) && isBadVersion(mid)){
            return mid;
        }
        if (left <= right && isBadVersion(mid) && isBadVersion(mid-1)){ //左递归
            right = mid -1;
            return binarySearch(n,left,right);
        }
        if (left <= right && !isBadVersion(mid)){ //右递归
            left = mid + 1;
            return binarySearch(n,left,right);
        }
        return -1;
    }
}

3. 搜素插入位置

题目描述

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

输入示例

输入: nums = [1,3,5,6], target = 5
输出: 2

思路讲解和代码实现

package com.why.day01;

import com.sun.xml.internal.ws.util.exception.LocatableWebServiceException;

import java.util.Stack;

/**
 * @ClassName：SearchinsertIndex
 * @Description：todo 搜索插入位置
 *
 * 题目：
 *  给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
 *  请必须使用时间复杂度为 O(log n) 的算法。
 *
 * 输入示例：
 *  输入: nums = [1,3,5,6], target = 5
 *  输出: 2
 *
 * @Author: why
 * @DateTime：2021/10/29 19:01
 */
public class SearchInsertIndex {

    public static void main(String[] args) {
        int[] nums = {1,3,5,6};
        System.out.println(searchInsert(nums,2));;
    }

    /**
     * 思路：
     * 1. 二分查找
     * 2. 若target < nums[mid]，则左递归
     * 3. 若target > nums[mid]，则右递归
     * 4. 若target == nums[mid]，返回位置
     * 5. 若执行完未查找到则返回left
     * @param nums
     * @param target
     * @return
     */
    public static int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right){
            int mid = left + (right - left) / 2;
            if (target < nums[mid]){
                right = mid -1;
            }else if (target > nums[mid]){
                left = mid + 1;
            }else {
                return mid;
            }
        }

        return left;
    }
}

4. 使用到的判空类

package com.why.common;

/**
 * @ClassName：isEmpty
 * @Description：todo 判空，数组，string等
 * @Author: why
 * @DateTime：2021/10/29 17:27
 */
public class CheckEmpty<T> {

    /**
     * 判断数组类型是否为空
     * @param arr 数组
     * @return
     */
    public boolean isEmpty(T[] arr){
        if (arr.length == 0 || arr == null){
            return true;
        }
        return false;
    }

    /**
     * 判断字符串是否为空
     * @param str
     * @return
     */
    public boolean isEmpty(String str){
        if (str.equals("") || str == null || str.length() == 0){
            return true;
        }
        return false;
    }

    /**
     * 判断引用类型是否为空
     * @param data
     * @return
     */
    public boolean isEmpty(T data){
        if (data == null){
            return true;
        }
        return false;
    }
}