【专题刷题】二分查找(二)
📝前言说明:
- 本专栏主要记录本人的基础算法学习以及LeetCode刷题记录,按专题划分
- 每题主要记录:(1)本人解法 + 本人屎山代码;(2)优质解法 + 优质代码;(3)精益求精,更好的解法和独特的思想(如果有的话)
- 文章中的理解仅为个人理解。如有错误,感谢纠错
🎬个人简介:努力学习ing
📋本专栏:C++刷题专栏
📋其他专栏:C语言入门基础,python入门基础,C++学习笔记,Linux
🎀CSDN主页 愚润泽
视频
- 69. x 的平方根
- 个人解
- 35. 搜索插入位置
- 个人解
- 852. 山脉数组的峰顶索引
- 个人解
- 162. 寻找峰值
- 个人解
- 153. 寻找旋转排序数组中的最小值
- 个人解
- 优质解
- LCR 173. 点名
- 个人解
69. x 的平方根
个人解
思路:
- 确定答案区间:
[0, min(x, 46341)]
(46341 是 2^31 - 1 的平方根 + 1) - 问题转换成:找平方 <= x 的右端点(因为题目向下取整)
mid
选取判断:因为向下取整,left = mid
会死循环
用时:
屎山代码:
class Solution {
public:int mySqrt(int x) {int left = 0, right = min(x, 46341);while(left < right) {unsigned int mid = left + (right - left + 1) / 2;if(mid * mid <= x)left = mid;elseright = mid - 1;}return left;}
};
时间复杂度:O(n)
空间复杂度:O(1)
35. 搜索插入位置
个人解
思路:
- 题目意思:有
target
就返回target
,没有就返回>target
的第一个位置 - 总结一下:就是返回
>= target
的第一个位置 - 细节处理:模拟三种情况:1,正常找到
target
或者正常在数组中间插入;2,全部值都小于target
;3,全部值都大于target
(在这道题中要特殊处理全小于target
的情况)
用时:5:00
屎山代码:
class Solution {
public:int searchInsert(vector<int>& nums, int target) {int left = 0, right = nums.size() - 1;while(left < right){int mid = left + (right - left) / 2;if(nums[mid] < target)left = mid + 1;elseright = mid;}// 特殊处理全小于target的情况if(nums[right] >= target)return right;elsereturn nums.size();}
};
时间复杂度:O(logN)
空间复杂度:O(1)
852. 山脉数组的峰顶索引
个人解
思路:
- 二段性:每次和右边的数比较
- 右边的数不存在 / 右边的数 <= 当前数:山峰肯定在
[left, mid]
- 右边的数 > 当前数:山峰肯定在
[mid + 1, right]
用时:5:00
屎山代码:
class Solution {
public:int peakIndexInMountainArray(vector<int>& arr) {int left = 0, right = arr.size() - 1;while(left < right){int mid = left + (right - left) / 2;if(mid + 1 == arr.size() || arr[mid + 1] <= arr[mid])right = mid;elseleft = mid + 1;}return right;}
};
时间复杂度:O(logN)
空间复杂度:O(1)
162. 寻找峰值
个人解
思路:
- 这道题的提示3:
nums[i] != nums[i + 1]
,太重要了(保证了一定有一个峰值) - 每次和右侧数字比较
> 右侧的数字
:峰值一定在[left ,mid]
(mid
有可能是峰值)< 右侧的数字
:峰值一定在[mid + 1, right]
用时:10:00(一开始没看到提示3)
屎山代码:
class Solution {
public:int findPeakElement(vector<int>& nums) {int left = 0, right = nums.size() - 1;while(left < right){int mid = left + (right - left) / 2;if(nums[mid] > nums[mid + 1])right = mid;elseleft = mid + 1;}return right;}
};
时间复杂度:O(logN)
空间复杂度:O(1)
153. 寻找旋转排序数组中的最小值
个人解
思路:
- 利用数组的有序性二分,找最小
- 但是问题在于:这里在翻转以后可能出现两段数组!一段数组上查找的时候,要判断最小值会不会出行在另一段数组上
- 如何判断呢?如果真的有两段数组,则第二段数组的最大值一定是
nums[n-1]
,如果当前nums[mid] < nums[n - 1]
代表在正确的数组上查找了,反之就是在错误的数组上查找了,要让left
移动到右边
用时:15:00
屎山代码:
class Solution {
public:int findMin(vector<int>& nums) {int n = nums.size();int left = 0, right = n - 1;while(left < right){int mid = left + (right - left) / 2;if(mid + 1 == n || (nums[mid] < nums[mid + 1] && nums[mid] < nums[n - 1]))right = mid;elseleft = mid + 1;}return nums[right];}
};
时间复杂度:O(log n)
空间复杂度:O(1)
优质解
看了官方题解以后想到的:
- 如果翻转了,产生了两个数组,则最小值,一定在第二个数组上!!!
- 并且,前一个数组的元素都大于第二个数组的元素
- 那我们的比较基准就可以和最后一个值进行比较
> nums[n-1]
:数组错了,答案一定在[mid + 1, right]
< nums[n-1]
:答案一定在[left, mid]
,mid
也有可能是答案
代码:
class Solution {
public:int findMin(vector<int>& nums) {int n = nums.size();int left = 0, right = n - 1;while(left < right){int mid = left + (right - left) / 2;if(nums[mid] < nums[n - 1])right = mid;elseleft = mid + 1;}return nums[right];}
};
LCR 173. 点名
个人解
思路:
- 因为数组是升序排序的,且学号从0开始,利用学号和下标对应的特点,找出缺失值在哪一遍
- mid == records[mid] ,则缺失值在 [mid + 1, right]
- mid > records[left, mid]
- 特殊判断,最后一个同学缺席
用时:7:00
屎山代码:
class Solution {
public:int takeAttendance(vector<int>& records) {int n = records.size();if(records[n - 1] == n - 1)return n;int left = 0, right = n - 1;while(left < right){int mid = left + (right - left) / 2;if(mid == records[mid])left = mid + 1;elseright = mid;}return records[right] - 1;}
};
时间复杂度:O(log n)
空间复杂度:O(1)
🌈我的分享也就到此结束啦🌈
要是我的分享也能对你的学习起到帮助,那简直是太酷啦!
若有不足,还请大家多多指正,我们一起学习交流!
📢公主,王子:点赞👍→收藏⭐→关注🔍
感谢大家的观看和支持!祝大家都能得偿所愿,天天开心!!!
相关文章:
【专题刷题】二分查找(二)
📝前言说明: 本专栏主要记录本人的基础算法学习以及LeetCode刷题记录,按专题划分每题主要记录:(1)本人解法 本人屎山代码;(2)优质解法 优质代码;ÿ…...
如何避免IDEA每次打开新项目都重复配置Maven?
每次打开新项目都要重新设置Maven路径?每次导入工程都要手动调整settings.xml?如果你也受够了IDEA这种“健忘”行为,那么这篇文章就是为你准备的!今天我们就来彻底解决这个问题,让IDEA记住你的Maven配置,一…...
【Linux网络编程】应用层协议HTTP(实现一个简单的http服务)
目录 前言 一,HTTP协议 1,认识URL 2,urlencode和urldecode 3,HTTP协议请求与响应格式 二,myhttp服务器端代码的编写 HTTP请求报文示例 HTTP应答报文示例 代码编写 网络通信模块 处理请求和发送应答模块 结…...
深度解析之算法之分治(快排)
44.颜色分类 题目链接 给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ,原地 对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。 我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。 必须在不使用库内置…...
【金仓数据库征文】-金仓数据库性能调优 “快准稳” 攻略:实战优化,让数据处理飞起来
我的个人主页 我的专栏: 人工智能领域、java-数据结构、Javase、C语言,希望能帮助到大家!!! 点赞👍收藏❤ 目录 一、KingbaseES金仓数据库简介二、快速入门:金仓数据库下载与安装指南三、“快”…...
DPIN河内AI+DePIN峰会:共绘蓝图,加速构建去中心化AI基础设施新生态
近日,一场聚焦前沿科技融合的盛会——AIDePIN峰会在越南河内成功举办。此次峰会由DPIN、QPIN及42DAO等Web3领域的创新项目联合组织,汇聚了众多Web3行业领袖、技术专家与社区成员。峰会于2025年4月19日举行,其核心议题围绕去中心化物理基础设施…...
vscode和git 踩坑
git init经常 在 vscode push错误问题: 正确姿势:先 GitHub 上建仓库 → git clone 拉到本地 → 再用 VSCode 打开编辑 ❌ 不是:VSCode 里 git init → 再去 GitHub 选个仓库绑定 举个对比 操作流程是否推荐后果GitHub 创建仓库 → git clone → 用 VSC…...
C++11介绍
目录 一、C11的两个小点 1.1、decltype 1.2、nullptr 二、列表初始化 2.1、C98传统的{} 2.2、C11中的{} 2.3、C11中的std::initializer_list 三、右值引用和移动语义 3.1、左值和右值 3.2、左值引用和右值引用 3.3、引用延长生命周期 3.4、左值和右值的参数匹配 3…...
AI数字人:繁荣背后的伦理困境与法律迷局(8/10)
摘要:本文深入剖析 AI 数字人从虚拟走向现实的历程,阐述其融合多技术实现从静态到动态交互的跨越,爆发式应用于各领域带来的商业价值与社会影响,同时直面由此引发的伦理法律挑战,包括身份认同、数据隐私、责任归属及权…...
SOLID 原则在单片机环境下的 C 语言实现示例,结合嵌入式开发常见场景进行详细说明
1. 单一职责原则 (SRP) 定义:一个模块(函数/文件)只负责一个功能。 示例:传感器数据采集与处理分离 // SensorAdc.h - 仅负责ADC原始数据采集 typedef struct { uint16_t (*ReadRaw)(void); // 原始数据读取接口 } SensorAdc; // SensorProcessor.h - 仅负责数据处理…...
RT Thread 发生异常时打印输出cpu寄存器信息和栈数据
打印输出发生hardfault时,当前栈十六进制数据和cpu寄存器信息 在发生 HardFault 时,打印当前栈的十六进制数据和 CPU 寄存器信息是非常重要的调试手段。以下是如何实现这一功能的具体步骤和示例代码。 1. 实现 HardFault 处理函数 我们需要在 HardFault 中捕获异常上下文,…...
SQL 函数进行左边自动补位fnPadLeft和FORMAT
目录 1.问题 2.解决 方式1 方式2 3.结果 1.问题 例如在SQL存储过程中,将1 或10 或 100 长度不足的时候,自动补足长度。 例如 1 → 001 10→ 010 100→100 2.解决 方式1 SELECT FORMAT (1, 000) AS FormattedNum; SELECT FORMAT(12, 000) AS Form…...
Unity中数据和资源加密(异或加密,AES加密,MD5加密)
在项目开发中,始终会涉及到的一个问题,就是信息安全,在调用接口,或者加载的资源,都会涉及安全问题,因此就出现了各种各样的加密方式。 常见的也是目前用的最广的加密方式,分别是:DES、3DES、AES、MD5、XOR(异或) 其中DES、3DES、AES、MD5用在数据加密中偏多,特别是…...
C++初窥门径
const关键字 一、const关键字 修饰成员变量 常成员变量:必须通过构造函数的初始化列表进行初始化,且初始化后不可修改。 示例: class Student { private: const int age; // 常成员变量 public: Student(string name, int age) : age(ag…...
Spring知识点总结
目录 1.什么是spring?你对spring的理解? 2.spring的优缺点? 3.解释一下IOC和AOP? 4.IOC和DI的区别? 5.spring中管理对象注入的方式? 6.自动注入的注解有哪些? 声明bean的注解 Bean的生命…...
Oracle_开启归档日志和重做日志
在Oracle中,类似于MySQL的binlog的机制是归档日志(Archive Log)和重做日志(Redo Log) 查询归档日志状态 SELECT log_mode FROM v$database; – 输出示例: – LOG_MODE – ARCHIVELOG (表示已开启) – NO…...
【金仓数据库征文】-数据库界新兴前列者,本篇带你速懂金仓数据库!
最近写课程设计、搞毕设是不是被数据库折腾到崩溃?动不动就报错、数据迁移还超麻烦!今天挖到个宝藏 —— 国产金仓数据库 KingbaseES,操作超简单,还自带 “翻译器” 帮你迁移数据!性能强还稳定,关键完全免费…...
人工智能与机器学习,谁是谁的子集 —— 再谈智能的边界与演进路径
人工智能(Artificial Intelligence, AI)作为当代最具影响力的前沿技术之一,常被大众简化为 “深度学习” 或 “大模型” 等标签。然而,这种简化认知往往掩盖了AI技术内部结构的复杂性与多样性。事实上,AI并非单一方法的…...
Linux进程学习【进程状态】
🌼🌼前言:在操作系统中,进程是最基本的资源管理单位,而操作系统通过精确管理这些进程的状态来确保系统能够高效运行。进程的状态不仅仅是操作系统设计的一部分,它对系统的性能、稳定性以及资源的分配起着至…...
用 ESP32 模拟 Wiegand 刷卡器:开发门禁系统必备的小工具
网罗开发 (小红书、快手、视频号同名) 大家好,我是 展菲,目前在上市企业从事人工智能项目研发管理工作,平时热衷于分享各种编程领域的软硬技能知识以及前沿技术,包括iOS、前端、Harmony OS、Java、Python等…...
什么是 MCP?与 AI Agent 的关系是什么?
首先先回答一下什么是MCP? 如果你经常使用像Claude这样的大语言模型,你可能已经注意到它们虽然强大,但有时候也有局限性,比如无法获取实时信息或访问特定工具。 模型上下文协议(Model Context Protocol,简…...
Python ZIP文件操作全解析:从基础压缩到高级技巧
目录 一、ZIP文件操作基础三板斧 1.1 创建压缩包 1.2 解压操作 1.3 文件遍历与信息获取 二、进阶技巧:让压缩更智能 2.1 加密压缩实战 2.2 增量更新策略 2.3 性能优化技巧 三、高级场景解决方案 3.1 分卷压缩实现 3.2 跨平台路径处理 3.3 异常处理最佳实…...
Linux:进程的等待
当以一个进程结束时,它会变成僵尸进程,这个僵尸进程如果不处理,就会一直占用CPU资源,如果父进程要回收这个进程会通过进程等待的方式处理,回收子进程只会,会得到进程的退出信息 进程等待 父进程通过进程等…...
玉米产量遥感估产系统的开发实践(持续迭代与更新)
项目地址:项目首页 - maize_yield_estimation:玉米估产的flaskvue项目 - GitCode 开发中,敬请期待。。。 以下是预先写的提纲,准备慢慢补充 一、项目背景与工程目标 业务需求分析 农业遥感估产的行业痛点(数据分散、模型精度不足…...
Python解析地址中省市区街道
Python解析地址中省市区街道 1、效果 输入:海珠区沙园街道西基村 输出: 2、导入库 pip install jionlp3、示例代码 import jionlp as jiotext 海珠区沙园街道西基村 res jio.parse_location(text, town_villageTrue) print(res)...
论文学习:《聚类矩阵正则化指导的层次图池化》
原文标题:Clustering matrix regularization guided hierarchical graph pooling 原文链接:https://www.sciencedirect.com/science/article/abs/pii/S0950705125001558 图池化技术大致可以分为两类:平面图池化和层次图池化。后者通过迭代粗化…...
【金仓数据库征文】- 国产化迁移实战:从Oracle到KingbaseES的平滑过渡
文章目录 引言:国产数据库的崛起与迁移需求一、兼容性架构设计与配置优化1.1 Oracle兼容模式的核心实现1.2 潜在语法差异的深度处理1.3 环境预配置关键技术1.3.1 用户与模式映射1.3.2 字符集与日期格式 1.4 深度兼容模式配置1.4.1 语法兼容开关1.4.2 数据类型映射策…...
「零配置陷阱」:现代全栈工具链的复杂度管控实践
一、工具链膨胀的「死亡螺旋」 2024年典型全栈项目的初始化噩梦: $ npm create vitelatest ✔ Project name: … demo ✔ Select a framework: › React ✔ Select a variant: › TypeScript SWC ✔ Install shadcn/ui? … Yes ✔ Add Storybook? … Yes ✔ Co…...
浅析锁的应用与场景
锁的应用与场景:从单机到分布式 摘要:在多线程和分布式系统中,“锁”是避免资源竞争、保障数据一致性的核心机制。但你真的了解锁吗?什么时候该用锁?用哪种锁?本文通过通俗的比喻和代码示例,带…...
图论---Kruskal(稀疏图)
O( m * log n )。 1,将所有边按权重从小到大排序,调用系统的sort() 2,枚举每条边的 a , b ,权重 if(a、b 不联通) 就将这条边加入集合中 // 最小生成树 —Kruskal算法(稀疏图) #include<iostream> #include<algorithm> using …...
MySQL 从入门到精通:第二篇 - 数据类型、约束与索引
1. MySQL数据类型详解 数值类型 整数类型 -- 常用整数类型及范围 CREATE TABLE integer_types (tiny_col TINYINT, -- 1字节,有符号(-128~127),无符号(0~255)small_col SMALLINT, -- 2字节,有符号(-32768~32767),无符号(0~65535)medium_col MEDIUMINT,...
基于AI技术的高速公路交通引流系统设计与应用研究
基于AI技术的高速公路交通引流系统设计与应用研究 1. 研究背景与意义 1.1 交通系统演化脉络 1.1.1 发展阶段划分 机械化时代(1950-1990):固定式信号控制信息化时代(1991-2010):SCATS/SCOOT系统智能化时代…...
n8n 中文系列教程_09. 从原始需求到精准实现:n8n节点选择指南
在自动化工作流工具n8n中,正确选择和使用节点是高效实现需求的关键。本文将从需求分析入手,逐步解析触发节点与执行节点的区别,梳理n8n的节点分类逻辑,并揭示外部服务节点的本质,帮助您精准匹配需求与实现方案。无论您…...
P19:Inception v1算法实战与解析
🍨 本文为🔗365天深度学习训练营 中的学习记录博客🍖 原作者:K同学啊 一、模型结构 Inception V1 的主要特点是在一个网络中同时使用不同大小的卷积核(1x1、3x3、5x5)和池化操作来提取多尺度特征。以下是…...
day32 学习笔记
文章目录 前言一、霍夫变换二、标准霍夫变换三、统计概率霍夫变换四、霍夫圆变换 前言 通过今天的学习,我掌握了霍夫变换的基本原本原理及其在OpenCV中的应用方法 一、霍夫变换 霍夫变换是图像处理中的常用技术,主要用于检测图像中的直线,圆…...
2025时间序列都有哪些创新点可做——总结篇
作为AI和数据科学的核心方向之一,时间序列在2025年依然保持着强劲的发展势头,稳站各大顶会顶刊投稿主题前列。 关于它的研究,目前在结合传统统计方法和深度学习的基础上,已延伸至频域等数理工具与神经网络的交叉创新。同时针对垂…...
头歌实训之索引
🌟 各位看官好,我是maomi_9526! 🌍 种一棵树最好是十年前,其次是现在! 🚀 今天来学习C语言的相关知识。 👍 如果觉得这篇文章有帮助,欢迎您一键三连,分享给更…...
通讯的基础概念:涵盖串行通信、并行通信、TCP、UDP、Socket 等关键概念和技术
一、通信基础概念 1. 串行通信与并行通信 串行通信 定义:通过一条线路逐位传输数据,每个字节包含起始位、数据位、校验位和停止位。特点: 传输稳定,但速度较慢(因逐位传输)。常用接口:RS-232、…...
Uni-App 多端电子合同开源项目介绍
项目概述 本项目是一款基于 uni-app框架开发的多端电子合同管理平台,旨在为企业及个人用户提供高效、安全、便捷的电子合同签署与管理服务。项目创新性地引入了 “证据链”与“非证据链”两种签署模式,满足不同场景下的签署需求,支持多种签署…...
一个非常快速的 Latex 入门教程【Part 1】
目录 1.LaTex简介 2.LaTex 中最基础的格式化命令 2.1加粗,斜体,下划线,添加新段落 2.2文档分节 2.3 图片 2.4 LaTeX 中列表的创建 无序列表 有序列表 2.5对数学公式的排版 2.6表格 1.LaTex简介 LaTex的主要优势是它会将文…...
用Obsidian四个插件打造小说故事关联管理系统:从模板到图谱的全流程实践
用Obsidian四个插件打造小说故事关联管理系统:从模板到图谱的全流程实践 一、前言:为什么需要故事关联管理系统 在小说创作中,复杂的人物关系、交错的情节线和多维的世界观常导致创作混乱。本文将通过 Dataview(数据查询…...
C++ 日志系统实战第三步:熟悉掌握各种设计模式
全是通俗易懂的讲解,如果你本节之前的知识都掌握清楚,那就速速来看我的项目笔记吧~ 相关技术知识补充,也是最后的补充知识了~ 下文将加入项目代码编写! 目录 设计模式 单例模式 饿汉模式 懒汉模式 工厂模式 简单…...
[ESP-IDF]:esp32-camera 使用指南 ESP32S3-OV2640 用例测试
【核知坊】:释放青春想象,码动全新视野。 我们希望使用精简的信息传达知识的骨架,启发创造者开启创造之路!!! 内容摘要:esp32-camera 组件为 ESP32 系列 SoC 提供了兼容的图…...
在统信UOS/麒麟Kylin OS中创建网页桌面快捷方式
在统信UOS/麒麟Kylin OS中创建网页桌面快捷方式 本文将详细介绍如何在统信UOS或麒麟KYLINOS中使用命令行创建一个网页桌面快捷方式,以方便构建云桌面模板及镜像模板。欢迎大家浏览、分享和转发!请关注我以获取更多技术分享。 1. 查看系统信息 首先&am…...
SQLite 是什么?
📌 一、SQLite 是什么? SQLite 是一个轻量级、嵌入式数据库,意思是它直接集成在你的 App 内部,不需要单独安装数据库服务端。 ✅ 特点: 特点说明本地使用所有数据保存在手机内部存储文件形式数据以 .db 文件形式存储…...
恒创科技「香港大带宽云」新老用户专享实例及热门配置
全球化数字浪潮下,高带宽应用正深度重构各行业运营模式——从跨境电商、流媒体与视频点播,到在线游戏与云游戏加速,涵盖所有高并发、强交互的业务场景。在此背景下,企业对高性能 IT 基础架构的需求持续升级,以此来支持…...
fpga系列 HDL:verilog latch在fpga中的作用 避免latch的常见做法
目录 Latch在FPGA中的作用Quartus中有关latch的警告⚠避免Latch的常见做法1. if-else 语句未覆盖所有条件生成Latch的代码:修复后的代码: 2. case语句未覆盖所有分支生成Latch的代码:修复后的代码: 3. 组合逻辑中缺少默认赋值生成…...
java配置
环境变量...
解决虚拟主机ping不通本地主机问题
win11 1 问题 虚拟主机和本地主机在同一网段。 2 解决方案 以win11为例: 设置 -> 网络和 Internet -> 高级网路设置 -> Windows 防火墙 -> 高级设置 -> 入站规则 -> 新建规则 需要设置:规则类型、 协议和端口、名称,其…...
Move Registry 发布,实现 Sui 的超级互操作性
Move Registry(MVR)的到来对 Sui 来说是一件大事。MVR 是一个功能齐全的链上包管理系统,提升了整个生态的可发现性、可信度和互操作性。Sui 本身就是最具互操作性的链之一,凭借 Move 语言和可编程交易区块(PTBs&#x…...