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

【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名

【LeetCode刷题】Day 14

  • 题目1:153.寻找旋转排序数组中的最小值
    • 思路分析:
    • 思路1:二分查找:以A为参照
    • 思路2:二分查找,以D为参照
  • 题目2:LCR 173.点名
    • 思路分析:
    • 思路1:遍历查找
    • 思路2:哈希表
    • 思路3:异或
    • 思路4:求和
    • 思路5:二分查找

在这里插入图片描述

题目1:153.寻找旋转排序数组中的最小值

在这里插入图片描述

思路分析:

在这里插入图片描述

O(logN)来做,我们就直接二分查找。所以第一步,去寻找其中的二段性。
这里我们可以有两种方式:以A为参照,以D为参照,来找C点的值。

思路1:二分查找:以A为参照

以A为参照:
1. 二段性:[A-B段都大于等于A][C-D段都小于A]
2. 迭代:C点在left外,所以left=mid+1,C在right内,所以right=mid,没有-1上面就不用+1mid=left+(right-left)/2
特殊情况:翻转后刚好是原来的升序数组,此时以A为参照会把该数组当成全部A-B段,会不断向外找,直到left<right不成立而结束,该情况需要特殊处理。

代码实现:

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

思路2:二分查找,以D为参照

以C为参照:
1. 二段性:[A-B段都大于D][C-D段都小于等于D]
2. 迭代:C点在left外,所以left=mid+1,C在right内,所以right=mid,没有-1上面就不用+1mid=left+(right-left)/2
无特殊情况:若翻转后刚好是原来的升序数组,会把整个数组当成C-D段,以D为参照,会往下找,就可以找到C,所以无需处理

代码实现:

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

LeetCode链接:153.寻找旋转排序数组中的最小值


题目2:LCR 173.点名

在这里插入图片描述

思路分析:

这道题很简单,有很多思路,简单的我就直接讲一下过程就OK。

思路1:遍历查找

遍历数组,寻找后一位减前一位的差为2的数,找到就返回,没找到就返回最后一个数的下一个。

思路2:哈希表

分别将数据导入哈希表,然后查看哪个数的个数为零,返回该值。

思路3:异或

数组records[0]~records[size-1] 与 当前数组各个数异或,若结果为x,则返回x;当x等于0时,需要格外处理,有两种情况,缺0或者是最后一个数后面的数。需要特殊处理:比对第一个数是不是0就可以。

思路4:求和

数组records[0]~records[size-1] 的和减去当前数组的和。若结果为x,则返回x;当x等于0时,需要格外处理,与思路3一样。

思路5:二分查找

这道题的二分查找很有趣,需要细节,能发现二段性,这题就相当简单。我们可以发现这个升序数组是从0到n-1,所以我们可以发现这样一个
二段性:[缺失值前面,下标与值相同][缺失值后面,下标与值不同],我们找到右区间的左值的下标就是缺失的值。
细节处理:当所有数的值和下标相同时,则返回left+1.

代码实现:

class Solution {
public:int takeAttendance(vector<int>& records) {int left=0,right=records.size()-1;while(left<right){int mid=left+(right-left)/2;if(mid==records[mid]) left=mid+1;else right=mid;}//处理细节:如果缺失的是最后一位if(left==records[left]) return left+1;else return left;}
};

LeetCode链接:LCR 173.点名


世界舞台就是草台班子,大胆尝试吧!!! ~天天开心🎈
请添加图片描述

相关文章:

【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名

【LeetCode刷题】Day 14 题目1&#xff1a;153.寻找旋转排序数组中的最小值思路分析&#xff1a;思路1&#xff1a;二分查找&#xff1a;以A为参照思路2&#xff1a;二分查找&#xff0c;以D为参照 题目2&#xff1a;LCR 173.点名思路分析&#xff1a;思路1&#xff1a;遍历查找…...

使用python绘制小提琴图

使用python绘制小提琴图 小提琴图效果代码 小提琴图 小提琴图&#xff08;Violin Plot&#xff09;是一种结合了箱线图和核密度估计图的图形&#xff0c;用于显示数据分布的情况。它不仅展示了数据的四分位数、最大值和最小值&#xff0c;还通过密度曲线展示了数据的分布形状。…...

【C++】6-7 你好,输出的格式控制(三角形)

6-7 你好&#xff0c;输出的格式控制&#xff08;三角形&#xff09; 分数 10 全屏浏览 切换布局 作者 向训文 单位 惠州学院 完善程序&#xff1a;输入行数rows&#xff08;大于0&#xff09;&#xff0c;第一行输出rows个*&#xff0c;接下来每行的*个数减1&#xff0c;直…...

力扣每日一题 6/1

2928.给小朋友们分糖果[简单] 题目&#xff1a; 给你两个正整数 n 和 limit 。 请你将 n 颗糖果分给 3 位小朋友&#xff0c;确保没有任何小朋友得到超过 limit 颗糖果&#xff0c;请你返回满足此条件下的 总方案数 。 示例 1&#xff1a; 输入&#xff1a;n 5, limit 2 …...

决定短视频打开率的要素:成都鼎茂宏升文化传媒公司

​ 在当下这个短视频盛行的时代&#xff0c;无论是个人创作者还是企业品牌&#xff0c;都希望通过短视频平台获得更多的曝光和关注。然而&#xff0c;如何让自己的短视频在众多内容中脱颖而出&#xff0c;吸引用户的点击和观看&#xff0c;成为了摆在我们面前的重要问题。成都…...

解决通过包管理器下载 Sharp 时遇到的二进制文件下载问题

sharp 是一个流行的 Node.js 库&#xff0c;用于高性能的图片处理。它依赖于预构建的 libvips 二进制文件&#xff0c;这些文件通常是从官方仓库下载的。 但在某些地区的网络环境下&#xff0c;直接下载可能会因为网络限制而失败。 通过在命令行中分别执行以下两行内容即可&a…...

反序输出c++

题目描述 输入n个数,要求程序按输入时的逆序把这n个数打印出来&#xff0c;已知整数不超过100个。也就是说&#xff0c;按输入相反顺序打印这n个数。 输入 输入一行共有n个数&#xff0c;每个数之间用空格隔开。 输出 如题要求&#xff1a;一行&#xff0c;共有n个数&…...

C++ 封装线程池(结合QT支持信号机制)

纯C风格线程池 纯C 风格线程池可参考这篇文章 https://llfc.club/category?catid225RaiVNI8pFDD5L4m807g7ZwmF#!aid/2c2IJUcCUOfzEQQRRdOXYIZuCjP 视频教程 相关线程池和并发编程的视频可以看看这个连接&#xff1a; https://www.bilibili.com/video/BV1Xt421H7M7/?vd_s…...

c# 学习教程

打印语句 折叠代码 变量 整形 浮点型 特殊类型...

【ros2】入门

ros2 在机器人控制&#xff0c;无人机飞行控制&#xff0c;自动驾驶领域&#xff0c;ros2可是如日中天的存在。无论是学习其架构设计&#xff0c;还是使用ros2开发机器人&#xff0c;ros2的是一个很错的选择。 安装 在ros2的,推荐“小鱼”的工具 wget http://fishros.com/i…...

网络安全基础技术扫盲篇 — 名词解释之“数据包“

用通俗易懂的话说&#xff1a; 数据包就像是一个信封。当你写信给某个人时&#xff0c;你将内容写在一张纸上&#xff0c;然后将纸叠起来并放入信封中&#xff0c;就形成了一个完整要发送的数据内容。信封上有发件人和收件人的详细地址&#xff0c;还有一些其他必要的信息&…...

26 _ 虚拟DOM:虚拟DOM和实际的DOM有何不同?

虚拟DOM是最近非常火的技术&#xff0c;两大著名前端框架React和Vue都使用了虚拟DOM&#xff0c;所以我觉得非常有必要结合浏览器的工作机制对虚拟DOM进行一次分析。当然了&#xff0c;React和Vue框架本身所蕴含的知识点非常多&#xff0c;而且也不是我们专栏的重点&#xff0c…...

C语言(内存函数)

Hi~&#xff01;这里是奋斗的小羊&#xff0c;很荣幸各位能阅读我的文章&#xff0c;诚请评论指点&#xff0c;欢迎欢迎~~ &#x1f4a5;个人主页&#xff1a;小羊在奋斗 &#x1f4a5;所属专栏&#xff1a;C语言 本系列文章为个人学习笔记&#xff0c;在这里撰写成文一…...

JVM之【执行引擎】

执行引擎 执行引擎是JVM的核心组件之一&#xff0c;它负责将Java字节码文件转换为机器指令并执行。这一过程涉及多个组成部分&#xff0c;各部分协同工作来完成字节码到机器指令的转换和执行。以下是执行引擎的主要组成部分及其作用&#xff1a; 1. 解释器&#xff08;Interp…...

maven部署到私服

方法一:网页上传 1、账号登录 用户名/密码 2、地址 http://自己的ip:自己的端口/nexus 3、查看Repositories列表&#xff0c;选择Public Repositories&#xff0c;确定待上传jar包不在私服中 4、选择3rd party仓库&#xff0c;点击Artifact Upload页签 5、GAV Definition选…...

Android精通值Fragment的使用 —— 不含底层逻辑(五)

1. Fragment 使用Fragment的目标&#xff1a;根据列表动态显示内容&#xff0c;更简洁显示界面、查找界面 eg. 使用新闻列表动态显示新闻 1.1 Fragment的特性 具备生命周期 —— 可以动态地移除一些Fragment必须委托在Activity中使用可以在Activity中进行复用 1.2 Fragmen…...

apache大数据各组件部署搭建(超级详细)

apache大数据数仓各组件部署搭建 第一章 环境准备 1. 机器规划 准备3台服务器用于集群部署,系统建议CentOS7+,2核8G内存 172.19.195.228 hadoop101 172.19.195.229 hadoop102 172.19.195.230 hadoop103 [root@hadoop101 ~]# cat /etc/redhat-release CentOS Linux rele…...

Servlet搭建博客系统

现在我们可以使用Servlet来搭建一个动态(前后端可以交互)的博客系统了(使用Hexo只能实现一个纯静态的网页,即只能在后台自己上传博客)。有一种"多年媳妇熬成婆"的感觉。 一、准备工作 首先创建好项目,引入相关依赖。具体过程在"Servlet的创建"中介绍了。…...

NextJs 渲染篇 - 什么是CSR、SSR、SSG、ISR 和服务端/客户端组件

NextJs 渲染篇 - 什么是CSR、SSR、SSG、ISR 和服务端/客户端组件 前言一. 什么是CSR、SSR、SSG、ISR1.1 CSR 客户端渲染1.2 SSR 服务端渲染1.3 SSG 静态站点生成① 没有数据请求的页面② 页面内容需要请求数据③ 页面路径需要获取数据 1.4 ISR 增量静态再生1.5 四种渲染方式的对…...

Python 二叉数的实例化及遍历

首先创建一个这样的二叉树&#xff0c;作为我们今天的实例。实例代码在下方。 #创建1个树类型 class TreeNode:def __init__(self,val,leftNone,rightNone):self.valvalself.leftleftself.rightright #实例化类 node1TreeNode(5) node2TreeNode(6) node3TreeNode(7) node4Tre…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

学校招生小程序源码介绍

基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码&#xff0c;专为学校招生场景量身打造&#xff0c;功能实用且操作便捷。 从技术架构来看&#xff0c;ThinkPHP提供稳定可靠的后台服务&#xff0c;FastAdmin加速开发流程&#xff0c;UniApp则保障小程序在多端有良好的兼…...

在四层代理中还原真实客户端ngx_stream_realip_module

一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡&#xff08;如 HAProxy、AWS NLB、阿里 SLB&#xff09;发起上游连接时&#xff0c;将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后&#xff0c;ngx_stream_realip_module 从中提取原始信息…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

Spring是如何解决Bean的循环依赖:三级缓存机制

1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间‌互相持有对方引用‌,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...

JVM虚拟机:内存结构、垃圾回收、性能优化

1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...

招商蛇口 | 执笔CID,启幕低密生活新境

作为中国城市生长的力量&#xff0c;招商蛇口以“美好生活承载者”为使命&#xff0c;深耕全球111座城市&#xff0c;以央企担当匠造时代理想人居。从深圳湾的开拓基因到西安高新CID的战略落子&#xff0c;招商蛇口始终与城市发展同频共振&#xff0c;以建筑诠释对土地与生活的…...

STM32HAL库USART源代码解析及应用

STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...

在 Spring Boot 项目里,MYSQL中json类型字段使用

前言&#xff1a; 因为程序特殊需求导致&#xff0c;需要mysql数据库存储json类型数据&#xff0c;因此记录一下使用流程 1.java实体中新增字段 private List<User> users 2.增加mybatis-plus注解 TableField(typeHandler FastjsonTypeHandler.class) private Lis…...