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

leetcode每日一题31

搜索旋转排序数组

那……二分法呗
数组中的数可以相同

比 33. 搜索旋转排序数组 多了一个「有重复元素」,导致无法根据 num >= nums[0] 来判断 num 在哪一半,比如
[1,1,1,1,1,2,1,1,1] 旋转数组两头相等,元素 1 可能在左半边可能在右半边
解决方法也很简单,只要把「旋转数组两头相等」这种特殊情况排除掉就行了

排除掉旋转数组两头相等的情况后,再像33一样判断从哪分
因为只旋转了一次,所以数组分为两段,两端分别是排序数组,那么mid一定会落入其中一种排序好的数列里
如果mid比start大,那么前一半是排序数组,如果mid比end小,那么后一半是排序数组
二分法的难点是代码的细节
以下引用自大佬的题解

第一类 1 0 1 1 1这种。此种情况下 nums[start] == nums[mid],分不清到底是前面有序还是后面有序,此时 start++ 即可。相当于去掉一个重复的干扰项。
第二类 2 3 4 5 6 7 1这种,也就是 nums[start] < nums[mid]。此例子中就是 2 < 5; 这种情况下,前半部分有序。因此如果 nums[start] <=target<nums[mid],则在前半部分找,否则去后半部分找。
第三类 6 7 1 2 3 4 5这种,也就是 nums[start] > nums[mid]。此例子中就是 6 > 2; 这种情况下,后半部分有序。因此如果 nums[mid] <target<=nums[end]。则在后半部分找,否则去前半部分找。

class Solution {
public:bool search(vector<int>& nums, int target) {int start=0;int end=nums.size()-1;int mid;while(start<=end){mid=start+(end-start)/2;if(nums[mid]==target)return true;if(nums[start]==nums[mid])start++;else if(nums[start]<nums[mid]){if(nums[start]<=target&&nums[mid]>target)end=mid-1;else{start=mid+1;}}else{if(nums[end]>=target&&nums[mid]<target)start=mid+1;else end=mid-1;}}return false;}
};

相关文章:

leetcode每日一题31

搜索旋转排序数组 那……二分法呗 数组中的数可以相同 比 33. 搜索旋转排序数组 多了一个「有重复元素」&#xff0c;导致无法根据 num > nums[0] 来判断 num 在哪一半&#xff0c;比如 [1,1,1,1,1,2,1,1,1] 旋转数组两头相等&#xff0c;元素 1 可能在左半边可能在右半边 …...

使用Pytorch测试cuda设备的性能(单卡或多卡并行)

以下CUDA设备泛指NVIDIA显卡 或 启用ROCm的AMD显卡 测试环境&#xff1a; Distributor ID: UbuntuDescription: Ubuntu 22.04.3 LTSRelease: 22.04Codename: jammy 1.首先&#xff0c;简单使用torch.ones测试CUDA设备 import torch import timedef cuda_benchmark(device_id…...

SpringBoot-AOP-基础到进阶

SpringBoot-AOP AOP基础 学习完spring的事务管理之后&#xff0c;接下来我们进入到AOP的学习。 AOP也是spring框架的第二大核心&#xff0c;我们先来学习AOP的基础。 在AOP基础这个阶段&#xff0c;我们首先介绍一下什么是AOP&#xff0c;再通过一个快速入门程序&#xff0c…...

Midjourney绘画提示词Prompt参考学习教程

一、工具 SparkAi&#xff1a; SparkAi创作系统是基于OpenAI很火的ChatGPT进行开发的Ai智能问答系统和Midjourney绘画系统&#xff0c;支持OpenAI-GPT全模型国内AI全模型。本期针对源码系统整体测试下来非常完美&#xff0c;可以说SparkAi是目前国内一款的ChatGPT对接OpenAI软…...

美国费米实验室SQMS启动“量子车库”计划!30+顶尖机构积极参与

​11月6日&#xff0c;美国能源部费米国家加速器实验室(SQMS)正式启动了名为“量子车库”的全新旗舰量子研究设施。这个6,000平方英尺的实验室是由超导量子材料与系统中心负责设计和建造&#xff0c;旨在联合国内外的科学界、工业领域和初创企业&#xff0c;共同推动量子信息科…...

DCDC同步降压控制器SCT82A30\SCT82630

SCT82A30是一款100V电压模式控制同步降压控制器&#xff0c;具有线路前馈。40ns受控高压侧MOSFET的最小导通时间支持高转换比&#xff0c;实现从48V输入到低压轨的直接降压转换&#xff0c;降低了系统复杂性和解决方案成本。如果需要&#xff0c;在低至6V的输入电压下降期间&am…...

本地/笔记本/纯 cpu 部署、使用类 gpt 大模型

文章目录 1. 安装 web UI1.1. 下载代码库1.2. 创建 conda 环境1.3. 安装 pytorch1.4. 安装 pip 库 2. 下载大模型3. 使用 web UI3.1. 运行 UI 界面3.2. 加载模型3.3. 进行对话 使用 web UI 大模型文件&#xff0c;即可在笔记本上部署、使用类 gpt 大模型。 1. 安装 web UI 1…...

企企通亮相广东智能装备产业发展大会:以数字化采购促进智能装备产业集群高质量发展

制造业是立国之本&#xff0c;是国民经济的主要支柱、是推动工业技术创新的重要来源。 广东作为我国制造业大省&#xff0c;装备制造业规模增长快速&#xff0c;技术水平居于全国前列。为全面贯彻学习党的二十大精神&#xff0c;进一步推动机械装备可靠性设计&#xff0c;促进新…...

pycharm安装教程

PyCharm的安装步骤如下&#xff1a; 找到下载PyCharm的路径&#xff0c;双击.exe文件进行安装。点击Next后&#xff0c;选择安装路径页面&#xff08;尽量不要选择带中文和空格的目录&#xff09;&#xff0c;选择好路径后&#xff0c;点击Next进行下一步。进入Installation O…...

LeetCode【76】最小覆盖子串

题目&#xff1a; 思路&#xff1a; https://segmentfault.com/a/1190000021815411 代码&#xff1a; public String minWindow(String s, String t) { Map<Character, Integer> map new HashMap<>();//遍历字符串 t&#xff0c;初始化每个字母的次数for (int…...

光谱图像超分辨率综述

光谱图像超分辨率综述 简介 ​ 论文链接&#xff1a;A Review of Hyperspectral Image Super-Resolution Based on Deep Learning UpSample网络框架 1.Front-end Upsampling ​ 在Front-end上采样中&#xff0c;是首先扩大LR图像&#xff0c;然后通过卷积网络对放大图像进行…...

Ubuntu apt-get换源

一、参考资料 ubuntu16.04更换镜像源为阿里云镜像源 二、相关介绍 1. apt常用命令 sudo apt-get clean sudo apt-get update2. APT加速工具 轻量小巧的零配置 APT 加速工具&#xff1a;APT Proxy GitHub项目地址&#xff1a;apt-proxy 三、换源关键步骤 1. 更新阿里源 …...

磐舟CI-Web前端项目

整体介绍 磐舟作为一个devops产品&#xff0c;它具备基础的CI流水线功能。同时磐舟的流水线是完全基于云原生架构设计的&#xff0c;在使用时会有一些注意事项。这里首先我们要了解磐舟整体的流水线打包逻辑。 文档结构说明 一般来说&#xff0c;磐舟推荐单个业务的标准git库…...

Flink 运行架构和核心概念

Flink 运行架构和核心概念 几个角色的作用&#xff1a; 客户端&#xff1a;提交作业JobManager进程 任务管理调度 JobMaster线程 一个job对应一个JobMaster 负责处理单个作业ResourceManager 资源的分配和管理&#xff0c;资源就是任务槽分发器 提交应用&#xff0c;为每一个…...

中间件安全:Apache Tomcat 文件上传.(CVE-2017-12615)

中间件安全&#xff1a;Apache Tomcat 文件上传. 当存在漏洞的 Tomcat 运行在 Windows / Linux 主机上&#xff0c;且启用了 HTTP PUT 请求方法(例如&#xff0c;将 readonly 初始化参数由默认值设置为ialse) &#xff0c; 攻击者将有可能可通过精心构造的攻击请求数据包向服务…...

Linux 命令补充

目录 tr 命令 命令举例 cut 命令 命令举例 uniq 命令 命令举例 sort 命令 命令举例 面试题 1. 给你一个文件如何提取前 10 的 IP 2. 如何提前 ss 中的状态 tr 命令 作用tr转换tr -d删除tr -c取反tr -s压缩 命令举例 cut 命令 作用cut提取cut -f指定列cut -d指定分…...

HTTP常见面试题(小林coding版总结)

1&#xff1a;HTTP基本概念 超文本 传输 协议 2&#xff1a;常见状态码 1xx 提示信息 2xx 成功 3xx 重定向 4xx 客户端错误 5xx 服务器错误 3&#xff1a;HTTP常见的字段 host 指定服务器的域名 Content-Length 回应的数据长度 Connection 长连接&#xff08;Keep-Alive&#x…...

一整个分析模型库,大数据分析工具都这么玩了吗?

一整个分析模型库&#xff0c;100张BI报表&#xff0c;覆盖销售、财务、采购、库存等多个分析主题。只需对接ERP&#xff0c;就能自动生成BI报表&#xff0c;完成对海量数据的系统化分析。现在大数据分析工具都发展到这种程度了吗&#xff1f; 放眼看去&#xff0c;现阶段能做…...

最新企业服务总线ESB的国内主要厂商和开源厂商排名,方案书价格多少

企业服务总线ESB是什么&#xff1f; ESB平台&#xff08;企业服务总线&#xff0c;Enterprise Service Bus&#xff09;是一种企业级集成平台&#xff0c;它提供了一种开放的、基于标准的消息机制&#xff0c;通过简单的标准适配器和接口&#xff0c;来完成粗粒度应用&#xff…...

react重要知识点(面经)

react重要知识点&#xff08;面经&#xff09; react生命周期classhooks reduxredux 核心概念redux 计数器案例 react页面加载卡顿使用懒加载异步加载JavaScript压缩和缓存静态资源使用React.memo() PubSub使用方式1.1 react导入库1.2 react 页面引入pubsubjs1.3 pubsubjs使用2…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

K8S认证|CKS题库+答案| 11. AppArmor

目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作&#xff1a; 1&#xff09;、切换集群 2&#xff09;、切换节点 3&#xff09;、切换到 apparmor 的目录 4&#xff09;、执行 apparmor 策略模块 5&#xff09;、修改 pod 文件 6&#xff09;、…...

【WiFi帧结构】

文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成&#xff1a;MAC头部frame bodyFCS&#xff0c;其中MAC是固定格式的&#xff0c;frame body是可变长度。 MAC头部有frame control&#xff0c;duration&#xff0c;address1&#xff0c;address2&#xff0c;addre…...

AI Agent与Agentic AI:原理、应用、挑战与未来展望

文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例&#xff1a;使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例&#xff1a;使用OpenAI GPT-3进…...

深入理解JavaScript设计模式之单例模式

目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式&#xff08;Singleton Pattern&#…...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练

前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1)&#xff1a;从基础到实战的深度解析-CSDN博客&#xff0c;但实际面试中&#xff0c;企业更关注候选人对复杂场景的应对能力&#xff08;如多设备并发扫描、低功耗与高发现率的平衡&#xff09;和前沿技术的…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分

一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计&#xff0c;提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合&#xff1a;各模块职责清晰&#xff0c;便于独立开发…...