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. 搜索旋转排序数组 多了一个「有重复元素」,导致无法根据 num > nums[0] 来判断 num 在哪一半,比如 [1,1,1,1,1,2,1,1,1] 旋转数组两头相等,元素 1 可能在左半边可能在右半边 …...
使用Pytorch测试cuda设备的性能(单卡或多卡并行)
以下CUDA设备泛指NVIDIA显卡 或 启用ROCm的AMD显卡 测试环境: Distributor ID: UbuntuDescription: Ubuntu 22.04.3 LTSRelease: 22.04Codename: jammy 1.首先,简单使用torch.ones测试CUDA设备 import torch import timedef cuda_benchmark(device_id…...
SpringBoot-AOP-基础到进阶
SpringBoot-AOP AOP基础 学习完spring的事务管理之后,接下来我们进入到AOP的学习。 AOP也是spring框架的第二大核心,我们先来学习AOP的基础。 在AOP基础这个阶段,我们首先介绍一下什么是AOP,再通过一个快速入门程序,…...
Midjourney绘画提示词Prompt参考学习教程
一、工具 SparkAi: SparkAi创作系统是基于OpenAI很火的ChatGPT进行开发的Ai智能问答系统和Midjourney绘画系统,支持OpenAI-GPT全模型国内AI全模型。本期针对源码系统整体测试下来非常完美,可以说SparkAi是目前国内一款的ChatGPT对接OpenAI软…...
美国费米实验室SQMS启动“量子车库”计划!30+顶尖机构积极参与
11月6日,美国能源部费米国家加速器实验室(SQMS)正式启动了名为“量子车库”的全新旗舰量子研究设施。这个6,000平方英尺的实验室是由超导量子材料与系统中心负责设计和建造,旨在联合国内外的科学界、工业领域和初创企业,共同推动量子信息科…...
DCDC同步降压控制器SCT82A30\SCT82630
SCT82A30是一款100V电压模式控制同步降压控制器,具有线路前馈。40ns受控高压侧MOSFET的最小导通时间支持高转换比,实现从48V输入到低压轨的直接降压转换,降低了系统复杂性和解决方案成本。如果需要,在低至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 大模型文件,即可在笔记本上部署、使用类 gpt 大模型。 1. 安装 web UI 1…...
企企通亮相广东智能装备产业发展大会:以数字化采购促进智能装备产业集群高质量发展
制造业是立国之本,是国民经济的主要支柱、是推动工业技术创新的重要来源。 广东作为我国制造业大省,装备制造业规模增长快速,技术水平居于全国前列。为全面贯彻学习党的二十大精神,进一步推动机械装备可靠性设计,促进新…...
pycharm安装教程
PyCharm的安装步骤如下: 找到下载PyCharm的路径,双击.exe文件进行安装。点击Next后,选择安装路径页面(尽量不要选择带中文和空格的目录),选择好路径后,点击Next进行下一步。进入Installation O…...
LeetCode【76】最小覆盖子串
题目: 思路: https://segmentfault.com/a/1190000021815411 代码: public String minWindow(String s, String t) { Map<Character, Integer> map new HashMap<>();//遍历字符串 t,初始化每个字母的次数for (int…...
光谱图像超分辨率综述
光谱图像超分辨率综述 简介 论文链接:A Review of Hyperspectral Image Super-Resolution Based on Deep Learning UpSample网络框架 1.Front-end Upsampling 在Front-end上采样中,是首先扩大LR图像,然后通过卷积网络对放大图像进行…...
Ubuntu apt-get换源
一、参考资料 ubuntu16.04更换镜像源为阿里云镜像源 二、相关介绍 1. apt常用命令 sudo apt-get clean sudo apt-get update2. APT加速工具 轻量小巧的零配置 APT 加速工具:APT Proxy GitHub项目地址:apt-proxy 三、换源关键步骤 1. 更新阿里源 …...
磐舟CI-Web前端项目
整体介绍 磐舟作为一个devops产品,它具备基础的CI流水线功能。同时磐舟的流水线是完全基于云原生架构设计的,在使用时会有一些注意事项。这里首先我们要了解磐舟整体的流水线打包逻辑。 文档结构说明 一般来说,磐舟推荐单个业务的标准git库…...
Flink 运行架构和核心概念
Flink 运行架构和核心概念 几个角色的作用: 客户端:提交作业JobManager进程 任务管理调度 JobMaster线程 一个job对应一个JobMaster 负责处理单个作业ResourceManager 资源的分配和管理,资源就是任务槽分发器 提交应用,为每一个…...
中间件安全:Apache Tomcat 文件上传.(CVE-2017-12615)
中间件安全:Apache Tomcat 文件上传. 当存在漏洞的 Tomcat 运行在 Windows / Linux 主机上,且启用了 HTTP PUT 请求方法(例如,将 readonly 初始化参数由默认值设置为ialse) , 攻击者将有可能可通过精心构造的攻击请求数据包向服务…...
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:HTTP基本概念 超文本 传输 协议 2:常见状态码 1xx 提示信息 2xx 成功 3xx 重定向 4xx 客户端错误 5xx 服务器错误 3:HTTP常见的字段 host 指定服务器的域名 Content-Length 回应的数据长度 Connection 长连接(Keep-Alive&#x…...
一整个分析模型库,大数据分析工具都这么玩了吗?
一整个分析模型库,100张BI报表,覆盖销售、财务、采购、库存等多个分析主题。只需对接ERP,就能自动生成BI报表,完成对海量数据的系统化分析。现在大数据分析工具都发展到这种程度了吗? 放眼看去,现阶段能做…...
最新企业服务总线ESB的国内主要厂商和开源厂商排名,方案书价格多少
企业服务总线ESB是什么? ESB平台(企业服务总线,Enterprise Service Bus)是一种企业级集成平台,它提供了一种开放的、基于标准的消息机制,通过简单的标准适配器和接口,来完成粗粒度应用ÿ…...
react重要知识点(面经)
react重要知识点(面经) react生命周期classhooks reduxredux 核心概念redux 计数器案例 react页面加载卡顿使用懒加载异步加载JavaScript压缩和缓存静态资源使用React.memo() PubSub使用方式1.1 react导入库1.2 react 页面引入pubsubjs1.3 pubsubjs使用2…...
AI Agent与Agentic AI:原理、应用、挑战与未来展望
文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例:使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例:使用OpenAI GPT-3进…...
相机从app启动流程
一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...
拉力测试cuda pytorch 把 4070显卡拉满
import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试,通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小,增大可提高计算复杂度duration: 测试持续时间(秒&…...
Java 二维码
Java 二维码 **技术:**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...
排序算法总结(C++)
目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指:同样大小的样本 **(同样大小的数据)**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...
python爬虫——气象数据爬取
一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用: 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests:发送 …...
论文阅读笔记——Muffin: Testing Deep Learning Libraries via Neural Architecture Fuzzing
Muffin 论文 现有方法 CRADLE 和 LEMON,依赖模型推理阶段输出进行差分测试,但在训练阶段是不可行的,因为训练阶段直到最后才有固定输出,中间过程是不断变化的。API 库覆盖低,因为各个 API 都是在各种具体场景下使用。…...
怎么开发一个网络协议模块(C语言框架)之(六) ——通用对象池总结(核心)
+---------------------------+ | operEntryTbl[] | ← 操作对象池 (对象数组) +---------------------------+ | 0 | 1 | 2 | ... | N-1 | +---------------------------+↓ 初始化时全部加入 +------------------------+ +-------------------------+ | …...
【大模型】RankRAG:基于大模型的上下文排序与检索增强生成的统一框架
文章目录 A 论文出处B 背景B.1 背景介绍B.2 问题提出B.3 创新点 C 模型结构C.1 指令微调阶段C.2 排名与生成的总和指令微调阶段C.3 RankRAG推理:检索-重排-生成 D 实验设计E 个人总结 A 论文出处 论文题目:RankRAG:Unifying Context Ranking…...
32位寻址与64位寻址
32位寻址与64位寻址 32位寻址是什么? 32位寻址是指计算机的CPU、内存或总线系统使用32位二进制数来标识和访问内存中的存储单元(地址),其核心含义与能力如下: 1. 核心定义 地址位宽:CPU或内存控制器用32位…...
