算法之双指针系列1
目录
一:双指针的介绍
1:快慢指针
2:对撞指针
二:对撞指针例题讲述
一:双指针的介绍
在做题中常用两种指针,分别为对撞指针与快慢指针。
1:快慢指针
简称为龟兔赛跑算法,它的基本思想是使用两个移动速度不同的指针在数组或链表等序列结构上移动。
这种对于处理环形链表和数组以及循环重复问题,是非常好用的。
2:对撞指针
简称为左右指针,它的基本思想是一个指针从最左端开始,一个从最右端开始,逐渐往中间逼近。一般终止条件是两个指针相遇或者错开。
一般用于顺序结构中。
注意:这里的指针并不是C语言中的指针,而是指在数组中设置的两个下标,通过改变两个下标来改变所在数组的位置。
二:对撞指针例题讲述
力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台
1:盛最多水容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明:你不能倾斜容器。
算法原理:
解法1:暴力枚举,是很简单的,但是我们可以发现他的时间复杂度是超时的。
解法2:双指针法,题中让求v,那么v=h*w.
| 1 | 8 | 6 | 2 | 5 | 4 | 8 | 3 | 7 |
就以上面的数组举例。
我们设左指针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
目录 一:双指针的介绍 1:快慢指针 2:对撞指针 二:对撞指针例题讲述 一:双指针的介绍 在做题中常用两种指针,分别为对撞指针与快慢指针。 1:快慢指针 简称为龟兔赛跑算法,它的基…...
苍穹外卖面试题
8. 如何理解分组校验 很多情况下,我们会将校验规则写到实体类中的属性上,而这个实体类有可能作为不同功能方法的参数使用,而不同的功能对象参数对象中属性的要求是不一样的。比如我们在新增和修改一个用户对象时,都会接收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、概述 今天是大年初一,先给大家拜个年&am…...
CI/CD到底是啥?持续集成/持续部署概念解释
前言 大家好,我是chowley,日常工作中,我每天都在接触CI/CD,今天就给出我心中的答案。 在现代软件开发中,持续集成(Continuous Integration,CI)和持续部署(Continuous D…...
golang常用库之-disintegration/imaging图片操作(生成缩略图)
文章目录 golang常用库之什么是imaging库导入和使用生成缩略图 golang常用库之 什么是imaging库 官网:https://github.com/disintegration/imaging imaging 是一个 Go 语言的图像处理库,它提供了一组功能丰富的函数和方法,用于进行各种图像…...
CSS 控制 video 标签的控制栏组件的显隐
隐藏下载功能 <video src"" controlsList"nodownload" />controlslist 取值如下(设定多个值则使用空格进行间隔) 如:controlslist"nodownload nofullscreen noremoteplayback"nodownload:取消更多控件弹窗的下载功…...
数据可视化之维恩图 Venn diagram
文章目录 一、前言二、主要内容三、总结 🍉 CSDN 叶庭云:https://yetingyun.blog.csdn.net/ 一、前言 维恩图(Venn diagram),也叫文氏图或韦恩图,是一种关系型图表,用于显示元素集合之间的重叠区…...
2024刘谦春晚第二个扑克牌魔术
前言 就是刚才看春晚感觉这个很神奇,虽然第一个咱模仿不过来,第二个全国人民这么多人,包括全场观众都有成功,这肯定是不需要什么技术,那我觉得这个肯定就是数学了,于是我就胡乱分析一通。 正文 首先准备…...
【k8s系列】(202402) 证书apiserver_client_certificate_expiration_seconds
apiserver_client_certificate_expiration_second证书定义的位置:kubernetes/staging/src/k8s.io/apiserver/pkg/authentication/request/x509/x509.go at 244fbf94fd736e94071a77a8b7c91d81163249d4 kubernetes/kubernetes (github.com) apiserver_client_certi…...
Rust变量与常量介绍
Rust是一门注重安全性和性能的系统编程语言,其中变量和常量的概念有着独特的设计和特性。在本文中,我们将深入了解Rust中的变量和常量,并解释它们之间的区别,同时通过多个例子进行说明。 Rust常量 在Rust中,常量是不…...
Flask基础学习2
连接mysql数据库测试(专业版) [注意1:要导入text库,否则可能出现找不到select 1错误] [注意2:若出现下列问题,可按照模板代码的顺序db SQLAlchemy(app) 的位置] RuntimeError: Either SQLALCHEMY_DATABASE_URI or SQLALCHEMY_B…...
文章页的上下篇功能是否有必要?boke112百科取消上下篇功能
也不知道是从什么时候开始,我们很多站长的博客网站文章页都会在文末添加上“上一篇”和“下一篇”功能,目的是进行站内SEO优化和方便用户阅读上下篇文章。 boke112百科不管是以前使用的Three主题还是现在使用的YIA主题,刚开始的文章页都是有…...
Lua序列化
我们经常需要序列化一些数据,为了将数据转换为字节流或者字符流,这样我们就可以保存到文件或者通过网络发送出去。我们可以在 Lua 代码中描述序列化的数据,在这种方式下,我们运行读取程序即可从代码中构造出保存的值。 number/st…...
Acwing---839. 模拟堆
模拟堆 1.题目2.基本思想3.代码实现 1.题目 维护一个集合,初始时集合为空,支持如下几种操作: I x,插入一个数 x;PM,输出当前集合中的最小值;DM,删除当前集合中的最小值(…...
STM32 STD/HAL库驱动W25Q64模块读写字库数据+OLED0.96显示例程
STM32 STD/HAL库驱动W25Q64 模块读写字库数据OLED0.96显示例程 🎬原创作者对W25Q64保存汉字字库演示: W25Q64保存汉字字库 🎞测试字体显示效果: 📑功能实现说明 利用W25Q64保存汉字字库,OLED显示汉字的时…...
Android 移动应用开发 创建第一个Android项目
文章目录 一、创建第一个Android项目1.1 准备好Android Studio1.2 运行程序1.3 程序结构是什么app下的结构res - 子目录(所有图片、布局、字AndroidManifest.xml 有四大组件,程序添加权限声明 Project下的结构 二、开发android时,部分库下载异…...
MATLAB语音去噪系统
目录 一、背景 二、GUI页面 三、程序 3.1 LMS滤波程序 3.2 GUI程序 四、附录 一、背景 本文介绍了一种最佳的自适应滤波器结构,该结构采用最小均方差(LMS)作为判据,通过不断迭代自适应结构来调整得到最佳滤波器…...
小程序-上传图片功能
技术前置: 1.框架采用colorUI 2.原生开发 功能: 上传图片 1.上传已经拍摄的图片 2.实时拍摄上传 3.设置上传图片数量,每次上传数量 4.上传等待 ChooseImage() {if(this.data.imgList.length>4){_this.ErrorEvent("最多上传4…...
alist基本用法@文档阅读@挂载网盘@网盘webdav挂载
文章目录 alist官网alist网站风格说明alist软件版本 安装和启动使用必看文档👺alist for android版本启动alist网页 典型用例挂载阿里云盘open获取阿里云令牌 主页检查挂载情况 常用页面以配置挂载列表管理配置页面 配置文件和目录👺FAQ可能遇到的错误检…...
Hive正则表达式
Hive版本:hive-3.1.2 一、Hive的正则表达式概述 正则表达式是一种用于匹配和操作文本的强大工具,它是由一系列字符和特殊字符组成的模式,用于描述要匹配的文本模式。 Hive的正则表达式灵活使用解决HQL开发过程中的很多问题,本篇文…...
Python爬虫实战:研究MechanicalSoup库相关技术
一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...
椭圆曲线密码学(ECC)
一、ECC算法概述 椭圆曲线密码学(Elliptic Curve Cryptography)是基于椭圆曲线数学理论的公钥密码系统,由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA,ECC在相同安全强度下密钥更短(256位ECC ≈ 3072位RSA…...
多场景 OkHttpClient 管理器 - Android 网络通信解决方案
下面是一个完整的 Android 实现,展示如何创建和管理多个 OkHttpClient 实例,分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...
Cesium1.95中高性能加载1500个点
一、基本方式: 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...
linux 错误码总结
1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...
苍穹外卖--缓存菜品
1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得,如果用户端访问量比较大,数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据,减少数据库查询操作。 缓存逻辑分析: ①每个分类下的菜品保持一份缓存数据…...
C# 类和继承(抽象类)
抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...
【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)
升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点,但无自动故障转移能力,Master宕机后需人工切换,期间消息可能无法读取。Slave仅存储数据,无法主动升级为Master响应请求ÿ…...
MySQL用户和授权
开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务: test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...
【开发技术】.Net使用FFmpeg视频特定帧上绘制内容
目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法,当前调用一个医疗行业的AI识别算法后返回…...
