从零学算法34
34.给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target,返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1:
输入:nums = [5,7,7,8,8,10], target = 8
输出:[3,4]
示例 2:
输入:nums = [5,7,7,8,8,10], target = 6
输出:[-1,-1]
示例 3:
输入:nums = [], target = 0
输出:[-1,-1]
- 非递减数组求区间,很容易想到的是两次二分查找找到左右边界。由于左右边界的找法几乎相同,所以把题目转换一下,只要找到 target 的右边界,我们就知道了结束位置为右边界 - 1;而开始位置,我们只要知道 target - 1 的右边界即可,因为是整数数组,所以只要 target 在数组中存在,那么刚刚大于 target - 1(也就是右边界) 的肯定是 target。这样的话我们只需要把二分查找右边界写成方法,最终返回大致为
[solve(target-1),solve(target)-1]即可。剩下的就是分析区间不存在的情况。首先数组没数肯定就直接返回了,其次如果我能找到区间。那么可以肯定的是,nums[开始位置] 一定是等于 target 的,不是的话肯定也返回了。还有就是如果所有数都比 target 小,那么起始位置会找到数组外面去,所以二分查找返回的数组下标也应当合法。 -
public int[] searchRange(int[] nums, int target) {if(nums.length == 0){return new int[]{-1,-1};}int first = solve(nums,target-1);// 需要先判断 first 是否合法,否则 nums[first] 可能直接数组越界了if(first >= nums.length || nums[first] != target){return new int[]{-1,-1};}return new int[]{first,solve(nums,target)-1};}public int solve(int[] nums,int target){int left=0,right=nums.length-1;while(left<=right && left >=0 && right <= nums.length-1){int mid = (left+right)/2;// 这里用小于等于,那么左边界就会不断右移,直到找到大于 target 的第一个数// 所以这里的 left 最后就是 target 的右边界,如果用小于就是左边界了if(nums[mid]<=target)left=mid+1;else right=mid-1;}return left;}
相关文章:
从零学算法34
34.给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target,返回 [-1, -1]。 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。 示例 1࿱…...
qiankun-微前端--vue2
项目结构 主应用技术: vue2 子应用技术:vue2 项目目录 这里是特意将主子项目分开来的,方便管理 主应用 安装 qiankun npm install qiankun重新定义一个启动端口,防止和其它子应用共用同一个端口(vue.config.js&…...
Win7累积补丁更新包_UpdatePack7R2-23.8.10
UpdatePack7是最新的Win7补丁累积更新包,Windows 7更新补丁安装包,Win7累积更新离线安装包包括所有关键更新和安全更新及Internet Explorer所有版本的更新,此外还集成了NVMe驱动和USB3.0驱动,使用它还可以将累积更新封装到系统内&…...
【二叉树】1-5,理论基础、前中后序遍历的递归法和迭代法、层序遍历
理论基础、前中后序遍历的递归法和迭代法、层序遍历 1,二叉树的种类满二叉树完全二叉树二叉搜索树平衡二叉搜索树 2,存储方式链式存储线式存储 3,二叉树的遍历深度优先搜索前序遍历(递归法、迭代法)中序遍历࿰…...
Mybatis-plus动态条件查询QueryWrapper的使用
Mybatis-plus动态条件查询QueryWrapper的使用 一:queryWrapper介绍 queryWrapper是mybatis plus中实现查询的对象封装操作类,可以封装sql对象,包括where条件,order by排序,select哪些字段等等,他的层级关…...
Redis安装配置远程连接
1. yum 安装 redis: 直接使用命令,将 redis 安装到 linux 服务器中: yum -y install redis 2. 启动 redis: 在 xshell 里,可以使用下面命令,以后台方式启动 redis: [rootVM-8-17-centos /]…...
pycharm中配置conda
安装好pycharm和conda后,打开pycharm:...
matlab解常微分方程常用数值解法1:前向欧拉法和改进的欧拉法
总结和记录一下matlab求解常微分方程常用的数值解法,本文先从欧拉法和改进的欧拉法讲起。 d x d t f ( x , t ) , x ( t 0 ) x 0 \frac{d x}{d t}f(x, t), \quad x\left(t_{0}\right)x_{0} dtdxf(x,t),x(t0)x0 1. 前向欧拉法 前向欧拉法使用了泰勒展开的第…...
SQL | 计算字段
7-创建计算字段 7.1-计算字段 存储在数据库中的数据一般不是我们所需要的字段格式, 需要公司名称,同时也需要公司地址,但是这两个数据存储在不同的列中。 省,市,县和邮政编码存储在不同的列中,但是当我们…...
leetcode做题笔记67
给你两个二进制字符串 a 和 b ,以二进制字符串的形式返回它们的和。 思路一:模拟题意 void reserve(char* s) {int len strlen(s);for (int i 0; i < len / 2; i) {char t s[i];s[i] s[len - i - 1], s[len - i - 1] t;} }char* addBinary(cha…...
fastadmin 自定义搜索分类和时间范围
1.分类搜索,分类信息获取----php 2.对应html页面,页面底部加搜索提交代码(这里需要注意:红框内容) 图上代码----方便直接复制使用 <script id"countrySearch" type"text/html"><!--form…...
Oracle Data Redaction与Data Pump
如果表定义了Redaction Policy,导出时数据会脱敏吗?本文解答这个问题。 按照Oracle文档Advanced Security Guide第13章,13.6.5的Tutorial,假设表HR.jobs定义了Redaction Policy。 假设HR用户被授予了访问目录对象的权限…...
设计模式(6)原型模式
一、介绍 Java中自带的原型模式是clone()方法。该方法是Object的方法,native类型。他的作用就是将对象的在内存的那一块内存数据一字不差地再复制一个。我们写简单类的时候只需要实现Cloneable接口,然后调用Object::clone方法就可实现克隆功能。这样实现…...
pywinauto结合selenium实现文件上传
简介 PC端-Windows上的元素识别可用viewWizard工具 PC端-Windows上的元素操作可用pywinauto库 浏览器上网页的元素识别可用selenium 安装 pip installer pywinauto 使用须知 pywinauto官方文档 确定app的可访问技术 1、win32 API(backend=“win32”) 一般是MFC、VB6、VC…...
【Java多线程学习7】Java线程池技术
线程池技术 一、什么是线程池 线程池顾名思义是管理一组线程的池子。当有任务要处理时,直接从线程池中获取线程来处理,处理完之后线程不会立即销毁,而是等待下一个任务。 二、为什么要使用线程池? 线程池的作用? 1、降低资源…...
VMware虚拟机NAT模式Ubuntu无法上网解决方案
发现只要NAT模式,ping地址时就报网络不可达,且右上方网络图标消失,但是外部USB网络设备又只能在NAT模式下使用。。。 博主的解决方案如下: 按WinR键入services.msc, 找到VMware DHCP Service、VMware NAT Service和V…...
Linux中无法忘记mysql密码处理办法
找到/etc/my.cnf或者/etc/mysql/my.cnf文件 添加下面两行代码,取消密码验证 [mysqld] skip-grant-table使用命令登录:mysql -u root -p,回车,回车使用sql语句来修改密码 mysql>use mysql; mysql>update user set password…...
vue 使用 el-upload 上传文件(自动上传/手动上传)
vue 使用 el-upload 上传文件(自动上传/手动上传) 文章目录 1. 自动上传(选择完文件后,调用axios上传)2.手动上传 1. 自动上传(选择完文件后,调用axios上传) <el-uploadref"upload1"action:multiple"false"accept".xlsx,.csv,.xls":auto-upl…...
服务器遭受攻击之后的常见思路
哈喽大家好,我是咸鱼 不知道大家有没有看过这么一部电影: 这部电影讲述了男主是一个电脑极客,在计算机方面有着不可思议的天赋,男主所在的黑客组织凭借着超高的黑客技术去入侵各种国家机构的系统,并引起了德国秘密警察…...
C语言学习笔记 使用vscode外部console出现闪退-12
前言 在使用vscode的外部console时,会出现闪退现象,这是因为程序运行结束后,系统自动退出了终端(终端机制决定的)。我们可以在C程序结束后,使用system函数来暂停DOS终端系统,这样就可以完整地看…...
浅谈 React Hooks
React Hooks 是 React 16.8 引入的一组 API,用于在函数组件中使用 state 和其他 React 特性(例如生命周期方法、context 等)。Hooks 通过简洁的函数接口,解决了状态与 UI 的高度解耦,通过函数式编程范式实现更灵活 Rea…...
微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】
微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来,Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...
盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来
一、破局:PCB行业的时代之问 在数字经济蓬勃发展的浪潮中,PCB(印制电路板)作为 “电子产品之母”,其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透,PCB行业面临着前所未有的挑战与机遇。产品迭代…...
DockerHub与私有镜像仓库在容器化中的应用与管理
哈喽,大家好,我是左手python! Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库,用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...
智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql
智慧工地管理云平台系统,智慧工地全套源码,java版智慧工地源码,支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求,提供“平台网络终端”的整体解决方案,提供劳务管理、视频管理、智能监测、绿色施工、安全管…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序
一、开发环境准备 工具安装: 下载安装DevEco Studio 4.0(支持HarmonyOS 5)配置HarmonyOS SDK 5.0确保Node.js版本≥14 项目初始化: ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...
深度学习水论文:mamba+图像增强
🧀当前视觉领域对高效长序列建模需求激增,对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模,以及动态计算优势,在图像质量提升和细节恢复方面有难以替代的作用。 🧀因此短时间内,就有不…...
C++ 设计模式 《小明的奶茶加料风波》
👨🎓 模式名称:装饰器模式(Decorator Pattern) 👦 小明最近上线了校园奶茶配送功能,业务火爆,大家都在加料: 有的同学要加波霸 🟤,有的要加椰果…...
【Linux手册】探秘系统世界:从用户交互到硬件底层的全链路工作之旅
目录 前言 操作系统与驱动程序 是什么,为什么 怎么做 system call 用户操作接口 总结 前言 日常生活中,我们在使用电子设备时,我们所输入执行的每一条指令最终大多都会作用到硬件上,比如下载一款软件最终会下载到硬盘上&am…...
HybridVLA——让单一LLM同时具备扩散和自回归动作预测能力:训练时既扩散也回归,但推理时则扩散
前言 如上一篇文章《dexcap升级版之DexWild》中的前言部分所说,在叠衣服的过程中,我会带着团队对比各种模型、方法、策略,毕竟针对各个场景始终寻找更优的解决方案,是我个人和我司「七月在线」的职责之一 且个人认为,…...
