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

LC记录一:寻找旋转数组最小值、判断旋转数组是否存在给定元素

文章目录

  • 33.搜索旋转排序数组
  • 81.搜索旋转排序数组||
  • 153.寻找旋转排序数组中的最小值
  • 154.寻找旋转排序数组中的最小值||
  • 参考链接

33.搜索旋转排序数组

https://leetcode.cn/problems/search-in-rotated-sorted-array/description/
在这里插入图片描述
下面这张图片是LC154题官方题解提供的一个图片:我转载一下:
在这里插入图片描述

上图与本题唯一的区别是:本题题目约束数组中不包含重复元素,所以在某次旋转后,数组一定会被分为「左数组」和「右数组」
其中「左数组」和「右数组」分别单调递增。有一种特殊情况需要注意:
当数组旋转数组长度个单位后,仍然是元素组,此时这个数组也被称为「右数组」,你可能要问为什么要将其称为「右数组」而不是「左数组」,可以使用123三个元素依次旋转就能够观察到,最后一定是「右数组」同时右数组在本题以及后面的题目中,都会作为划分左右数组边界的关键所在。
第一题实现思路:

  • 采用二分法,计算出mid都应的值:num[mid]
  • 如果num[mid] == target,则直接返回。
  • 如果不相等,则需要判断,nums[mid] 和 target的大小关系。此时就涉及到 target 和 nums[mid] 分别位于左边界还是右边界的问题。
  • 我划分的标准是使用 target 和 nums[r] 对比,如果 target > nums[r] 则此时 target 一定位于左边界,如果 target < nums[r] 则此时 target一定位于右边界。在本题中由于不包含重复元素,所以不存在target == nums[r] 的情况,下面一题是这种情况。
  • 当 target 划分好左边边界后,需要使用 nums[mid] 和 nums[r] 的大小关系判断出 mid 位于左右边界的情况,对于左右边界的值分别进行比较。
    • target 位于左边界时,mid 位于右边界:r = mid - 1。
    • target 位于左边界时,mid 位于左边界:target > nums[mid] 时,l = mid + 1;target < nums[mid] 时,r = mid - 1;两者相等的情况上面已经判断过了
    • target 位于右边界时,mid 位于左边界:l = mid + 1。
    • target 位于右边界时,mid 位于右边界:target > nums[mid] 时,l = mid + 1;target < nums[mid] 时,r = mid - 1;

具体代码如下:

class Solution {public int search(int[] nums, int target) {int l = 0, r = nums.length - 1;while(l < r){int mid = (l + r) / 2;if(nums[mid] == target){return mid;}if(target > nums[r]){// target位于左边界if(nums[mid] < nums[r]){// mid位于右边界r = mid - 1;}else{// mid位于左边界if(nums[mid] > target){r = mid - 1;}else{l = mid + 1;}}}else{// target位于右边界if(nums[mid] > nums[r]){// mid位于左边界l = mid + 1;}else{// mid位于右边界if(nums[mid] > target){r = mid - 1;}else{l = mid + 1;}}}}System.out.println(l);return nums[l] == target ? l : -1;}
}

81.搜索旋转排序数组||

https://leetcode.cn/problems/search-in-rotated-sorted-array-ii/
在这里插入图片描述
此题就是对上面题目的扩展,上一题目中判断是否位于左边界,直接和nums[r] 相比,大于则位于左边界,随后直接位于右边界,根本不考虑相等的情况,因为第一题元素值不相等,根本不存在 == nums[r] 这中情况。
本题存在相等元素,只需要在上一题的判断的基础上,添加上是否 等于 nums[r] 这种情况即可。
具体见代码及注释:

class Solution {public boolean search(int[] nums, int target) {int l = 0, r = nums.length - 1;while(l < r){int mid = (l + r) / 2;if(nums[mid] == target){return true;}if(target > nums[r]){// 此时target位于左边界数组if(nums[mid] == nums[r]){// mid不确定位于左边界,还是右边界,此时只能缩小右边界的范围r = r - 1;}else if(nums[mid] < nums[r]){// mid位于右边界r = mid - 1;}else{// mid位于左边界if(nums[mid] > target){r = mid - 1;}else{l = mid + 1;}}}else if(target < nums[r]){// 此时target位于右边界数组if(nums[mid] == nums[r]){// mid不确定位于左边界,还是右边界,此时只能缩小右边界的范围r = r - 1;}else if(nums[mid] > nums[r]){// mid位于左边界l = mid + 1;}else{// mid位于右边界if(nums[mid] > target){r = mid - 1;}else{l = mid + 1;}}}else if(target == nums[r]){// target直接和右边界相等,则直接返回return true;}}return nums[l] == target;}
}

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

https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/
在这里插入图片描述
这道题目寻找旋转数组的最小值,就是旋转数组的左右边界交界处。
仍然可以利用二分取得mid后和nums[r] 进行比较。

  • nums[mid] > nums[r] : 此时mid位于左边界,肯定不符合要求,直接 l = mid + 1;
  • nums[mid] < nums[r] : 此时mid位于右边界,由于二分查找计算的mid是向下取整的,所以 l <= mid < r ;所以此时直接令 r = mid 即可,不需要额外mid - 1。

代码展示:

class Solution {public int findMin(int[] nums) {int l = 0, r = nums.length - 1;while(l < r){int mid = (l + r) / 2;if(nums[mid] > nums[r]){// 此时mid位于左边界l = mid + 1;}else{// 此时mid位于右边界,由于向下取整,直接 mid = r 主要考虑到r可能此时就是右边界函数的最左边小值r = mid;}}return nums[l];}
}

154.寻找旋转排序数组中的最小值||

https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array-ii/description/
在这里插入图片描述
如果对与1题到2题的演化关系比较熟练了,那么此时从3题演化到4题,也可以类比,在3题的基础上添加nums[mid] == num[r] 相等条件的判断即可。
代码演示:

class Solution {public int findMin(int[] nums) {int len = nums.length;int l = 0, r = len - 1;while(l < r){int mid = (l + r) / 2;if(nums[mid] > nums[r]){// 此时m位于左排序数组中l = mid + 1;}else if(nums[mid] < nums[r]){// 此时m位于右排序数组中r = mid;}else{r = r - 1;}}return nums[l];}
}

对于第四题可以参考下述链接加深理解。

参考链接

https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array-ii/

相关文章:

LC记录一:寻找旋转数组最小值、判断旋转数组是否存在给定元素

文章目录 33.搜索旋转排序数组81.搜索旋转排序数组||153.寻找旋转排序数组中的最小值154.寻找旋转排序数组中的最小值||参考链接 33.搜索旋转排序数组 https://leetcode.cn/problems/search-in-rotated-sorted-array/description/ 下面这张图片是LC154题官方题解提供的一个图…...

关于 JVM 个人 NOTE

目录 1、JVM 的体系结构 2、双亲委派机制 3、堆内存调优 4、关于GC垃圾回收机制 4.1 GC中的复制算法 4.2 GC中的标记清除算法 1、JVM 的体系结构 "堆"中存在垃圾而"栈"中不存在垃圾的原因&#xff1a; 堆&#xff08;Heap&#xff09; 用途&#xff…...

网络工程和信息安全专业应该考哪些证书?

网络工程和信息安全专业在校大学生可以考的网络信息安全方向证书有NISP一级、NISP二级、CISP-DSG、CISP-PTE&#xff01; 一、NISP一级 NISP一级是网络安全行业入门证书&#xff01; NISP一级报名条件&#xff1a;年满16周岁即可 NISP一级报名时间&#xff1a;随时可报 NI…...

ASP.NET Core 创建使用异步队列

示例图 在 ASP.NET Core 应用程序中&#xff0c;执行耗时任务而不阻塞线程的一种有效方法是使用异步队列。在本文中&#xff0c;我们将探讨如何使用 .NET Core 和 C# 创建队列结构以及如何使用此队列异步执行操作。 步骤 1&#xff1a;创建 EmailMessage 类 首先&#xff0c…...

从Linux系统的角度看待文件-基础IO

目录 从Linux系统的角度看待文件 系统文件I/O open write read 文件操作的本质 vim中批量注释的方法 从Linux系统的角度看待文件 关于文件的共识&#xff1a; 1.空文件也要占用磁盘空间 2.文件内容属性 3.文件操作包括文件内容/文件属性/文件内容属性 4.文件路径文…...

总结之Coze 是一站式 AI Bot 开发平台——工作流使用及coze总结(三)

工作流介绍 工作流支持通过可视化的方式&#xff0c;对插件、大语言模型、代码块等功能进行组合&#xff0c;从而实现复杂、稳定的业务流程编排&#xff0c;例如旅行规划、报告分析等。 当目标任务场景包含较多的步骤&#xff0c;且对输出结果的准确性、格式有严格要求时&…...

汽车线束之故障诊断方案-TDR测试

当前&#xff0c;在汽车布局中的线束的性能要求越来越高。无法通过简单的通断测试就能满足性能传输要求。早起对智能化要求不高&#xff0c;比如没有激动雷达、高清摄像、中央CPU等。 近几年的智能驾驶对网络传输要求越来越高&#xff0c;不但是高速率&#xff0c;还需要高稳定…...

自己做个国庆75周年头像生成器

版权声明&#xff1a;本文为博主原创文章&#xff0c;转载请在显著位置标明本文出处以及作者网名&#xff0c;未经作者允许不得用于商业目的。 下载相关代码&#xff1a;【免费】《自己做个国庆75周年头像生成器》代码资源-CSDN文库 又是一年国庆节&#xff0c;今年使用国旗做…...

2k1000LA loongnix 安装java

问题&#xff1a; 客户 需要在 loongnix 上 使用 java 的程序。 情况说明&#xff1a; 使用 apt get 是无法 安装java 的。 按照的资料就行。 首先是 下载 loongarch64 的 java 的压缩包。这个我已经下载下来了。 社区下载地址&#xff1a; http://www.loongnix.cn/zh/api/…...

中信银行西安分行:构建科技金融体质 做好科技金融“大文章”

中央金融工作会议提出&#xff0c;要做好科技金融、绿色金融、普惠金融、养老金融、数字金融五篇大文章。做好新时代金融五篇大文章&#xff0c;不仅为统筹推进经济和金融高质量发展明确了重点&#xff0c;也锚定了着力点。 作为一家拥有红色基因的国有金融企业&#xff0c;中…...

Linux系统性能调优技巧详解

Linux系统性能调优技巧详解 Linux 系统广泛应用于服务器、嵌入式设备以及开发工作站中&#xff0c;因此对其进行性能调优是保障系统高效运行的关键之一。性能调优不仅可以提高系统的响应速度&#xff0c;还能有效优化资源使用&#xff0c;避免瓶颈。在这篇文章中&#xff0c;我…...

MFC工控项目实例之十九手动测试界面输出信号切换

承接专栏《MFC工控项目实例之十八手动测试界面输入信号实时检测》 根据板卡设置界面组合框选项设定的输出信号&#xff0c;通过读取文件中保存的键值&#xff0c;用单选按钮切换输出信号接通、关闭。 1、在Data_1.h文件中添加代码 CString COMB_Data_O_1[]{"夹紧",&…...

数据结构——栈的基本操作

前言 介绍 &#x1f343;数据结构专区&#xff1a;数据结构 参考 该部分知识参考于《数据结构&#xff08;C语言版 第2版&#xff09;》55 ~ 59页 &#x1f308;每一个清晨&#xff0c;都是世界对你说的最温柔的早安&#xff1a;ૢ(≧▽≦)و✨ 1、栈的基本概念 栈&#x…...

Chainlit集成LlamaIndex实现知识库高级检索(组合对象检索)

检索原理 对象组合索引的原理 是利用IndexNode索引节点&#xff0c;将两个不同类型的检索器作为节点对象&#xff0c;使用 SummaryIndex &#xff08;它可以用来构建一个包含多个索引节点的索引结构。这种索引通常用于从多个不同的数据源或索引方法中汇总信息&#xff0c;并能…...

万界星空科技铜拉丝行业MES系统,实现智能化转型

一、铜拉丝行业生产管理的难点主要体现在以下几个方面&#xff1a; 1、标准严格&#xff1a;铜线产品对质量的要求极高&#xff0c;特别是在电气性能、导电性、耐腐蚀性等方面&#xff0c;任何微小的瑕疵都可能影响产品的使用效果和安全性。 2、过程监控&#xff1a;生产过程…...

ECCV 2024 现场:参会者付高价、跨万里,却无法入场?

ECCV&#xff08;European Conference on Computer Vision&#xff0c;欧洲计算机视觉国际会议&#xff09;是计算机视觉领域的重要国际会议之一&#xff0c;与CVPR和ICCV并称为计算机视觉的三大顶级会议。 ECCV2024是该系列会议的第18届会议&#xff0c;2024年9月29日至10月4…...

使用rsync+jenkins实现服务自动部署全流程

项目背景&#xff1a;城市政务云服务器没有上k8s&#xff0c;所有后端服务都是原始方式部署启动 &#xff08;java -jar xxx.jar&#xff09;&#xff0c;那么有没有方式简化部署难度&#xff0c;实现自动部署&#xff1f;当然是有的&#xff0c;下面详细介绍&#xff08;以Cen…...

python 实现decision tree决策树算法

decision tree决策树算法介绍 决策树算法&#xff08;Decision Tree Algorithm&#xff09;是一种基于输入特征对实例进行分类的树结构模型&#xff0c;主要用于分类和回归任务。其基本原理是根据训练数据的特征属性和类别标签之间的关系&#xff0c;生成一个能够对新样本进行…...

前端大模型入门:实战篇之Vue3+Antdv+transformers+本地模型实现增强搜索

本文将之前的文章&#xff0c;实现一个场景的实战应用&#xff0c;包含代码等内容。利用纯前端实现增强的列表搜索&#xff0c;抛弃字符串匹配&#xff0c;目标是使用番茄关键字可以搜索到西红柿 1 准备工作 1.1 了解llm和web开发 web端的ai开发参考 前端大模型入门&#xff…...

《向量数据库指南》——Fivetran 的 Partner SDK:构建自定义连接器和目标

哈哈,说到 Fivetran 的 Partner SDK,这可真是个好东西啊!作为向量数据库领域的“老司机”,我今天就来给大家详细讲讲这个 SDK 的厉害之处,以及如何用它来构建自定义连接器和目标,实现与 Fivetran 自动化数据移动平台的无缝集成。 一、Fivetran Partner SDK:开启自定义连…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

HarmonyOS运动开发:如何用mpchart绘制运动配速图表

##鸿蒙核心技术##运动开发##Sensor Service Kit&#xff08;传感器服务&#xff09;# 前言 在运动类应用中&#xff0c;运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据&#xff0c;如配速、距离、卡路里消耗等&#xff0c;用户可以更清晰…...

嵌入式学习笔记DAY33(网络编程——TCP)

一、网络架构 C/S &#xff08;client/server 客户端/服务器&#xff09;&#xff1a;由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序&#xff0c;负责提供用户界面和交互逻辑 &#xff0c;接收用户输入&#xff0c;向服务器发送请求&#xff0c;并展示服务…...

C++:多态机制详解

目录 一. 多态的概念 1.静态多态&#xff08;编译时多态&#xff09; 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1&#xff09;.协变 2&#xff09;.析构函数的重写 5.override 和 final关键字 1&#…...

mac 安装homebrew (nvm 及git)

mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用&#xff1a; 方法一&#xff1a;使用 Homebrew 安装 Git&#xff08;推荐&#xff09; 步骤如下&#xff1a;打开终端&#xff08;Terminal.app&#xff09; 1.安装 Homebrew…...

永磁同步电机无速度算法--基于卡尔曼滤波器的滑模观测器

一、原理介绍 传统滑模观测器采用如下结构&#xff1a; 传统SMO中LPF会带来相位延迟和幅值衰减&#xff0c;并且需要额外的相位补偿。 采用扩展卡尔曼滤波器代替常用低通滤波器(LPF)&#xff0c;可以去除高次谐波&#xff0c;并且不用相位补偿就可以获得一个误差较小的转子位…...

WPF八大法则:告别模态窗口卡顿

⚙️ 核心问题&#xff1a;阻塞式模态窗口的缺陷 原始代码中ShowDialog()会阻塞UI线程&#xff0c;导致后续逻辑无法执行&#xff1a; var result modalWindow.ShowDialog(); // 线程阻塞 ProcessResult(result); // 必须等待窗口关闭根本问题&#xff1a…...

高端性能封装正在突破性能壁垒,其芯片集成技术助力人工智能革命。

2024 年&#xff0c;高端封装市场规模为 80 亿美元&#xff0c;预计到 2030 年将超过 280 亿美元&#xff0c;2024-2030 年复合年增长率为 23%。 细分到各个终端市场&#xff0c;最大的高端性能封装市场是“电信和基础设施”&#xff0c;2024 年该市场创造了超过 67% 的收入。…...