一、前言
盲目刷题只会让自己心态爆炸,所以本期14天算法学习计划,也是LeetCode上的 [算法] 学习计划,在本专栏的每一篇文章都会整理每一天的题目并给出详细题解,以及知识点的整理
二、知识点
第一天的知识点是二分查找,也是一个较简单的查找算法,但是在做题时不能只想着去套模板解题,而是要根据题目意思来使用二分查找的算法解决问题,有关于二分查找的知识点我已经整理在一篇文章里了,想要复习知识点或者对它还一知半解的可以阅读一下
算法查找——二分查找
三、LeetCode704. 二分查找
1.题目
LeetCode704. 二分查找
给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。
示例 1
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2
输入: nums = [-1,0,3,5,9,12],,target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
2.解题示意图
原始定义的 left 、right 和 mid
如果要找的 targe 比 mid 指向的值大,就在右半边找(绿色为新的 left 和 mid )
可见left的值应该修改为mid+1
如果要找的 targe 比 mid 指向的值小,就在右半边找(绿色为新的 left 和 mid )
可见 right 的值应该修改为 mid-1
3.解题思路
1.先查找数组中最中间的元素mid(下标值向下取整)
2.如果要查找的元素值比中间的元素大,就将最大值改为中间值减一
max = mid - 1
3.如果要查找的元素值比中间的元素小,就将最小值改为中间值加一
min = mid + 1
4.重复上述步骤,直至找到所要查找的元素
4.注意事项
很多小伙伴可能第一次刷题的时候会设mid = (left + right)/2,但是如果数据的值大就会溢出。想不明白为什么会溢出?别急,接着往下听我分析
如果我们规定整数的最大值只能是100的话,如果有个老六偏要设数组头和尾的值都是99的话,99+99=198 > 100,芭比Q了,这不就没办法运行程序了嘛,所以为了避免出现这种错误,只能用减法,由于数组的下标值是依次递增的,要想知道他的一半是多少的话,直接拿最大值-最小值的差除以2再加上最小值(一秒回到小学),即 mid = left + (right - left) / 2
如果不相信的话,可以举例试试,比如6到99的中间值是多少?(99-6)/ 2 + 6 = 52,(99+6)/ 2再向下取整(Java内部自动的)也是52,完全没问题
5.代码实现
class Solution { public int search(int[] nums, int target) { int left = 0; int right = nums.length - 1; while(left <= right){ int mid = left + (right - left) / 2; if(nums[mid] < target){ left = mid + 1; } else if(nums[mid] > target){ right = mid - 1; } else{ return mid; } } return -1; } }
6.验证代码
四、LeetCode278. 第一个错误的版本
1.题目
LeetCode278.第一个错误的版本
你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, …, n],你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
示例 1
输入:n = 5, bad = 4
输出:4
解释: 调用 isBadVersion(3) -> false
调用isBadVersion(5) -> true
调用isBadVersion(4) -> true
所以,4 是第一个错误的版本
示例2:
输入:n = 1, bad = 1
输出:1
2.解题示意图
这道题看完第一眼,这题目是什么意思???纯纯黑人问号,所以接下来我会一点一点剥开它,显出原形——二分查找
我们先定义n为10,如果一个个去查找他是不是正确的话,实在是太麻烦了,那么直接一下子砍一半,看中间,也就是第5个版本,发现他这个版本出错了(这道题比较容易让人晕乎的点在此:true表示这个版本是错误的)
既然我们要找出第一个错误的版本,题目里面又告诉我们 “错误的版本之后的所有版本都是错的 ”所以不用看5以后的版本,都是错的,只需要看5版本之前的,也同样先砍一半看最中间的,所以要修改right的值,即 mid = true 时,right = mid
发现是3是false:这个版本不是错误的(是正确的),也就是说3版本是正确的
那此时我们就要修改left的值,即 left = mid+1去判断mid后一个的值,发现重合了,我们就返回left的值就好了
3.解题思路
1.找出中间的元素mid,并判断是否是错误版本
2.如果是错误版本**(mid = true)**,则修改right的值,使得 right = mid
3.如果是正确版本(mid = false),则修改left的值,使得
4.注意事项
- false:这个版本不是错误的,即该版本正确
- true:这个版本是错误的
- mid = left + (right - left) / 2
5.代码实现
/* The isBadVersion API is defined in the parent class VersionControl. boolean isBadVersion(int version); */ public class Solution extends VersionControl { public int firstBadVersion(int n) { int left = 1; int right = n; while(left < right){ int mid = left + (right - left)/2; if(isBadVersion(mid)){ right = mid; } else{ left = mid +1; } } return left; } }
6.验证代码
五、LeetCode35. 搜索插入位置
1.题目
LeetCode35.搜索插入位置
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1
输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2
输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3
输入: nums = [1,3,5,6], target = 7
输出: 4
2.解题思路
1.先查找数组中最中间的元素mid(下标值向下取整)
2.当left <= right时,通过循环查找元素
3.如果要查找的元素值比中间的元素大,就将最大值改为中间值减一
right = mid - 1
4.如果要查找的元素值比中间的元素小,就将最小值改为中间值加一
left = mid + 1
5.重复上述步骤,直至找到所要查找的元素
6.如果没有,就返回left的值;因为要插入的元素是要把比这个元素大的向后移位,而比这个元素小的是不会改变的,所以其下标值为最后搜索的两个元素的后面,如[1,3,5,7,9],target=4,
第一次mid的值为2,元素为5,
第二次mid值为1,值为3,由于搜索不到,但是left(下标0)和right(下标1)并没有重合,且 target > nums[mid] 所以又要修改left的值为 left = mid+1 = 2,那么left > right 所以退出循环,返回的值为left
这里第五步有点绕,建议配合代码食用
3.代码实现
class Solution { public 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]){ left = mid + 1; } else{ right = mid - 1; } } return left; } }
4.验证代码
六、结语
最后一道题的解题方法是我自己优化了官方的解题方法后实现的,虽然理解比较困难,但是一定程度上优化了代码,如果有更加高效的解题方法,欢迎评论留言