【算法day1】数组:双指针算法
题目引用
这里以
1、LeetCode704.二分查找
2、LeetCode27.移除元素
3、LeetCode977.有序数组的平方
这三道题举例来说明数组中双指针的妙用。
1、二分查找
给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。
首先我们来理解一下题意
我们需要在一段连续递增的数组当中找到 ==target 元素,并在函数结尾返回它。
暴力的解法是直接把数组遍历一遍,一一比对,找到后返回。当然时间复杂度会是 O(N) 级别的。
那么有没有更简便的写法呢?
当然有,那就是我们今天要见识到的 双指针算法。
首先我们初始化两个指针,一个指向数组的头left,另一个指向数组的尾right。并且维护一个 mid 指针,使其始终处于 [left,right] 范围内,比较数组 mid 位置与target 的数值大小。如果 mid 位置的数值比target大,那么将right移动到mid位置,再次更新mid位置。如果 mid 位置的数值比target小,那么将left移动到mid位置,再次更新mid位置。如此循环直到找到 ==target 值的位置或者 left>right 循环结束。
注意:由于区间的个人喜好不同,一般有左闭右开写法和左闭右闭两种写法。
左闭右开写法:
int search(vector<int>& nums, int target) {int left=0,right=nums.size();while(left<right){int mid=(left+right)>>1;if(target>nums[mid]){left=mid+1;}else if(target<nums[mid]){right=mid;}else{return mid;}}return -1;}
左闭右闭写法:
int search(vector<int>& nums, int target) {int left=0,right=nums.size()-1;while(left<=right){int mid=(left+right)>>1;if(target>nums[mid]){left=mid+1;}else if(target<nums[mid]){right=mid-1;}else{return mid;}}return -1;}
那么这题就被完美地解决了~
2、移除元素
给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
假设 nums 中不等于 val 的元素数量为 k,要通过此题,您需要执行以下操作:
更改 nums 数组,使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
返回 k。
我们来理解一下题意:
给了我们一个存储着随机元素且随机长度的数组,让我们来移除 ==val 的元素,这道题当然可以遍历一遍数组,将数组中 ==val 的元素全部覆盖掉,但是这样是很容易丢失数据位置进而引发结果错误的。那么应该怎么写才能快速而优雅地AC它呢?当然还是双指针。
我们定义两个指针,一个快指针fast,一个慢指针slow。我们让fast指针先走,边走边判断数组中的元素是否 ==val 。如果等于,我们继续往下走(是不是很奇怪?别急,慢慢看),如果 !=val ,我们让fast位置的值和slow位置的值交换,并且 slow++。当fast走到数组末尾的时候,返回slow。
为什么?
为什么slow位置就能代表 !=val 的所有元素的数目呢?
我来画个图给大家看看
所以返回slow就会是被移除后的元素数量。
附上代码
int removeElement(vector<int>& nums, int val) {int slow=0;for(int fast=0;fast<nums.size();fast++){if(nums[fast]!=val) nums[slow++]=nums[fast];}return slow;}
这题也就完美的完成啦~
3、有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。
这题我们也分析一下下~
首先用暴力算完再排序也是可以的~但我们是手艺人,不能题题都暴力。
这题也是给我们一个非递减数组,也就是要么增要么等。那么还是使用双指针来解吧。定义一个头指针i,尾指针j,遍历数组,比较 nums[i] , nums[j] 平方后的大小, i 位置的平方比较大就交换,反之则将 平方后的数 放回数组对应位置继续循环。
直接上代码
vector<int> sortedSquares(vector<int>& nums) {int n = nums.size();vector<int> ans(n);int i = 0, j = n - 1;for (int p = n - 1; p >= 0; p--) {int x = nums[i], y = nums[j];if (-x > y) {ans[p] = x * x;i++;} else {ans[p] = y * y;j--;}}return ans;}
总结
双指针算法既简便又能快速解决问题,如果我们遇到数组相关的问题可以积极考虑它。
相关文章:
【算法day1】数组:双指针算法
题目引用 这里以 1、LeetCode704.二分查找 2、LeetCode27.移除元素 3、LeetCode977.有序数组的平方 这三道题举例来说明数组中双指针的妙用。 1、二分查找 给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜…...
Ubuntu 22.04 离线安装软件包
在使用最小化安装时,默认是不带有vim 或者nano编辑器的,如果你的环境不能上外网就需要离线安装。 首先你需要先找一台可以上网的ubuntu系统(虚拟机搭建也行),下载所有的依赖包,然后上传到需要安装的服务器…...
网络安全——浅谈HTTP协议
HTTP请求 HTTP请求是客户端往服务端发送请求动作,告知服务器自己的要求。 HTTP请求由状态行、请求头、请求正文三部分组成: 状态行:包括请求方式Method、资源路径URL、协议版本Version;请求头:包括一些访问的域名、…...
鸿蒙开发-在ArkTS中制作音乐播放器
音频播放功能实现 导入音频播放相关模块 首先需要从ohos.multimedia.audio模块中导入必要的类和接口用于音频播放。例如: import audio from ohos.multimedia.audio;创建音频播放器实例并设置播放源 可以通过audio.createAudioPlayer()方法创建一个音频播放器实…...
Rust学习笔记_03——元组
Rust学习笔记_01——基础 Rust学习笔记_02——数组 Rust学习笔记_03——元组 文章目录 Rust学习笔记_03——元组元组1. 定义元祖2. 访问元组中的元素3. 元组的解构4. 元组不可遍历和切片5. 元组作为函数返回值6. 单元元组7. 代码演示 元组 在Rust编程语言中,元组&a…...
LabVIEW内燃机气道试验台测控系统
基于LabVIEW软件开发的内燃机气道试验台测控系统主要应用于内燃机气道的性能测试和数据分析,通过高精度的测控技术,有效提升内燃机的测试精度和数据处理能力。 项目背景 随着内燃机技术的发展,对其气道性能的精准测量需求日益增加。该系统通…...
git 本地同步远端分支
一、关联远程仓库 本地仓库关联远端仓库 git remote add origin https://github.com/user/repository.git 二、获取远程分支信息 获取远程仓库的最新分支信息 git fetch origin 三、创建或切换到本地分支以跟踪远程分支 1. 创建分支 创建分支并关联到远端分支 git bra…...
用Pycharm安装manim
由于版本和工具的差异,manim的安装方式不尽相同。本文用Pycharm来安装manim. 一、准备工作:安装相应版本的python、pycharm和ffmpeg. 此处提供一种安装ffmpeg的方式 下载地址:FFmpeg 下载后,解压到指定目录。 配置环境变量&am…...
#渗透测试#红蓝攻防#HW#漏洞挖掘#漏洞复现01-笑脸漏洞(vsftpd)
免责声明 本教程仅为合法的教学目的而准备,严禁用于任何形式的违法犯罪活动及其他商业行为,在使用本教程前,您应确保该行为符合当地的法律法规,继续阅读即表示您需自行承担所有操作的后果,如有异议,请立即停…...
vue3项目中使用星火API
在node环境epxress中使用讯飞ai接口进行二次封装,通过ai对话回复提取,获得ai提取的文章摘要 本文章只是简单使用,更复杂功能比如调用星火API制作对话机器人可以查看文档,对于初次使用星火AI接口或许有帮助 讯飞星火大模型API-大模…...
digit_eye开发记录(3): C语言读取MNIST数据集
在前两篇,我们解读了 MNIST 数据集的 IDX 文件格式,并分别用 C 和 Python 做了 读取 MNIST 数据集的实现。 基于 C 的代码稍长,基于 Python 的代码则明显更短,然而它们的共同特点是:依赖了外部库: 基于 C …...
【linux】(23)对象存储服务-MinIo
MinIO 是一个高性能的对象存储服务,兼容 Amazon S3 API。 Docker安装MinIo 前提条件 确保您的系统已经安装了 Docker。如果还没有安装 Docker,可以参考 Docker 官方文档进行安装。 1. 拉取 MinIO Docker 镜像 首先,从 Docker Hub 拉取 Mi…...
如何使用Python解析从淘宝API接口获取到的JSON数据?
基本的 JSON 解析 当从淘宝 API 接口获取到数据后(假设数据存储在变量response_data中),首先要判断数据类型是否为 JSON。如果是,就可以使用 Python 内置的json模块进行解析。示例代码如下: import json # 假设respon…...
C# 2024年Visual Studio实用插件集合
在2024年,Visual Studio作为.NET开发者的首选IDE,其插件生态不断壮大,为开发者提供了更高效、便捷的开发体验。本文将介绍一些实用的Visual Studio插件,特别是针对C#开发者,帮助提升开发效率和代码质量。 1. GitHub C…...
Matlab Simulink HDL Coder开发流程(一)— 创建HDL兼容的Simulink模型
创建HDL兼容的Simulink模型 一、使用Balnk DUT模板二、从HDL Coder库中选择模块三、为DUT开发算法/功能四、为设计创建Testbench五、仿真验证设计功能六、Simulink模型生成HDL代码 这个例子说明了如何创建一个用于生成HDL代码的Simulink模型。要创建兼容HDL代码生成的MATLAB算法…...
详解Qt pdf 之QPdfSelection 选择文本类
文章目录 QPdfSelection 类详解前言 详细说明公共函数说明1. 构造函数2. text3. boundingRect4. isEmpty5. startPage6. endPage 使用场景示例代码代码说明总结 QPdfSelection 类详解 前言 QPdfSelection 是 Qt PDF 模块中的一个类,用于表示在 PDF 文档中被选中的…...
docker中redis查看key、删除key
查看docker启动的进程 docker ps这个命令会列出所有正在运行的容器,包括容器的 ID、镜像名称、创建时间、状态、端口映射和名称 CONTAINER ID IMAGE COMMAND CREATED STATUS PORTS NAMES 1a2b3c4d5e6…...
【MySQL — 数据库基础】MySQL的安装与配置 & 数据库简单介绍
数据库基础 本节目标 掌握关系型数据库,数据库的作用掌握在Windows和Linux系统下安装MySQL数据库了解客户端工具的基本使用和SQL分类了解MySQL架构和存储引擎 1. 数据库的安装与配置 1.1 确认MYSQL版本 处理无法在 cmd 中使用 mysql 命令的情况&a…...
ehr系统建设方案,人力资源功能模块主要分为哪些,hrm平台实际案例源码,springboot人力资源系统,vue,JAVA语言hr系统(源码)
eHR人力资源管理系统:功能强大的人力资源管理工具 随着企业规模的不断扩大和业务需求的多样化,传统的人力资源管理模式已无法满足现代企业的需求。eHR人力资源管理系统作为一种先进的管理工具,能够为企业提供高效、准确、实时的人力资源管理。…...
【解决安全扫描漏洞】---- 检测到目标站点存在 JavaScript 框架库漏洞
1. 漏洞结果 JavaScript 框架或库是一组能轻松生成跨浏览器兼容的 JavaScript 代码的工具和函数。如果网站使用了存在漏洞的 JavaScript 框架或库,攻击者就可以利用此漏洞来劫持用户浏览器,进行挂马、XSS、Cookie劫持等攻击。 1.1 漏洞扫描截图 1.2 具体…...
flink学习(12)——checkPoint
如何设置checkPoint package com.bigdata.day06;/** * 1、需要三句话 * 2、设置完checkPoint后若程序出现异常,会一直重启 * 3、此时是自动进行checkPoint保存 * 4、注意:此时如果有checkpoint ,是不会出现异常的,需要将checkpoint的代码关…...
【iOS】《Effective Objective-C 2.0》阅读笔记(一)
文章目录 前言了解OC语言的起源在类的头文件中尽量少引入其他头文件多用字面量语法,少用与之等价的方法字面量数值字面量数组字面量字典 多用类型常量,少用#define预处理指令用枚举法表示状态、选项、状态码 总结 前言 最近开始阅读一些iOS开发的相关书籍…...
LVS 负载均衡面试题及参考答案
目录 什么是 LVS 负载均衡?它的主要作用是什么? 为什么要使用 LVS 进行负载均衡? LVS 有哪些组成部分? 简述 LVS 的架构。 LVS 中有哪两种典型的架构?请简要说明它们的特点。 LVS 的工作原理是怎样的?简述 LVS 的工作原理。 解释 LVS 中的虚拟服务器(VS)概念。 …...
北京科博会 天云数据CEO雷涛谈人工智能技术服务数字资产建设
7月13日,第二十六届中国北京国际科技产业博览会(简称北京科博会)在国家会议中心开幕。本届科博会年度主题为“实施创新驱动发展战略 增强高质量发展动能”。会上,天云数据CEO雷涛发表《人工智能技术服务数字资产建设》主题演讲。 近期非常引人注目的事件…...
【Python运维】容器管理新手入门:使用Python的docker-py库实现Docker容器管理与监控
《Python OpenCV从菜鸟到高手》带你进入图像处理与计算机视觉的大门! 解锁Python编程的无限可能:《奇妙的Python》带你漫游代码世界 随着容器技术的广泛应用,Docker已经成为开发和运维中的标准工具之一。使用Python语言管理Docker容器,不仅可以自动化繁琐的容器操作,还能…...
小程序解决大问题-物流系统磁盘爆满问题处理
晚上七点,煤矿调运的物流调度系统突然磁盘报名导致服务崩溃。系统用的是微服务,没有详细操作说明,也不敢动,运煤车辆排起了长队,只能联系厂家处理。好在经过30多分钟的处理,服务终于启动,系统运…...
计算机网络基础篇
TCP/IP网络模型 TCP/IP网络模型的作用就是给数据包进行层层封装,帮助数据包能够正确的找到对应的设备接受数据。 一个URL所经历的全部过程 URL所经历的全部过程: HTTP -> DNS ->协议栈-TCP->IP->MAC->网卡->交换机->路由器->服…...
32 从前序与中序遍历序列构造二叉树
32 从前序与中序遍历序列构造二叉树 32.1 从前序与中序遍历序列构造二叉树解决方案 class Solution { public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {return buildTreeHelper(preorder, inorder, 0, 0, inorder.size() - 1)…...
D82【python 接口自动化学习】- pytest基础用法
day82 pytest初体验 学习日期:20241128 学习目标:pytest基础用法 -- pytest初体验 学习笔记: 文件命名规范 py测试文件必须以test_开头(或_test结尾)测试方法必须以test开头测试类必须以Test开头,并且…...
在开发环境中,前端(手机端),后端(电脑端),那么应该如何设置iisExpress
首先,要想手机端应用能成功请求后端,两个设备至少需在同一个局域网内,且IP地址互通; 因为ajax是http(s)://IP地址端口号的方式请求,但是iisExpress默认是localhost如何解决,并没有IP地址,所以手…...
网站后台 灰色/北京本地网络推广平台
欢迎加入学习python的队伍,我们非常欢迎,一起学习,一起进步!!!转载于:https://www.cnblogs.com/xiaohaiying/p/7169017.html...
手机网站定制建设/产品推广文案范文
摘要 图结构数据上进行半监督学习的可拓展方法。该方法基于 直接在图上操作的卷积神经网络 的有效变体。 通过 谱图卷积的局部一阶近似 来激励我们选择 卷积结构。我们的模型在 图边 上的数量(number of graph edges)上线性缩放,并且学习隐藏层表示(其encode 局部图…...
wordpress中文下载/外链生成
CSS 背景(background) 目标 - 理解 - 背景的作用 - css背景图片和插入图片的区别 - 应用 - 通过css背景属性,给页面元素添加背景样式 - 能设置不同的背景图片位置 4.1 背景颜色(color) - 语法: background-color:颜色值; 默认的值是 trans…...
wordpress ecshop/全国十大跨境电商排名
榜单解读: 2021年12月影音娱乐行业上榜的20个视频号共发布作品2518个,平均点赞数70143个, 平均转发数46761个,平均评论数2076个。 依据榜单可知:1)从作品数来看,12月影音娱乐行业上榜的20个视频…...
怎么建网站做淘宝客/百度优化
IBM XIV被业内称为革命性的新一代存储架构,它是采用了大规模并行的分布式网格存储技术,使用了“Scale out”(横向扩展)的存储架构,利用多路网格模块并行分担存储负荷,并通过细粒度数据分布算法保证数据的恒…...
新安网站建设/站长推荐
CompletableFuture Future接口理论知识复习 Future接口(FutureTask实现类)定义了操作异步任务执行一些方法,如获取异步任务的执行结果,取消任务,判断任务是否被取消,判断任务是否完毕等比如主线程让一个子线程取执行任务,子线程可能比较耗时,启动子线程开始执行任务后,主线程…...