【LeetCode】升级打怪之路 Day 01:二分法
今日题目:
- 704. 二分查找
- 35. 搜索插入位置
- 34. 在排序数组中查找元素的第一个和最后一个位置
目录
- 今日总结
- Problem 1: 二分法
- LeetCode 704. 二分查找 【easy】
- LeetCode 35. 搜索插入位置 ⭐⭐⭐⭐⭐
- LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置 【medium】
今日总结
重点学习了使用二分法来解决问题,需要特别理解的是,二分法在通过 while(low <= high) 循环后,low 与 high 的关系所呈现出来的性质,以及为什么能够呈现这样的性质。利用这个性质可以更容易地解决相关问题。
Problem 1: 二分法
LeetCode 704. 二分查找 【easy】
704. 二分查找 | LeetCode
这个题目很经典,题目本身很简单,但这里有一种具有普适性的写法,可以用来解决其他二分查找相关的题目,这里需要着重学习一下:

关键理解好二分法在经过 while(low <= high) 这个循环后,low 和 high 所呈现出来的结果的性质:

- high 最后一定是在 low 左边,而且 high == low - 1,形成一个交错
- low 和 high 中间将数字序列划分成了两个部分:
- 左半边从开始到 high 为止,都是小于 target
- 右半边从 low 到结束,都是大于等于 target
为什么会具备这样的性质?
简单来说,因为 while 的判断是low <= high,所以最终 low 一定是大于 high。
同时,low 和 high 每次更新都是基于 mid 来向前或向后一步走,而 mid 是一定出现在 [low,high] 这个区间内,所以每次更新的结果是,low 或 high 一定是处于原先 [low,high] 范围内或者这个范围的左边或右边一个为止。所以,最终一定是high == low - 1。
当然,目前也很容易理解 [0, high] 一定是小于 target,[low, end) 一定是大于等于 target。因为当nums[mid] == target时,我们是将 high 移动到 mid 左边,这样的结果就是让等于 target 元素的值出现在了 high 右边,所有右半边才会有等于 target 的元素。
在上面的代码中,low 最终指向的是第一个大于等于 target 的元素,但由于 target 可能不存在,所以在作为结果返回时,需要判断一下 low 是否在 nums 的合法范围内,以及 low 指向的值是否等于 target。
学会了这个题目,下面几个题目就是可以利用这里总结的性质来解决。
LeetCode 35. 搜索插入位置 ⭐⭐⭐⭐⭐
35. 搜索插入位置 | LeetCode
通过这个题,对二分法的思路有了更深入的理解。
这个题目是返回搜索的位置或者插入的位置,自然也就是 low 的位置,所以代码如下:

整体与第一个二分法的题目一样,只是最后直接把 low 给 return 出去而已。
所以,学习二分法需要注意:
- 代码中 while 的条件、low 与 high 变更的方式
- 经过 while 循环后 low 与 high 所呈现出来的性质
LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置 【medium】
34. 在排序数组中查找元素的第一个和最后一个位置 | LeetCode
这个题目就有难度了,解决这个题目,需要依靠我们在上面的题目中总结出来的经验。
由于题目要求复杂度 O ( log n ) O(\log n) O(logn),所以需要通过两次二分查找来分别找到左边界和右边界。
刚刚我们总结到,当经过 while 循环后,low 指向了第一个大于等于 target 的元素,这不就是这个题目的左边界嘛!所以,我们可以写出找左边界的代码,但是因为这个题目中 nums 中的数字是可能重复的,所以我们需要做一些更改:

这个代码有两点需要我们特别关注:
- 当
val == target的时候,我们是更新 low 还是 high? - 左边界和 low 的关系?
在上面代码中,如果 val == target,那么就让 high 移动到 mid 左边,这样的结果就是当 while 循环完之后,等于 target 的元素都出现在了右半边,也就是 [low, end) 这个区间内,所以 low 才成了左边界。
同时因为 low 可能超出 nums 的索引范围,以及可能没有找到 target,所以给左边界 first 赋值时需要检查一下,检查不通过就是赋值 -1,代表没有找到。
根据刚刚的思路,当 val == target 时,如果我们让 low 移动到 mid 右边,那么 while 循环完的结果就变成了 “target 的元素都出现了左半边”,也就是 [0, high] 这个区间,所以 high 自然就成了右边界。
所以寻找右边界的二分写法是:

注意这里与找左边界的区别。
相关文章:
【LeetCode】升级打怪之路 Day 01:二分法
今日题目: 704. 二分查找35. 搜索插入位置34. 在排序数组中查找元素的第一个和最后一个位置 目录 今日总结Problem 1: 二分法LeetCode 704. 二分查找 【easy】LeetCode 35. 搜索插入位置 ⭐⭐⭐⭐⭐LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置 【medi…...
单片机stm32智能鱼缸
随着我国经济的快速发展而给人们带来了富足的生活,也有越来越多的人们开始养鱼,通过养各种鱼类来美化居住环境和缓解压力。但是在鱼类饲养过程中,常常由于鱼类对水质、水位及光照强度有着很高的要求,而人们也由于工作的方面而无法…...
面试经典150题——生命游戏
"Push yourself, because no one else is going to do it for you." - Unknown 1. 题目描述 2. 题目分析与解析 2.1 思路一——暴力求解 之所以先暴力求解,是因为我开始也没什么更好的思路,所以就先写一种解决方案,没准写着写…...
【C++】C++11下线程库
C11下线程库 1. thread类的简单介绍2.线程函数参数3.原子性操作库(atomic)4.mutex的种类5. RAII风格加锁解锁5.1Lock_guard5.2unique_lock 6.condition_variable 1. thread类的简单介绍 在C11之前,涉及到多线程问题,都是和平台相关的,比如wi…...
面试经典150题——矩阵置零
"Dream it. Wish it. Do it." - Unknown 1. 题目描述 2. 题目分析与解析 2.1 思路一——暴力求解 思路一很简单,就是尝试遍历矩阵的所有元素,如果发现值等于0,就把当前行与当前列的值分别置为0。同时我们需要注意,…...
多端开发围炉夜话
文章目录 一、多端开发 一、多端开发 uni-app 官网 UNI-APP中的UI框架:介绍常用的UI框架及其特点 uView UIVant WeappColor UIMint UI uniapp嵌入android原生开发的功能 uniapp使用安卓原生sdk uni-app中的uni.requireNativePlugin...
分治算法总结(Java)
目录 分治算法概述 快速排序 练习1:排序数组 练习2:数组中的第K个最大元素 练习3:最小k个数 归并排序 练习4:排序数组 练习5:交易逆序对的总数 练习6:计算右侧小于当前元素的个数 练习7࿱…...
【云原生系列之kubernetes】--Ingress使用
service的缺点: 不支持基于URL等机制对HTTP/HTTPS协议进行高级路由、超时、重试、基于流量的灰度等高级流量治理机制难以将多个service流量统一管理 1.1ingress的概念 ingress是k8s中的一个对象,作用是如何将请求转发到service的规则ingress controlle…...
练习:鼠标类设计之2_类和接口
前言 续鼠标类设计之1,前面解决了鼠标信号问题,这里解决显示问题 引入 鼠标伴随操作系统而生,考虑在屏幕上怎样显示 思路 1>鼠标显示是一个动态效果,所以需要一个“动态效果类”对象,添加进鼠标类的属性里。 在面…...
【程序员英语】【美语从头学】初级篇(入门)(笔记)Lesson 15 At the Department Store 在百货商店
《美语从头学初级入门篇》 注意:被 删除线 划掉的不一定不正确,只是不是标准答案。 文章目录 Lesson 15 At the Department Store 在百货商店会话A会话B笔记 Lesson 15 At the Department Store 在百货商店 会话A A: Can you help me, please? B: Sur…...
linux 安装、删除 JTAG驱动
安装 安装驱动需要sudo访问权限,所以得手动安装。 在petalinux安装目录下: 文件的路径。 cd tools/xsct/data/xicom/cable_drivers/lin64/install_script/install_drivers 然后执行文件 install_drivers。 sudo ./install_drivers安装成功。 删除 …...
CSS的伪类选择器:nth-child()
CSS的伪类选择器:nth-child() CSS的伪类选择器 :nth-child() 是一个非常强大的工具,它允许你根据元素在其父元素中的位置(序数)来选择特定的子元素。这个选择器可以应用于任何元素,并且可以与类型选择器、类选择器或ID选择器结合…...
python celery使用队列
在celery的配置方法中有个参数叫task_routes,是用来设置不同的任务 消费不同的队列(也就是路由)。 格式如下: { ‘task name’: { ‘queue’: ‘queue name’ }}直接上代码,简单明了,目录格式如下&#x…...
四非保研之旅
大家好,我是工藤学编程,虽有万分感概,但是话不多说,先直接进入正题,抒情环节最后再说,哈哈哈 写在开头 我的分享是来给大家涨信心的,网上的大佬们都太强了,大家拿我涨涨信心&#…...
基于Java+SpringBoot的旅游路线规划系统(源码+论文)
文章目录 目录 文章目录 前言 一、功能设计 二、功能实现 1.1 前端首页模块的实现 1.2 景点新闻 1.3 景点在线预订 1.4 酒店在线预订 1.5 管理员景点管理 1.6 管理员旅游线路管理 1.7 酒店信息管理 三、库表设计 前言 随着我国的经济的不断发展,现在的一些热门的景…...
AI与测试自动化:未来已来
AI与测试自动化注定融合。软件开发的速度和准确性要求已经远远超出了预期。测试自动化通过重复、详细和数据密集型测试来解决这个问题,确保敏捷和持续交付环境中的软件质量。AI的学习、适应和预测能力以完美的效率和准确性增强了测试自动化。复杂的算法现在充当质量…...
深度学习基础之《TensorFlow框架(6)—张量》
一、张量 1、什么是张量 张量Tensor和ndarray是有联系的,当我们print()打印值的时候,它返回的就是ndarray对象 TensorFlow的张量就是一个n维数组,类型为tf.Tensor。Tensor具有以下两个重要的属性: (1)typ…...
第三百六十六回
文章目录 1. 概念介绍2. 使用方法2.1 List2.2 Map2.3 Set 3. 示例代码4. 内容总结 我们在上一章回中介绍了"convert包"相关的内容,本章回中将介绍collection.闲话休提,让我们一起Talk Flutter吧。 1. 概念介绍 我们在本章回中介绍的内容是col…...
Fiddler工具 — 18.Fiddler抓包HTTPS请求(一)
1、Fiddler抓取HTTPS过程 第一步:Fiddler截获客户端发送给服务器的HTTPS请求,Fiddler伪装成客户端向服务器发送请求进行握手 。 第二步:服务器发回相应,Fiddler获取到服务器的CA证书, 用根证书(这里的根证…...
多租户数据库的缓冲区共享和预分配方案设计
多租户数据库的缓冲区共享和预分配方案设计 文章目录 多租户数据库的缓冲区共享和预分配方案设计简介初始化输入交互输出输入部分的输出交互部分的输出 评分注意点语言要求需要使用的模块系统框架图方案设计初始化阶段交互阶段 修改进度规划最终代码 简介 云计算技术使企业能够…...
SpringBoot-17-MyBatis动态SQL标签之常用标签
文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...
调用支付宝接口响应40004 SYSTEM_ERROR问题排查
在对接支付宝API的时候,遇到了一些问题,记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...
阿里云ACP云计算备考笔记 (5)——弹性伸缩
目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...
如何在看板中体现优先级变化
在看板中有效体现优先级变化的关键措施包括:采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中,设置任务排序规则尤其重要,因为它让看板视觉上直观地体…...
蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练
前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1):从基础到实战的深度解析-CSDN博客,但实际面试中,企业更关注候选人对复杂场景的应对能力(如多设备并发扫描、低功耗与高发现率的平衡)和前沿技术的…...
汇编常见指令
汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX(不访问内存)XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...
【JavaSE】绘图与事件入门学习笔记
-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角,以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向,距离坐标原点x个像素;第二个是y坐标,表示当前位置为垂直方向,距离坐标原点y个像素。 坐标体系-像素 …...
IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)
文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...
使用 SymPy 进行向量和矩阵的高级操作
在科学计算和工程领域,向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能,能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作,并通过具体…...
Linux nano命令的基本使用
参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时,显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...
