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

算法之双指针系列1

目录

一:双指针的介绍

1:快慢指针

2:对撞指针

二:对撞指针例题讲述


一:双指针的介绍

在做题中常用两种指针,分别为对撞指针与快慢指针。

1:快慢指针

简称为龟兔赛跑算法,它的基本思想是使用两个移动速度不同的指针在数组或链表等序列结构上移动。

这种对于处理环形链表和数组以及循环重复问题,是非常好用的。

2:对撞指针

简称为左右指针,它的基本思想是一个指针从最左端开始,一个从最右端开始,逐渐往中间逼近。一般终止条件是两个指针相遇或者错开。

一般用于顺序结构中。

注意:这里的指针并不是C语言中的指针,而是指在数组中设置的两个下标,通过改变两个下标来改变所在数组的位置。

二:对撞指针例题讲述

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

1:盛最多水容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明:你不能倾斜容器。

算法原理:

解法1:暴力枚举,是很简单的,但是我们可以发现他的时间复杂度是超时的。

解法2:双指针法,题中让求v,那么v=h*w.

186254837

就以上面的数组举例。

我们设左指针left为数组最左边的下标,右指针right为数组最右边的下标。

那么我们要取最大的V只有一种情况,就要h变大,w变小。(因为最开始的W最大)。

int n=height.size();
int left=0,right=n-1;设置左右指针。
int ret=0;
while(left<right)
{int sum=min(height[left],height[right])*(right-left) //求vret=max(ret,sum)//求出最大的v.if(height[left]<height[right])left++;elseright--;}
return ret;

 力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

2:有效三角形的个数

给定一个包含非负整数的数组 nums ,返回其中可以组成三角形三条边的三元组个数。

示例 1:

输入: nums = [2,2,3,4]
输出: 3
解释:有效的组合是: 
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3

需要的判断条件就是两个最小边之和大于最大边。

算法原理:

第一种:暴力求解。明显的是超出时间限制的。

第二种:双指针 。利用单调性。

1.先固定最大的数。

2.在最大的数的左区域内,使用双指针算法,快速统计出符合要求的三元组的个数。

sort(nums.begin(),nums.end());//这一步是排序。
int n=nums.size();
int i=n-1;
int ret=0;for(i;i>=2;i--){int left=0;int right=i-1;while(left<right)//基本条件{ if(nums[left]+nums[right]<=nums[i]) left++;else  {ret+=right-left;right--;}}}
return ret;}

 力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

购物车内的商品价格按照升序记录于数组 price。请在购物车中找到两个商品的价格总和刚好是 target。若存在多种情况,返回任一结果即可。

示例 1:

输入:price = [3, 9, 12, 15], target = 18
输出:[3,15] 或者 [15,3]

算法思路

1:暴力枚举。显然还是超过时间限制。

2:双指针。比较简单就不再详解。

 int left = 0, right = nums.size() - 1;while(left < right){int sum = nums[left] + nums[right];if(sum > target) right--;else if(sum < target) left++;else return {nums[left], nums[right]};}// 照顾编译器return {-4941, -1};

 

相关文章:

算法之双指针系列1

目录 一&#xff1a;双指针的介绍 1&#xff1a;快慢指针 2&#xff1a;对撞指针 二&#xff1a;对撞指针例题讲述 一&#xff1a;双指针的介绍 在做题中常用两种指针&#xff0c;分别为对撞指针与快慢指针。 1&#xff1a;快慢指针 简称为龟兔赛跑算法&#xff0c;它的基…...

苍穹外卖面试题

8. 如何理解分组校验 很多情况下&#xff0c;我们会将校验规则写到实体类中的属性上&#xff0c;而这个实体类有可能作为不同功能方法的参数使用&#xff0c;而不同的功能对象参数对象中属性的要求是不一样的。比如我们在新增和修改一个用户对象时&#xff0c;都会接收User对象…...

【Qt 学习之路】在 Qt 使用 ZeroMQ

文章目录 1、概述2、ZeroMQ介绍2.1、ZeroMQ 是什么2.2、ZeroMQ 主线程与I/O线程2.3、ZeroMQ 4种模型2.4、ZeroMQ 相关地址 3、Qt 使用 ZeroMQ3.1、下载 ZeroMQ3.2、添加 ZeroMQ 库3.3、使用 ZeroMQ3.4、相关 ZeroMQ 案例 1、概述 今天是大年初一&#xff0c;先给大家拜个年&am…...

CI/CD到底是啥?持续集成/持续部署概念解释

前言 大家好&#xff0c;我是chowley&#xff0c;日常工作中&#xff0c;我每天都在接触CI/CD&#xff0c;今天就给出我心中的答案。 在现代软件开发中&#xff0c;持续集成&#xff08;Continuous Integration&#xff0c;CI&#xff09;和持续部署&#xff08;Continuous D…...

golang常用库之-disintegration/imaging图片操作(生成缩略图)

文章目录 golang常用库之什么是imaging库导入和使用生成缩略图 golang常用库之 什么是imaging库 官网&#xff1a;https://github.com/disintegration/imaging imaging 是一个 Go 语言的图像处理库&#xff0c;它提供了一组功能丰富的函数和方法&#xff0c;用于进行各种图像…...

CSS 控制 video 标签的控制栏组件的显隐

隐藏下载功能 <video src"" controlsList"nodownload" />controlslist 取值如下(设定多个值则使用空格进行间隔) 如&#xff1a;controlslist"nodownload nofullscreen noremoteplayback"nodownload&#xff1a;取消更多控件弹窗的下载功…...

数据可视化之维恩图 Venn diagram

文章目录 一、前言二、主要内容三、总结 &#x1f349; CSDN 叶庭云&#xff1a;https://yetingyun.blog.csdn.net/ 一、前言 维恩图&#xff08;Venn diagram&#xff09;&#xff0c;也叫文氏图或韦恩图&#xff0c;是一种关系型图表&#xff0c;用于显示元素集合之间的重叠区…...

2024刘谦春晚第二个扑克牌魔术

前言 就是刚才看春晚感觉这个很神奇&#xff0c;虽然第一个咱模仿不过来&#xff0c;第二个全国人民这么多人&#xff0c;包括全场观众都有成功&#xff0c;这肯定是不需要什么技术&#xff0c;那我觉得这个肯定就是数学了&#xff0c;于是我就胡乱分析一通。 正文 首先准备…...

【k8s系列】(202402) 证书apiserver_client_certificate_expiration_seconds

apiserver_client_certificate_expiration_second证书定义的位置&#xff1a;kubernetes/staging/src/k8s.io/apiserver/pkg/authentication/request/x509/x509.go at 244fbf94fd736e94071a77a8b7c91d81163249d4 kubernetes/kubernetes (github.com) apiserver_client_certi…...

Rust变量与常量介绍

Rust是一门注重安全性和性能的系统编程语言&#xff0c;其中变量和常量的概念有着独特的设计和特性。在本文中&#xff0c;我们将深入了解Rust中的变量和常量&#xff0c;并解释它们之间的区别&#xff0c;同时通过多个例子进行说明。 Rust常量 在Rust中&#xff0c;常量是不…...

Flask基础学习2

连接mysql数据库测试(专业版) [注意1&#xff1a;要导入text库&#xff0c;否则可能出现找不到select 1错误] [注意2&#xff1a;若出现下列问题&#xff0c;可按照模板代码的顺序db SQLAlchemy(app) 的位置] RuntimeError: Either SQLALCHEMY_DATABASE_URI or SQLALCHEMY_B…...

文章页的上下篇功能是否有必要?boke112百科取消上下篇功能

也不知道是从什么时候开始&#xff0c;我们很多站长的博客网站文章页都会在文末添加上“上一篇”和“下一篇”功能&#xff0c;目的是进行站内SEO优化和方便用户阅读上下篇文章。 boke112百科不管是以前使用的Three主题还是现在使用的YIA主题&#xff0c;刚开始的文章页都是有…...

Lua序列化

我们经常需要序列化一些数据&#xff0c;为了将数据转换为字节流或者字符流&#xff0c;这样我们就可以保存到文件或者通过网络发送出去。我们可以在 Lua 代码中描述序列化的数据&#xff0c;在这种方式下&#xff0c;我们运行读取程序即可从代码中构造出保存的值。 number/st…...

Acwing---839. 模拟堆

模拟堆 1.题目2.基本思想3.代码实现 1.题目 维护一个集合&#xff0c;初始时集合为空&#xff0c;支持如下几种操作&#xff1a; I x&#xff0c;插入一个数 x&#xff1b;PM&#xff0c;输出当前集合中的最小值&#xff1b;DM&#xff0c;删除当前集合中的最小值&#xff08…...

STM32 STD/HAL库驱动W25Q64模块读写字库数据+OLED0.96显示例程

STM32 STD/HAL库驱动W25Q64 模块读写字库数据OLED0.96显示例程 &#x1f3ac;原创作者对W25Q64保存汉字字库演示&#xff1a; W25Q64保存汉字字库 &#x1f39e;测试字体显示效果&#xff1a; &#x1f4d1;功能实现说明 利用W25Q64保存汉字字库&#xff0c;OLED显示汉字的时…...

Android 移动应用开发 创建第一个Android项目

文章目录 一、创建第一个Android项目1.1 准备好Android Studio1.2 运行程序1.3 程序结构是什么app下的结构res - 子目录&#xff08;所有图片、布局、字AndroidManifest.xml 有四大组件&#xff0c;程序添加权限声明 Project下的结构 二、开发android时&#xff0c;部分库下载异…...

MATLAB语音去噪系统

目录 一、背景 二、GUI页面 三、程序 3.1 LMS滤波程序 3.2 GUI程序 四、附录 一、背景 本文介绍了一种最佳的自适应滤波器结构&#xff0c;该结构采用最小均方差&#xff08;LMS&#xff09;作为判据&#xff0c;通过不断迭代自适应结构来调整得到最佳滤波器…...

小程序-上传图片功能

技术前置&#xff1a; 1.框架采用colorUI 2.原生开发 功能&#xff1a; 上传图片 1.上传已经拍摄的图片 2.实时拍摄上传 3.设置上传图片数量&#xff0c;每次上传数量 4.上传等待 ChooseImage() {if(this.data.imgList.length>4){_this.ErrorEvent("最多上传4…...

alist基本用法@文档阅读@挂载网盘@网盘webdav挂载

文章目录 alist官网alist网站风格说明alist软件版本 安装和启动使用必看文档&#x1f47a;alist for android版本启动alist网页 典型用例挂载阿里云盘open获取阿里云令牌 主页检查挂载情况 常用页面以配置挂载列表管理配置页面 配置文件和目录&#x1f47a;FAQ可能遇到的错误检…...

Hive正则表达式

Hive版本&#xff1a;hive-3.1.2 一、Hive的正则表达式概述 正则表达式是一种用于匹配和操作文本的强大工具&#xff0c;它是由一系列字符和特殊字符组成的模式&#xff0c;用于描述要匹配的文本模式。 Hive的正则表达式灵活使用解决HQL开发过程中的很多问题&#xff0c;本篇文…...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具

作者&#xff1a;来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗&#xff1f;了解下一期 Elasticsearch Engineer 培训的时间吧&#xff01; Elasticsearch 拥有众多新功能&#xff0c;助你为自己…...

Day131 | 灵神 | 回溯算法 | 子集型 子集

Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者写过很多次这道题了&#xff0c;不想写题解了&#xff0c;大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

ETLCloud可能遇到的问题有哪些?常见坑位解析

数据集成平台ETLCloud&#xff0c;主要用于支持数据的抽取&#xff08;Extract&#xff09;、转换&#xff08;Transform&#xff09;和加载&#xff08;Load&#xff09;过程。提供了一个简洁直观的界面&#xff0c;以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

EtherNet/IP转DeviceNet协议网关详解

一&#xff0c;设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络&#xff0c;本网关连接到EtherNet/IP总线中做为从站使用&#xff0c;连接到DeviceNet总线中做为从站使用。 在自动…...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列&#xff0c;以便知晓哪些列包含有价值的数据&#xff0c;…...

Yolov8 目标检测蒸馏学习记录

yolov8系列模型蒸馏基本流程&#xff0c;代码下载&#xff1a;这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中&#xff0c;**知识蒸馏&#xff08;Knowledge Distillation&#xff09;**被广泛应用&#xff0c;作为提升模型…...

MySQL 8.0 事务全面讲解

以下是一个结合两次回答的 MySQL 8.0 事务全面讲解&#xff0c;涵盖了事务的核心概念、操作示例、失败回滚、隔离级别、事务性 DDL 和 XA 事务等内容&#xff0c;并修正了查看隔离级别的命令。 MySQL 8.0 事务全面讲解 一、事务的核心概念&#xff08;ACID&#xff09; 事务是…...

【深度学习新浪潮】什么是credit assignment problem?

Credit Assignment Problem(信用分配问题) 是机器学习,尤其是强化学习(RL)中的核心挑战之一,指的是如何将最终的奖励或惩罚准确地分配给导致该结果的各个中间动作或决策。在序列决策任务中,智能体执行一系列动作后获得一个最终奖励,但每个动作对最终结果的贡献程度往往…...