当前位置: 首页 > news >正文

算法修炼之路之二分查找

目录

一:三大二分介绍及模板

1.普通二分

2.查找左右边界的二分及模板 

二:LeetCode OJ练习

1.第一题

2.第二题 

 3.第三题

 4.第四题

 5.第五题

 6.第六题

一:三大二分介绍及模板

1.普通二分

这里通过一道题来引出普通二分及模板

LeetCode_704 二分查找

画图分析:

 

具体代码:

int search(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) right=mid-1;else if(nums[mid]<target) left=mid+1;else return mid;}return -1;}

普通二分模板

 

2.查找左右边界的二分及模板 

 通过题来引出

LeetCode_34 在排序数组中查找元素的第一个和最后一个位置

画图分析:

 

具体代码:

vector<int> searchRange(vector<int>& nums, int target) {//处理边界情况if(nums.size()==0) return {-1,-1};int left=0,right=nums.size()-1;int begin=0;//查找左端点while(left<right){int mid=left+(right-left)/2;if(nums[mid]<target) left=mid+1;else right=mid;}//判断是否有结果if(nums[left]==target) begin=left;//标记一下左端点else return {-1,-1};//查找右端点left=0,right=nums.size()-1;while(left<right){int mid=left+(right-left+1)/2;if(nums[mid]>target) right=mid-1;else left=mid;}return {begin,left};}

左右边界的二分模板: 

二:LeetCode OJ练习

1.第一题

LeetCode_69 x的平方根

画图分析:

 

具体代码:

int mySqrt(int x) {//处理边界情况if(x<1) return 0;int left=1,right=x;//防止当x=INT_MAX时,right-0+1操作直接越界的while(left<right){long long mid=left+(right-left+1)/2;//防止越界if(mid*mid>x) right=mid-1;else left=mid;}return left;}

2.第二题 

 LeetCode_35 搜索插入位置

画图分析:

 

具体代码:

 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;else right=mid;}//处理在数组末尾插入的情况if(nums[left]<target) return left+1;else return left;}

 3.第三题

LeetCode_852 山脉数组的峰顶索引

画图分析:

 

具体代码:

 int peakIndexInMountainArray(vector<int>& arr) {int left=1,right=arr.size()-2;//首尾不可能是结果while(left<right){int mid=left+(right-left+1)/2;if(arr[mid]>arr[mid-1]) left=mid;else right=mid-1;}return left;}

 4.第四题

LeetCode_162 寻找峰值

 画图分析:

具体代码:

 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;else left=mid+1;}return left;}

 5.第五题

LeetCode_153 寻找旋转排序数组中的最小值

画图分析:

 

具体代码:

int findMin(vector<int>& nums) {int left=0,right=nums.size()-1;int t=nums[right];while(left<right){int mid=left+(right-left)/2;if(nums[mid]>t) left=mid+1;else right=mid;}return nums[left];}

 6.第六题

LeetCode_LCR 173 点名

画图分析:

 

具体代码:

int takeAttendance(vector<int>& records) {int left=0,right=records.size()-1;while(left<right){int mid=left+(right-left)/2;if(records[mid]==mid) left=mid+1;else right=mid;}//处理细节问题return records[left]==left? left+1:left;}

相关文章:

算法修炼之路之二分查找

目录 一:三大二分介绍及模板 1.普通二分 2.查找左右边界的二分及模板 二:LeetCode OJ练习 1.第一题 2.第二题 3.第三题 4.第四题 5.第五题 6.第六题 一:三大二分介绍及模板 1.普通二分 这里通过一道题来引出普通二分及模板 LeetCode_704 二分查找 画图分析: 具体代…...

OpenAI预计明年将推出“代理”系统

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…...

每日OJ题_牛客_重排字符串_贪心_C++_Java

目录 牛客_重排字符串_贪心 题目解析 C代码 Java代码 牛客_重排字符串_贪心 重排字符串 (nowcoder.com) 描述&#xff1a; 小红拿到了一个只由小写字母组成的字符串。她准备把这个字符串重排&#xff08;只改变字母的顺序&#xff0c;不改变数量&#xff09; …...

Python 进阶部分详细整理

1. 面向对象编程&#xff08;OOP&#xff09; 面向对象编程 (OOP) 是一种通过将程序中的数据和功能封装为对象的编程范式。OOP 基于四个核心概念&#xff1a;类与对象、继承、封装与多态。 类与对象 类&#xff08;Class&#xff09;&#xff1a;类是创建对象的蓝图或模板。它…...

[ RK3566-Android11 ] 关于移植 RK628F 驱动以及后HDMI-IN图像延迟/无声等问题

问题描述 由前一篇文章https://blog.csdn.net/jay547063443/article/details/142059700?fromshareblogdetail&sharetypeblogdetail&sharerId142059700&sharereferPC&sharesourcejay547063443&sharefromfrom_link&#xff0c;移植HDMI-IN部分驱动后出现&a…...

【黑马点评】 使用RabbitMQ实现消息队列——2.使用RabbitMQ监听秒杀下单

2 使用RabbitMQ实现消息队列 2.1 修改\hm-dianping\pom.xmlpom.xml文件 添加RabbitMQ的环境 <!-- RabbitMQ--> <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-amqp</artifactId> </depe…...

业务封装与映射 -- OTUk/ODUk/OPUk开销帧结构

开销是为了保证净荷正常、灵活传送所必须附加的供网络运行、管理和维护&#xff08;OAM&#xff09;使用的字节。 OTN电层开销包括OTUk开销、ODUk开销、OPUk开销、OTUCn开销、ODUCn开销、OPUCn开销和帧对齐开销。 SM开销属于OTU开销&#xff0c;占用3个字节&#xff1b;PM开销…...

Vim基本用法

Vim用法 一、基本模式 1. 普通模式&#xff08;Normal Mode&#xff09; 移动光标 基本移动&#xff1a;使用方向键&#xff08;h左移、j下移、k上移、l右移&#xff09;&#xff0c;也可以使用 H&#xff08;移到屏幕顶部&#xff09;、M&#xff08;移到屏幕中间&#xff…...

python 实现Tarjan 用于在有向图中查找强连通分量的算法

Tarjan 用于在有向图中查找强连通分量的算法介绍 Tarjan算法是一种用于在有向图中查找强连通分量的高效算法&#xff0c;由Robert Tarjan在1972年提出。强连通分量是指在有向图中&#xff0c;如果从顶点u到顶点v以及从顶点v到顶点u都存在一条路径&#xff0c;那么顶点u和顶点v…...

Qt开发技巧(十五)字符串去除空格,跨网段搜索不生效,设置图片显示失败问题,表格视图的批量删除,主动判断字串编码,开启向前查询的属性,画家类载入html来绘制

继续讲一些Qt开发中的技巧操作&#xff1a; 1.字符串去除空格 我们经常会遇到字符串重去除空格的情况&#xff0c;对于QString去除空格&#xff0c;有多种场景&#xff0c;可能需要去除左侧、右侧、所有等位置的空格&#xff1b; //字符串去空格 -1移除左侧空格 0移除所有空格…...

【机器学习】智驭未来:探索机器学习在食品生产中的革新之路

&#x1f4dd;个人主页&#x1f339;&#xff1a;Eternity._ &#x1f339;&#x1f339;期待您的关注 &#x1f339;&#x1f339; ❀目录 &#x1f50d;1. 引言&#xff1a;探索机器学习在食品生产中的革新之路&#x1f4d2;2. 机器学习在食品质量控制中的应用&#x1f31e;实…...

Ubuntu 安装CUDA并使用Docker配置Pytorch环境

文章目录 参考安装顺序Nvidia GPU driverDockerNvidia Container ToolkitDocker PyTorch 1. Nvidia GPU Driver2. Docker 安装&#xff08;使用apt存储库进行安装&#xff09;3. Nvidia Container Toolkit3.1 Docker测试GPU 参考 安装顺序 Nvidia GPU driver Docker Nvidia…...

【论文阅读】Simulating 500 million years of evolution with a language model

Simulating 500 million years of evolution with a language model 1、概述 展示了语言模型在蛋白质设计和进化模拟方面的能力。通过对 ESM3 模型的研究,发现其能够生成与自然蛋白质差异较大且具有功能的新蛋白质,如新型绿色荧光蛋白(GFP),表明语言模型可以达到自然进化…...

detectron2/layers源码笔记

from .wrappers import ( BatchNorm2d, Conv2d, #在torch.conv2d的基础上集成了norm层和activation层 ConvTranspose2d, cat, interpolate, Linear, nonzero_tuple, #nonzero_tuple(x)得到tuple of 每个维度的索引 cross_entropy, empty_input_loss_func…...

LLM+知识图谱新工具! iText2KG:使用大型语言模型构建增量知识图谱

iText2KG是一个基于大型语言模型的增量知识图谱构建工具&#xff0c;通过从文本文档中提取实体和关系来逐步构建知识图谱。该工具具有零样本学习能力&#xff0c;能够在无需特定训练的情况下&#xff0c;在多个领域中进行知识提取。它包括文档提炼、实体提取和关系提取模块&…...

React基础-快速梳理

React介绍 React由Meta公司开发&#xff0c;是一个用于构建Web和原生交互界面的库 React的优势 相较于传统基于DOM开发的优势 组件化的开发方式不错的性能 相较于其它前端框架的优势 丰富的生态跨平台支持 开发环境创建 create-react-app是一个快速创建React开发环境的…...

H.264编解码 - NALU详解

一、概述 NALU(Network Abstraction Layer Unit)是H.264编解码中的一个重要概念。H.264是一种视频压缩标准,将视频数据分割成一系列的NALU。每个NALU都是一个独立的数据单元,包含视频压缩后的一个片段。每个NALU都有自己的起始码和长度前缀,用于标识NALU的起始位置和长度。…...

vSAN02:容错、存储策略、文件服务、快照与备份、iSCSI

目录 vSAN容错条带化存储策略1. 创建新策略2. 应用存储策略 vSAN文件服务文件服务快照与备份 vSAN iSCSI目标服务 vSAN容错 FTT&#xff1a;Fault to Tolerance 允许故障数 故障域&#xff1a;每一台vSAN主机是一个故障域 - 假设3台超融合&#xff08;3计算1存储&#xff09;&…...

图解C#高级教程(四):协变、逆变

本章的主题是可变性&#xff08;variance&#xff09;&#xff0c;这里的可变性更多的是指基类和派生类之间的转换。可变性分为三种&#xff1a;协变&#xff08;covariance&#xff09;、逆变&#xff08;contravariance&#xff09;和不变&#xff08;invariance&#xff09;…...

详解CSS中的伪元素

4.3 伪元素 可以把样式应用到文档树中根本不存在的元素上。 ::first-line 文本中的第一行 ::first-letter 文本中的第一个字母 ::after 元素之后添加 ::before 元素之前 代码&#xff1a; <!DOCTYPE html> <html> <head><meta charset"utf-8&q…...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?

编辑&#xff1a;陈萍萍的公主一点人工一点智能 未来机器人的大脑&#xff1a;如何用神经网络模拟器实现更智能的决策&#xff1f;RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战&#xff0c;在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式&#xff0c;可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

QMC5883L的驱动

简介 本篇文章的代码已经上传到了github上面&#xff0c;开源代码 作为一个电子罗盘模块&#xff0c;我们可以通过I2C从中获取偏航角yaw&#xff0c;相对于六轴陀螺仪的yaw&#xff0c;qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

MMaDA: Multimodal Large Diffusion Language Models

CODE &#xff1a; https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA&#xff0c;它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构&#xf…...

Python实现prophet 理论及参数优化

文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候&#xff0c;写过一篇简单实现&#xff0c;后期随着对该模型的深入研究&#xff0c;本次记录涉及到prophet 的公式以及参数调优&#xff0c;从公式可以更直观…...

华为OD机试-食堂供餐-二分法

import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...

现代密码学 | 椭圆曲线密码学—附py代码

Elliptic Curve Cryptography 椭圆曲线密码学&#xff08;ECC&#xff09;是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础&#xff0c;例如椭圆曲线数字签…...

什么是EULA和DPA

文章目录 EULA&#xff08;End User License Agreement&#xff09;DPA&#xff08;Data Protection Agreement&#xff09;一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA&#xff08;End User License Agreement&#xff09; 定义&#xff1a; EULA即…...