算法之双指针系列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开发过程中的很多问题,本篇文…...
ubuntu20.04-编译安装Qt5.15.2-C++
文章目录 步骤一:安装依赖项步骤二:下载Qt 5.15源代码步骤三:配置并编译Qt步骤四:配置环境变量注意事项更新于2024年 在Ubuntu 22.04 LTS(Jammy Jellyfish)环境下编译Qt 5.15,由于Ubuntu 22.04的…...
【PTA|期末复习|编程题】数组相关编程题(二)
目录 7-1 数组元素循环右移问题(20分) 输入格式: 输出格式: 输入样例: 输出样例: 代码 7-2 找出不是两个数组共有的元素(20分) 输入格式: 输出格式: 输入样例: 输出样例: 代码 7-3 方阵循环右移(20分) 输入格式: 输出格式: 输入样例&…...
重温阿里云宝塔面板部署前后端项目
首先祝大家新年快乐啊! 回到老家,便打算趁这一段空闲时间提升一下自己,重点是学习实践一下echarts相关内容,很多公司项目都需要实现可视化,所以在bilibili上找了黑马的一个教程开始学习,不同的是ÿ…...
6个好看的wordpress模板
简站wordpress服务业通用主题 2023年立秋纪念版,简站wordpress服务行业通用主题,适合服务行业企业官网使用。 https://www.jianzhanpress.com/?p5393 小语种翻译wordpress主题 小语种国家外贸网站建设需要的wordpress主题模板,适合做小语…...
零基础学python之高级编程(1)---面向对象编程及其类的创建
面向对象编程及其类的创建 文章目录 面向对象编程及其类的创建前言一、面向过程编程和面向对象编程的概念1.面向过程编程(Procedural Programming)2.面向对象编程(Object-Oriented Programming,OOP) 二、面向对象编程基础1.初识类(class)和对象调用方法 2.类中的两种…...
[C# WPF] DataGrid选中行或选中单元格的背景和字体颜色修改
问题描述 WPF中DataGrid的选中行或选中者单元格,在焦点失去后,颜色会很淡,很不明显,不容易区分。 解决方法 在失去焦点的情况下,如何设置行或单元格与选中的时候颜色一样? <DataGrid.Resources>&…...
单片机学习笔记---串口通信(1)
目录 通信的基本概念 通信的方式 1.按照数据传送的方式,可分为串行通信和并行通信。 1.1串行通信 1.2并行通信 2.按照通信的数据同步方式,又可以分为异步通信和同步通信。 2.1 异步通信 2.2同步通信 3.按照数据的传输方向,又可以分为…...
熔断机制解析:如何用Hystrix保障微服务的稳定性
微服务与系统的弹性设计 大家好,我是小黑,在讲Hystrix之前,咱们得先聊聊微服务架构。想象一下,你把一个大型应用拆成一堆小应用,每个都负责一部分功能,这就是微服务。这样做的好处是显而易见的,更新快,容错性强,每个服务可以独立部署,挺美的对吧?但是,问题也随之而…...
第三节 zookeeper基础应用与实战2
目录 1. Watch事件监听 1.1 一次性监听方式:Watcher 1.2 Curator事件监听机制 2. 事务&异步操作演示 2.1 事务演示 2.2 异步操作 3. Zookeeper权限控制 3.1 zk权限控制介绍 3.2 Scheme 权限模式 3.3 ID 授权对象 3.4 Permission权限类型 3.5 在控制台…...
C# Socket通信从入门到精通(21)——Tcp客户端判断与服务器断开连接的三种方法以及C#代码实现
前言 我们开发的tcp客户端程序在连接服务器以后,经常会遇到服务器已经关闭但是作为客户端的我们不知道,这时候应该应该有一个机制我们可以实时监测客户端和服务器已经断开连接,如果已经断开了连接,我们应该及时报警提示用户客户端和服务器已经断开连接,本文介绍三种可以监…...
vulnhub-->hacksudo-Thor靶机详细思路
目录 1. IP探测2.端口服务扫描3.网站漏洞扫描4.目录扫描5.信息分析6.破壳漏洞(Shellshock)nmap---漏洞检测CVE-2014-6271 7.nc反弹8.提权9.service提权 1. IP探测 ┌──(root㉿kali)-[~] └─# arp-scan -l Interface: eth0, type: EN10MB, MAC: 00:0c:29:10:3c:9b, IPv4: 19…...
Java外卖小程序管理系统
技术架构: springboot ssm mysql redis 有需要该项目的小伙伴可以私信我你的Q。 功能描述: 商品管理:新增商品、所有商品 菜单管理:菜单管理、菜单分类 订单管理:订单总览(包括未付款、已付款、已…...
挖掘嵌入式系统在物联网和智能设备中的应用潜力
1. 物联网的发展和嵌入式系统 介绍物联网的定义和特点,以及其在各个领域中的应用。探讨物联网对嵌入式系统的需求,包括低功耗、小型化、实时性等特性,以及对嵌入式系统的数据处理和通信能力的要求。 2. 嵌入式系统在智能设备中的应用 分析…...
用docker 配置scala spark环境
要使用Docker配置Scala和Spark环境,您可以按照以下步骤进行操作。以下是一个基本的示例,您可能需要根据您的具体需求进行调整。 安装Docker: 在您的系统上安装Docker。您可以从Docker官方网站下载并安装适用于您操作系统的版本。 创建Dockerfile: 在您的…...
医疗处方架构设计和实现的实战经验总结
医疗处方是医生开具给患者的药物治疗建议。在现代医疗系统中,设计和实现一个高效而可靠的医疗处方架构至关重要。本文将介绍医疗处方架构的设计原则和关键组件,以及如何实现一个可扩展和安全的处方管理系统。 内容: 1. 引言 - 医疗处方的…...
专业140+总分410+华南理工大学811信号与系统考研经验华工电子信息与通信,真题,大纲,参考书。
23考研已经落幕,我也成功的上岸华工,回首这一年多的历程,也是有一些经验想和大家分享一下。 首先说一下个人情况,本科211,初试成绩400分。专业课140。 整体时间安排 对于考研,很重要的一环就是时间安排&…...
软件测试学习笔记-测试用例的编写
7中测试分类 按照阶段可划分单元测试、集成测试、系统测试、验收测试。代码可见度划分黑盒测试、灰盒测试、白盒测试 单元测试:针对源代码的测试 集成测试:针对接口进行测试 系统测试:针对功能和非功能的测试 验收测试:公测、内测…...
『运维备忘录』之 Kubernetes(K8S) 常用命令速查
一、简介 kubernetes,简称K8s,是用8代替名字中间的8个字符“ubernete”而成的缩写,是一个开源的,用于管理云平台中多个主机上的容器化的应用。kubernetes是基于容器技术的分布式架构解决方案,具有完备的集群管理能力&a…...
Android SDK 上传 Maven 喂奶级教程
最近领导给安排了个任务,让我把我们现有的一个 SDK 上传到 Maven 上去,方便客户直接用 gradle 依赖,不再需要拷贝 jar 和 so 了,此前我也看过一些相关的文章我想问题也不大,觉得工作量也就一两天的事情,主要…...
R语言绘图教程 | 双侧条形图绘制教程
写在前面 双侧条形图在我们的文章中也是比较常见的,那么这样的图形是如何绘制的呢? 以及它使用的数据类型是什么呢? 这些都是我们在绘制图形前需要掌握的,至少我们知道绘图的数据集如何准备,这样才踏出第一步。 今天的教程,我们会从数据的准备,以及数据如何整理,以及…...
ubuntu篇---ubuntu安装python3.9
ubuntu篇—ubuntu安装python3.9 在ubuntu上安装Python有两种方法:在线安装和源码编译安装。 方法1:使用apt在线安装 1.更新软件包列表并安装必备组件: $ sudo apt update $ sudo apt install software-properties-common2.将Deadsnakes PPA添加到系统…...
git初始化一个远程空仓库
目录 1. 仅做简单初始化2. 推送现有的非仓库文件夹3. 推送现有的仓库 git初始化一个远程空仓库主要有以下三种途径: 仅做简单初始化,例如添加 README.md 和 .gitignore。将现有的文件夹(非仓库)推送到远程仓库。将现有的仓库推送…...
装箱问题+宠物小精灵之收服+数字组合——01背包
一、装箱问题 (裸题) 有一个箱子容量为 V,同时有 n 个物品,每个物品有一个体积(正整数)。 要求 n 个物品中,任取若干个装入箱内,使箱子的剩余空间为最小。 输入 第一行是一个整数 V (0 < V ≤ 20000)&…...
记一次页面接口502问题:“502 Bad Gateway”
接收别人的项目进行迭代,项目部署到服务器上之后,有一个接口数据刷不出来,一直502 后来联想到网关的问题,想通过设置白名单的方式解决,设置之后依旧不行。 查看nginx日志发现报错: *169 connect() failed …...
Oracle systemstate、gdb、dbx介绍
当数据库出现严重的性能问题或者hang了的时候, 可能最常用的办法就是重启数据库,简单有效解决问题;但是重启后如何追踪问题的根本原因成了难题,很多信息随着重启也消失不见了,让追查问题变的十分棘手,这时就…...
Stable Diffusion 模型下载:RealCartoon-Anime - V10
文章目录 模型介绍生成案例案例一案例二案例三案例四案例五案例六案例七案例八案例九案例十下载地址模型介绍 这个检查点是从 RealCartoon3D 检查点分支出来的。它的目标是产生更多的“动漫”风格,因为我喜欢动漫。:)我知道有很多人做得很好(...
课时22:内置变量_字符串相关
2.4.2 字符串相关 学习目标 这一节,我们从 基础知识、简单实践、小结 三个方面来学习 基础知识 字符串相关的变量解析 字符串计数${#file} 获取字符串的长度字符串截取 - 语法为${var:pos:length} 表示对变量var从pos开始截取length个字符,pos为…...
软件应用实例分享,电玩计时计费怎么算,佳易王PS5游戏计时器系统程序教程
软件应用实例分享,电玩计时计费怎么算,佳易王PS5游戏计时器系统程序教程 一、前言 以下软件教程以 佳易王电玩计时计费管理系统软件V17.9为例说明 软件文件下载可以点击最下方官网卡片——软件下载——试用版软件下载 点击开始计时后,图片…...
架设游戏服务器租用价格?腾讯云和阿里云价格对比
游戏服务器租用多少钱一年?1个月游戏服务器费用多少?阿里云游戏服务器26元1个月、腾讯云游戏服务器32元,游戏服务器配置从4核16G、4核32G、8核32G、16核64G等配置可选,可以选择轻量应用服务器和云服务器,阿腾云atengyu…...
ag-Grid:对数据变化的单元格进行高亮显示
对单元格高亮 问:ag-grid 当 rowData 数据变化,如何对数据变化的党员个进行高亮? 解析: 在ag-Grid中,想要对数据变化的单元格进行高亮显示,你可以使用以下步骤来实现: 监听数据变化:首先,你需要监听rowData的变化。这可以通过在你的组件中观察rowData属性的变化来实…...