算法之双指针系列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};

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/253613.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

上海泗博HART转ModbusTCP网关HME-635应用案例之组态王和超声波液位计通信

如今工业现场的应用也逐渐把现场的不同应用协议转换成以太网&#xff0c;以此来提升现场的通信速度和质量。Modbus TCP是工业以太网协议的一种&#xff0c;也是现场应用中最常使用的。本应用案例是基于Modbus TCP的组态王和基于HART的超声波液位计之间数据通讯的具体应用。 应用…

STM32F407 CAN参数配置 500Kbps

本篇CAN参数适用 芯片型号&#xff1a;STM32F407xx系统时钟&#xff1a;168MHz&#xff0c;CAN挂载总线APB1为42M波 特 率 &#xff1a;500Kpbs引脚使用&#xff1a;TX_PB9&#xff0c;RX_PB8&#xff1b;修改为PA11PA12后&#xff0c;参数不变。 步骤一、打勾开启CAN&#xf…

vector类的模拟实现

实现基本的vector框架 参考的是STL的一些源码&#xff0c;实现的vector也是看起来像是一个简略版的&#xff0c;但是看完能对vector这个类一些接口函数更好的认识。 我们写写成员变量&#xff0c;先来看看STL的成元变量是那些 namespace tjl {template<class T>class …

无损音乐下载,最新音乐下载,mp3格式音乐下载,一键下载mp3格式音乐,我只用这个软件,歌曲资源丰富,全网音乐免费下载,稳定运行,告别收费

一、软件简介 现在很多支持一键下载mp3音乐/无损音质音乐的音乐播放器通常都是解析接口套了一个壳&#xff0c;一旦解析接口失效&#xff0c;软件就不能下载音乐了&#xff0c;因此一个稳定的解析接口是这类软件最大的保障。本次小编推荐的音乐下载软件接口非常稳定&#xff0…

C语言:函数

创作不易&#xff0c;友友们给个三连吧&#xff01;&#xff01; 一、函数的概念 数学中我们见过函数的概念&#xff0c;例如ykxb&#xff0c;k和b都是常数&#xff0c;给任意一个x就可以得到y 而C语言也引入了函数&#xff08;function&#xff09;这个概念&#xff0c;C语…

利用LLM大模型生成sql的深入应用探究

Chat2DB 是一款有开源免费的多数据库客户端工具,和传统的数据库客户端软件Navicat、DBeaver 相比 Chat2DB 集成了 AIGC 的能力&#xff0c;能够将自然语言转换为 SQL&#xff0c;也可以将 SQL 转换为自然语言&#xff0c;可以给出研发人员 SQL 的优化建议&#xff0c;极大地提升…

初识C语言·预处理详解

目录 1 预定义符号 2 define定义常量 3 #define定义宏 4 带有副作用的宏 5 宏替换的规则 6 宏和函数的对比 7 # 和 ## i) #运算符 ii) ##运算符 8 命名约定 9 命令行定义 10 条件编译 条件编译1&#xff1a; 条件编译2&#xff1a; 条件编译3&#xff1a; 条件…

单片机学习笔记---LED点阵屏的工作原理

目录 LED点阵屏分类 LED点阵屏显示原理 74HC595的介绍 一片74HC595的工作原理 多片级联工作原理 总结 LED点阵屏由若干个独立的LED组成&#xff0c;LED以矩阵的形式排列&#xff0c;以灯珠亮灭来显示文字、图片、视频等。LED点阵屏广泛应用于各种公共场合&#xff0c;如汽…

鸿蒙(HarmonyOS)项目方舟框架(ArkUI)之ScrollBar组件

鸿蒙&#xff08;HarmonyOS&#xff09;项目方舟框架&#xff08;ArkUI&#xff09;之ScrollBar组件 一、操作环境 操作系统: Windows 10 专业版、IDE:DevEco Studio 3.1、SDK:HarmonyOS 3.1 二、ScrollBar组件 鸿蒙&#xff08;HarmonyOS&#xff09;滚动条组件ScrollBar&…

Logback - 日志框架

引言 在当今的企业级应用开发中&#xff0c;日志管理是一个不可或缺的部分。它不仅帮助我们进行错误跟踪&#xff0c;还能有效监控应用程序的运行状态&#xff0c;为性能优化提供数据支撑。Spring Boot作为一个简化Spring应用开发的框架&#xff0c;自带了强大的日志管理功能。…

如何用python进行数据分析?

前言 很多人可能会有这样的疑问&#xff0c;数据分析Excel挺强大的&#xff0c;会Excel就行&#xff0c;为什么还要去学python&#xff1f; 是的&#xff0c;Excel和python对于数据分析而言&#xff0c;这两者都只是不同的工具而已。 但&#xff0c;有一点我们要考虑&#x…

iOS 需求 多语言(国际化)App开发 源码

一直觉得自己写的不是技术&#xff0c;而是情怀&#xff0c;一个个的教程是自己这一路走来的痕迹。靠专业技能的成功是最具可复制性的&#xff0c;希望我的这条路能让你们少走弯路&#xff0c;希望我能帮你们抹去知识的蒙尘&#xff0c;希望我能帮你们理清知识的脉络&#xff0…

路由器、路由器的构成、交换结构

目录 1 路由器 1.1 路由器的结构 “转发”和“路由选择”的区别 1.1.1 输入端口对线路上收到的分组的处理 1.1.2 输出端口将交换结构传送来的分组发送到线路 2.2 交换结构 2.2.1 通过存储器 2.2.2 通过总线 2.2.3 通过纵横交换结构 (crossbar switch fabric) 1 路由器…

BUGKU-WEB 留言板

题目描述 题目无需登录后台&#xff01;需要xss平台接收flag&#xff0c; http协议需要http协议的xss平台打开场景后界面如下&#xff1a; 解题思路 看到此类的题目&#xff0c;应该和存储型xss有关&#xff0c;也就是将恶意代码保存到服务器端即然在服务器端&#xff0c;那就…

CSS 闪电按钮效果

<template><view class="const"><div class="voltage-button"><button>闪电按钮</button><svg version="1.1" xmlns="http://www.w3.org/2000/svg" x="0px" y="0px" viewBox=&q…

简易计算器的制作(函数指针数组的实践)

个人主页&#xff08;找往期文章包括但不限于本期文章中不懂的知识点&#xff09;&#xff1a; 我要学编程(ಥ_ಥ)-CSDN博客 前期思路&#xff08;菜单的制作等&#xff09;&#xff1a;利用C语言的分支循环少量的函数知识写一个猜数字的小游戏-CSDN博客 计算器的制作其实与游…

使用ChatGpt和文心一言辅助文章创作

近期在写数字水浒系列文章&#xff0c;使用了ChatGpt和文心一言进行辅助创作&#xff0c;整体感受不错&#xff0c;提高了工作效率。 在使用过程中&#xff0c;感觉文心的中文能力更强一些&#xff0c;主要体现在&#xff1a; 1 语料库更大&#xff0c;比如对水浒传了解的更多…

Postman(接口测试工具),什么是Postman接口

目录 一.基本介绍 Postman 是什么Postman 快速入门快速入门需求说明 二.Postman 完成 Controller 层测试 需要的代码&#xff1a; Java类request.jspsuccess.jsp1. 完成请求2. 完成请求3. 完成请求4. 完成请求5. 完成请求 三.发送join 目录 一.基本介绍 Postman 是什么 …

微信小程序解决华为手机保存图片到相册失败

1.新增隐私设置 2.优化代码 新增uni.authorize判断 _saveCode() {let that this;console.log(点击了保存图片)console.log(this.result)uni.authorize({scope: scope.writePhotosAlbum,success(e) {console.log(e)if (this.result ! "") {uni.saveImageToPhotosAlb…

一步步建立一个C#项目(连续读取S7-1200PLC数据)

这篇博客作为C#的基础系列,和大家分享如何一步步建立一个C#项目完成对S7-1200PLC数据的连续读取。首先创建一个窗体应用。 1、窗体应用 2、配置存储位置 3、选择框架 拖拽一个Button,可以选择视图菜单---工具箱 4、工具箱 拖拽Lable控件和TextBook控件 5、拖拽控件 接下来…