从零学算法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终端系统,这样就可以完整地看…...
linux 错误码总结
1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...
CocosCreator 之 JavaScript/TypeScript和Java的相互交互
引擎版本: 3.8.1 语言: JavaScript/TypeScript、C、Java 环境:Window 参考:Java原生反射机制 您好,我是鹤九日! 回顾 在上篇文章中:CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...
LLM基础1_语言模型如何处理文本
基于GitHub项目:https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken:OpenAI开发的专业"分词器" torch:Facebook开发的强力计算引擎,相当于超级计算器 理解词嵌入:给词语画"…...
Android15默认授权浮窗权限
我们经常有那种需求,客户需要定制的apk集成在ROM中,并且默认授予其【显示在其他应用的上层】权限,也就是我们常说的浮窗权限,那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...
OpenLayers 分屏对比(地图联动)
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能,和卷帘图层不一样的是,分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...
Java编程之桥接模式
定义 桥接模式(Bridge Pattern)属于结构型设计模式,它的核心意图是将抽象部分与实现部分分离,使它们可以独立地变化。这种模式通过组合关系来替代继承关系,从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...
如何更改默认 Crontab 编辑器 ?
在 Linux 领域中,crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用,用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益,允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...
淘宝扭蛋机小程序系统开发:打造互动性强的购物平台
淘宝扭蛋机小程序系统的开发,旨在打造一个互动性强的购物平台,让用户在购物的同时,能够享受到更多的乐趣和惊喜。 淘宝扭蛋机小程序系统拥有丰富的互动功能。用户可以通过虚拟摇杆操作扭蛋机,实现旋转、抽拉等动作,增…...
MyBatis中关于缓存的理解
MyBatis缓存 MyBatis系统当中默认定义两级缓存:一级缓存、二级缓存 默认情况下,只有一级缓存开启(sqlSession级别的缓存)二级缓存需要手动开启配置,需要局域namespace级别的缓存 一级缓存(本地缓存&#…...
【Kafka】Kafka从入门到实战:构建高吞吐量分布式消息系统
Kafka从入门到实战:构建高吞吐量分布式消息系统 一、Kafka概述 Apache Kafka是一个分布式流处理平台,最初由LinkedIn开发,后成为Apache顶级项目。它被设计用于高吞吐量、低延迟的消息处理,能够处理来自多个生产者的海量数据,并将这些数据实时传递给消费者。 Kafka核心特…...
