当前位置: 首页 > 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;本篇文…...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄

文&#xff5c;魏琳华 编&#xff5c;王一粟 一场大会&#xff0c;聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中&#xff0c;汇集了学界、创业公司和大厂等三方的热门选手&#xff0c;关于多模态的集中讨论达到了前所未有的热度。其中&#xff0c;…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)

2025年能源电力系统与流体力学国际会议&#xff08;EPSFD 2025&#xff09;将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会&#xff0c;EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

多场景 OkHttpClient 管理器 - Android 网络通信解决方案

下面是一个完整的 Android 实现&#xff0c;展示如何创建和管理多个 OkHttpClient 实例&#xff0c;分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...

淘宝扭蛋机小程序系统开发:打造互动性强的购物平台

淘宝扭蛋机小程序系统的开发&#xff0c;旨在打造一个互动性强的购物平台&#xff0c;让用户在购物的同时&#xff0c;能够享受到更多的乐趣和惊喜。 淘宝扭蛋机小程序系统拥有丰富的互动功能。用户可以通过虚拟摇杆操作扭蛋机&#xff0c;实现旋转、抽拉等动作&#xff0c;增…...

Linux 下 DMA 内存映射浅析

序 系统 I/O 设备驱动程序通常调用其特定子系统的接口为 DMA 分配内存&#xff0c;但最终会调到 DMA 子系统的dma_alloc_coherent()/dma_alloc_attrs() 等接口。 关于 dma_alloc_coherent 接口详细的代码讲解、调用流程&#xff0c;可以参考这篇文章&#xff0c;我觉得写的非常…...

6️⃣Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙

Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙 一、前言:离区块链还有多远? 区块链听起来可能遥不可及,似乎是只有密码学专家和资深工程师才能涉足的领域。但事实上,构建一个区块链的核心并不复杂,尤其当你已经掌握了一门系统编程语言,比如 Go。 要真正理解区…...

字符串哈希+KMP

P10468 兔子与兔子 #include<bits/stdc.h> using namespace std; typedef unsigned long long ull; const int N 1000010; ull a[N], pw[N]; int n; ull gethash(int l, int r){return a[r] - a[l - 1] * pw[r - l 1]; } signed main(){ios::sync_with_stdio(false), …...

路由基础-路由表

本篇将会向读者介绍路由的基本概念。 前言 在一个典型的数据通信网络中&#xff0c;往往存在多个不同的IP网段&#xff0c;数据在不同的IP网段之间交互是需要借助三层设备的&#xff0c;这些设备具备路由能力&#xff0c;能够实现数据的跨网段转发。 路由是数据通信网络中最基…...

Docker、Wsl 打包迁移环境

电脑需要开启wsl2 可以使用wsl -v 查看当前的版本 wsl -v WSL 版本&#xff1a; 2.2.4.0 内核版本&#xff1a; 5.15.153.1-2 WSLg 版本&#xff1a; 1.0.61 MSRDC 版本&#xff1a; 1.2.5326 Direct3D 版本&#xff1a; 1.611.1-81528511 DXCore 版本&#xff1a; 10.0.2609…...

深入理解 C++ 左值右值、std::move 与函数重载中的参数传递

在 C 编程中&#xff0c;左值和右值的概念以及std::move的使用&#xff0c;常常让开发者感到困惑。特别是在函数重载场景下&#xff0c;如何合理利用这些特性来优化代码性能、确保语义正确&#xff0c;更是一个值得深入探讨的话题。 在开始之前&#xff0c;先提出几个问题&…...