算法刷题-Day01
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;
}
}