前端工程师leetcode算法面试必备-二分搜索算法(中)
一、前言
二分搜索算法本身并不是特别复杂,核心点主要集中在:
-
有序数组:指的是一个递增或者递减的区间(特殊情况如:【852. 山脉数组的峰顶索引】);
-
中间数:用来确定搜索目标落在左半区间还是右半区间;
进入 Medium 难度之后,这两个条件一般不会直接给出,需要解题者根据题目自行构造。
二、LeetCode 实战
1、378. 有序矩阵中第K小的元素
由水平和垂直方向为递增数组的条件,可以得到当前二维空间中的左上角为最小值,右下角为最大值,所以有序数组即为最小值到最大值的整数递增序列。
题目要求计算出第 k 小的元素,那么从有序数组中挑选出来的中间数并不能直接与 k 进行比较,需要在二维空间中找出当前中间数是第几小的数字,再与 k 进行比较:
-
如果当前中间数比第 k 小的元素要大,那么第 k 小元素必然在左半区间;
-
否则必然落在右半区间;
通过当前二维数组水平和垂直方向单调递增的特性,可以从左下角开始搜索当前中间数为第几小的数字。
类似解题思路的还有:
- 【74. 搜索二维矩阵】
2、875. 爱吃香蕉的珂珂
这道题要求我们找出一个最慢吃香蕉的速度,使得在 H 小时可以吃完 N 堆香蕉。
珂珂最慢吃香蕉的速度是每个小时吃1根,最快的速度是每小时吃掉 max(N),有序数组即为 1 到 max(N) 的整数递增序列。
从有序数组中找出一个速度之后,还需要计算当前速度下吃完所有香蕉所需的时间和 H 相比较:
-
如果当前速度下吃完所有香蕉的时间大于 H,那么所需要搜索的速度 K 必然落在右半区间;
-
反之,K 落在左半区间;
3、658. 找到 K 个最接近的元素
这道题要求我们找到一个起始下标 index,使得 [index, index + k) 中的数字最靠近 x 。
该题并没有隐藏有序数组这一条件,所以这道题目的难点在于如何通过中间下标来判断 index 落在哪个区间:
-
首先考虑数组边界的问题,如果 mid + k > arr.length - 1,那么 index 必然在落在左半区间;
-
接下来利用最靠近 x 和优先选择最小元素(也就是优先选择左边的元素)这两个条件:如果距离 x 左边的差值小于距离 x 右边的差值,那么 index 必然落在左半区间;
类似解题思路的题目还有:
- 【275. H指数 II】
4、34. 在排序数组中查找元素的第一个和最后一个位置
这道题目相对比较简单,但是它与前面题目的差异在于:搜索目标不一定存在有序数组中,那么在搜索结束后,就需要注意特殊情况的处理。
通过两次二分搜索找出目标值的上下界限下标,再将上下界限值与目标值进行比对,从而得出正确的开始下标和结束下标:
参考视频:传送门
写在最后
算法作为计算机的基础学科,用 JavaScript 刷,一点也不丢人ε=ε=ε=┏(゜ロ゜;)┛。
本系列文章会分别给出一种算法的3种难度的总结篇(简单难度,中等难度以及困难难度)。在简单难度中,会介绍该算法的基本知识与实现,另外两个难度,着重讲解解题的思路。
如果本文对您有所帮助,可以点赞或者关注来鼓励博主。
相关文章:
前端工程师leetcode算法面试必备-二分搜索算法(中)
一、前言 二分搜索算法本身并不是特别复杂,核心点主要集中在: 有序数组:指的是一个递增或者递减的区间(特殊情况如:【852. 山脉数组的峰顶索引】); 中间数:用来确定搜索目标落在左…...
【数据库】MySQL 单表查询,多表查询
目录 单表查询 一,创建表worker 1,创建表worker的sql代码如下: 2,向worker表中插入信息 二, 按要求进行单表查询 1、显示所有职工的基本信息。 2、查询所有职工所属部门的部门号,不显示重复的部门号。 …...
【c++】vector实现(源码剖析+手画图解)
vector是我接触的第一个容器,好好对待,好好珍惜! 目录 文章目录 前言 二、vector如何实现 二、vector的迭代器(原生指针) 三、vector的数据结构 图解: 四、vector的构造及内存管理 1.push_back() …...
VScode查看python f.write()的文件乱码
VScode查看python f.write()的文件乱码 在使用 VScode 编写 python 代码, print(),汉字正常显示, 使用 with open()as f: f.write()文件后, 在 …...
excel应用技巧:如何用函数制作简易抽奖动图
利用INDEX函数和随机整数函数RANDBETWEEN配合,在Excel中做一个简单的抽奖器,可以随机抽取姓名或者奖品。有兴趣的伙伴可以做出来试试,撞撞2023年好运气。每次年会大家最期待的就是抽奖环节。为了看看自己今年运气怎么样,会不会获奖…...
CSI Tool 安装及配置记录
一、Ubuntu安装 1.下载Ubuntu 首先安装Ubuntu 14.04 LTS 64位下载地址(页面中第一个链接) 2.制作启动盘(注意备份) 可以使用官方的工具Rufus,下载地址:https://rufus.ie/ 打开Rufus,先备份…...
华为OD机试 - 最低位排序(Python)| 真题+思路+代码
最低位排序 题目 给定一个非空数组(列表),起元素数据类型为整型, 请按照数组元素十进制最低位从小到大进行排序, 十进制最低位相同的元素,相对位置保持不变, 当数组元素为负值时,十进制最低为等同于去除符号位后对应十进制值最低位。 输入 给定一个非空数组(列表) 其…...
C#开发的OpenRA使用TrimExcess方法
C#开发的OpenRA使用TrimExcess方法 当你在细看OpenRA的代码,就会发现在下面这段代码添加了一个方法: foreach (var nodes in levels) nodes.TrimExcess(); 在上面代码里遍历整个节点列表,把所有节点都调用TrimExcess方法处理一下, 这样做的意义何在?为什么我们在一般的代码…...
ImageMagick任意文件读取漏洞(CVE-2022-44268)
0x00 前提 前几天爆出一个 ImageMagick 漏洞 ,可以造成一个任意文件读取的危害比较可观,最近有时间来复现学习一下 主要是影响的范围很大,很多地方都有这个问题,需要来学习一下 0x01 介绍 ImageMagick 是一个免费的开源软件套…...
第十九篇 ResNet——论文翻译
文章目录 摘要1 引言2 相关工作3 深度残差学习3.1 残差学习3.2 快捷恒等映射3.3 网络架构3.4 实现4 实验4.1 ImageNet 分类4.2 CIFAR-10 和分析4.3 PASCAL 和 MS COCO 上的物体检测🐇🐇🐇🐇🐇🐇 🐇 欢迎阅读 【AI浩】 的博客🐇 👍 阅读完毕,可以动动小手赞一…...
RiProRiProV2主题美化顶部增加一行导航header导航通知
背景: 有些网站的背景顶部有一行罪行公告,样式不错,希望自己的网站也借鉴过来,本教程将指导如何操作,并调整成自己想要的样式。 比如网友搭的666资源站 xd素材中文网...
RT-Thread MSH_CMD_EXPORT分析
RT-Thread MSH_CMD_EXPORT分析 1. 源码分析 在rt-thread中,使用FinSH,可以支持命令行。在源码中,使用MSH_CMD_EXPORT导出函数到对应命令。 extern void rt_show_version(void); long version(void) {rt_show_version();return 0; } MSH_CM…...
电脑麦克风没声音怎么办?这3招就可以解决!
最近有用户在使用电脑麦克风进行视频录制时,发现麦克风没有声音。这是什么原因?电脑麦克风没有声音怎么办?关于解决方案,我专门整理了三种方法来帮你们,一起来看看吧! 操作环境: 演示机型&#…...
【C++】运算符重载
运算符重载 C为了增强代码的可读性引入了运算符重载,运算符重载是具有特殊函数名的函数,也具有其返回值类型,函数名以及参数列表。其返回值类型和参数列表与普通的函数类型。 函数名字为:关键字operator后面接需要重载的运算符号…...
什么是眼图?(扫盲向)
什么是眼图?(扫盲向) Ref: What’s eye diagram? 1 基础图示 眼图 2 用途 常用于评估差分链路中的信号传输质量 "眼睛"张得越开,链路信号质量越好 3 观测原理 眼图是传输信号序列在时域上的叠加 4 观测参数 4…...
【C++】类与对象(二)
前言 在前一章时我们已经介绍了类与对象的基本知识,包括类的概念与定义,以及类的访问限定符,类的实例化,类的大小的计算,以及C语言必须传递的this指针(C中不需要我们传递,编译器自动帮我们实现&…...
【软考】系统集成项目管理工程师(二十一)项目收尾管理
1. 项目验收2. 项目总结3. 系统维护4. 项目后评价补充:人员转移和资源遣散广义的系统集成项目收尾管理工作通常包含四类典型的工作:项目验收工作、项目总结工作、系统维护工作 以及 项目后评价工作,此外项目团队成员的后续工作也应在收尾管理时妥善安排;狭义的系统集成项目…...
关于公钥与私钥的一点看法
故事的起源 私密性 之前,用户a想给用户b发消息,a希望他自己发出现的消息,只能被b读懂。也就是说a希望发出去的数据是被加密过的,收到消息的人可以是b,c,d,e等等。但是只有b能被读懂。 这个需求…...
深入React源码揭开渲染更新流程的面纱
转前端一年半了,平时接触最多的框架就是React。在熟悉了其用法之后,避免不了想深入了解其实现原理,网上相关源码分析的文章挺多的,但是总感觉不如自己阅读理解来得深刻。于是话了几个周末去了解了一下常用的流程。也是通过这篇文章…...
32个关于FPGA的学习网站
语言类学习网站 1、HDLbits 网站地址:https://hdlbits.01xz.net/wiki/Main_Page 在线作答、编译的学习Verilog的网站,题目很多,内容丰富。非常适合初学Verilog的人!!! 2、牛客网 网站地址:http…...
5分钟快速上手Promise使用
promise 是处理异步编程的一种处理方式,可以将异步操作按照同步操作的方式编写。是一个对象或者构造函数,里面存放着某个未来才会执行的结果的方法(一般就是异步操作) 自己身上有all、reject、resolve这几个方法,原型上…...
大客户市场:阿里云、腾讯云、华为云“贴身肉搏”
配图来自Canva可画 近年来,随着中国逐渐进入数字化经济快车道,国内企业数字化、智能化升级已是刻不容缓。而为了帮助自身或其他企业实现数字化转型升级,阿里、腾讯、百度、京东、字节、网易、华为等众多国内知名企业早在多年以前,…...
华为OD机试 - 求字符串中所有整数的最小和(Python)| 真题+思路+代码
求字符串中所有整数的最小和 题目 说明 字符串 s,只包含 a-z A-Z + - ;合法的整数包括 1) 正整数 一个或者多个0-9组成,如 0 2 3 002 102 2)负整数 负号 - 开头,数字部分由一个或者多个0-9组成,如 -0 -012 -23 -00023输入 包含数字的字符串 输出 所有整数的最小和 …...
企业电子招投标采购系统源码之首页设计
功能模块: 待办消息,招标公告,中标公告,信息发布 描述: 全过程数字化采购管理,打造从供应商管理到采购招投标、采购合同、采购执行的全过程数字化管理。通供应商门户具备内外协同的能力,为…...
浅谈一下前端工作中全流程多层次的四款测试工具
在应届生找工作的时候,我们经常会见到一条招聘要求:要求实习经历。或者 有实习经历者优先。 为什么大部分公司在招聘时,都要求你必须有实习经历? 商业项目与个人项目不同,一段实习经历,能够熟悉公司中成熟…...
【运算放大器】反相放大电路仿真应用
目录 一、反相放大电路原理(简化电路) 二、反相放大电路电路原理(实际特性) 2.1原理图 2.2实际电路 三、虚短 虚断 3.1 虚短 3.2 虚断 四、作业 4.1 (反相)放大电路设计 4.2 LM741芯片 五、标准…...
数组的操作
1.splice 1.splice 是数组的一个方法,使用这个方法会改变原来的数组结构,splice(index ,howmany , itemX);这个方法接受三个参数,我们在使用的时候可根据自己的情况传递一个参数&…...
Python - 文件基础操作
目录 文件的读取 open()打开函数 read类型 read()方法 readlines()方法 readline()方法 for循环读取文件行 close() 关闭文件对象 with open 语法 文件的写入 文件的追加 文件的读取 操作 功能 文件对象 open(file, mode, encoding) 打开文件获得文件对象 文件…...
react的useState源码分析
前言 简单说下为什么React选择函数式组件,主要是class组件比较冗余、生命周期函数写法不友好,骚写法多,functional组件更符合React编程思想等等等。更具体的可以拜读dan大神的blog。其中Function components capture the rendered values这句…...
SharpImpersonation:一款基于令牌和Shellcode注入的用户模拟工具
关于SharpImpersonation SharpImpersonation是一款功能强大的用户模拟工具,该工具基于令牌机制和Shellcode注入技术实现其功能,可以帮助广大研究人员更好地对组织内部的网络环境和系统安全进行分析和测试。 该工具基于 Tokenvator的代码库实现其功能&a…...
中国建设银行邀约提额网站/扬州百度推广公司
1、查找某条数据的创建时间同个月内的所有数据 SELECT * FROM 表名 WHERE DATE_FORMAT( create_time, %Y%m ) DATE_FORMAT( 2021-01-01 , %Y%m ) create_time:表里表示创建时间的字段名 2021-01-01 :选择的某条数据创建时间的年月日 2、使用select…...
dw做网站 后台用什么后台/列表网推广效果怎么样
2019独角兽企业重金招聘Python工程师标准>>> 在Linux shell 中启动图形界面的应用(如eclipse),会遇到一个麻烦:即当不小心关闭或退出shell时,在该shell中启动的程序也会被结束。这在有些情况下是我们不想看…...
做公司网站需要花钱吗/百度投放广告联系谁
01串 时间限制:1000 ms | 内存限制:65535 KB难度:2描述ACM的zyc在研究01串,他知道某一01串的长度,但他想知道不含有“11”子串的这种长度的01串共有多少个,他希望你能帮帮他。 注:01串的长度为…...
车险网站模版/百度推广首次开户需要多少钱
今天做的一个小程序项目中需要用到scope.userLocation获取用户地理位置这个权限,这个权限对应两个接口wx.getLocation(Object object) 和wx.chooseLocation(Object object),这两个接口都能够获取到用户当前位置的经纬度,但是除此之外…...
南京网站建设设计/网络策划书范文
计算机二级C语言程序填空题练习题导语:为帮助同学们更好更有准备地复习计算机二级C语言,小编整理了计算机二级C语言程序填空题练习题,一起来测试一下吧:程序填空题下列给定程序中,函数fun的功能是:把形参a所…...
wordpress企业网站模板/北京百度推广公司
杨利民: 点击打开链接王静: 点击打开链接颜洁: 点击打开链接伍道军: 点击打开链接陈俊: 点击打开链接 向慧琳:点击打开链接 张埂铝:点击打开链接 蒋俊:点击打开链接 代思雨ÿ…...