14天刷爆LeetCode算法学习计划——Day01 二分查找(内含三道力扣真题)

简介: 如果我们规定整数的最大值只能是100的话,如果有个老六偏要设数组头和尾的值都是99的话,99+99=198 > 100,芭比Q了,这不就没办法运行程序了嘛,所以为了避免出现这种错误,只能用减法,由于数组的下标值是依次递增的,要想知道他的一半是多少的话,直接拿最大值-最小值的差除以2再加上最小值(一秒回到小学),即 mid = left + (right - left) / 2

一、前言


盲目刷题只会让自己心态爆炸,所以本期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


72e0b5aeecbb46a18923a9a872553056.png


如果要找的 targe 比 mid 指向的值大,就在右半边找(绿色为新的 left 和 mid )


可见left的值应该修改为mid+1


f915489e9330439c8eca13c1bf15623a.png


如果要找的 targe 比 mid 指向的值小,就在右半边找(绿色为新的 left 和 mid )


可见 right 的值应该修改为 mid-1


30e391069e2846e6837bcbc5e3355360.png


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.验证代码


bce94662da1445b6ae73fae832307635.png


四、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表示这个版本是错误的)


e476feaa8c9c4e57abc401ffd684a0cb.png


既然我们要找出第一个错误的版本,题目里面又告诉我们 “错误的版本之后的所有版本都是错的 ”所以不用看5以后的版本,都是错的,只需要看5版本之前的,也同样先砍一半看最中间的,所以要修改right的值,即 mid = true 时,right = mid

发现是3是false:这个版本不是错误的(是正确的),也就是说3版本是正确的


8adadfe7dae141d5878940eb2ec33988.png


那此时我们就要修改left的值,即 left = mid+1去判断mid后一个的值,发现重合了,我们就返回left的值就好了


2b1bb05c01d245aea13bbb61f40e4ce8.png


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.验证代码


14737c8d82fb4df5ac86fc8d1e433dd9.png


五、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.验证代码


c9b96d13525e4de2b9880d652f352fcc.png


六、结语


最后一道题的解题方法是我自己优化了官方的解题方法后实现的,虽然理解比较困难,但是一定程度上优化了代码,如果有更加高效的解题方法,欢迎评论留言

相关文章
|
15天前
|
存储 算法
数据结构与算法学习二二:图的学习、图的概念、图的深度和广度优先遍历
这篇文章详细介绍了图的概念、表示方式以及深度优先遍历和广度优先遍历的算法实现。
30 1
数据结构与算法学习二二:图的学习、图的概念、图的深度和广度优先遍历
|
12天前
|
缓存 算法 Java
JVM知识体系学习六:JVM垃圾是什么、GC常用垃圾清除算法、堆内存逻辑分区、栈上分配、对象何时进入老年代、有关老年代新生代的两个问题、常见的垃圾回收器、CMS
这篇文章详细介绍了Java虚拟机(JVM)中的垃圾回收机制,包括垃圾的定义、垃圾回收算法、堆内存的逻辑分区、对象的内存分配和回收过程,以及不同垃圾回收器的工作原理和参数设置。
36 4
JVM知识体系学习六:JVM垃圾是什么、GC常用垃圾清除算法、堆内存逻辑分区、栈上分配、对象何时进入老年代、有关老年代新生代的两个问题、常见的垃圾回收器、CMS
|
13天前
|
算法
动态规划算法学习三:0-1背包问题
这篇文章是关于0-1背包问题的动态规划算法详解,包括问题描述、解决步骤、最优子结构性质、状态表示和递推方程、算法设计与分析、计算最优值、算法实现以及对算法缺点的思考。
40 2
动态规划算法学习三:0-1背包问题
|
9天前
|
算法
每日一道算法题(Leetcode 20)
每日一道算法题(Leetcode 20)
17 2
|
12天前
|
算法 C# 索引
C#二分查找算法
C#二分查找算法
|
13天前
|
算法
动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)
这篇文章介绍了动态规划算法中解决最大上升子序列问题(LIS)的方法,包括问题的描述、动态规划的步骤、状态表示、递推方程、计算最优值以及优化方法,如非动态规划的二分法。
48 0
动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)
|
13天前
|
算法
动态规划算法学习二:最长公共子序列
这篇文章介绍了如何使用动态规划算法解决最长公共子序列(LCS)问题,包括问题描述、最优子结构性质、状态表示、状态递归方程、计算最优值的方法,以及具体的代码实现。
55 0
动态规划算法学习二:最长公共子序列
|
13天前
|
缓存 负载均衡 算法
nginx学习:配置文件详解,负载均衡三种算法学习,上接nginx实操篇
Nginx 是一款高性能的 HTTP 和反向代理服务器,也是一个通用的 TCP/UDP 代理服务器,以及一个邮件代理服务器和通用的 HTTP 缓存服务器。
19 0
nginx学习:配置文件详解,负载均衡三种算法学习,上接nginx实操篇
|
14天前
|
程序员 C语言
【C语言】LeetCode(力扣)上经典题目
【C语言】LeetCode(力扣)上经典题目
|
13天前
|
存储 算法
动态规划算法学习一:DP的重要知识点、矩阵连乘算法
这篇文章是关于动态规划算法中矩阵连乘问题的详解,包括问题描述、最优子结构、重叠子问题、递归方法、备忘录方法和动态规划算法设计的步骤。
56 0