双指针(滑动窗口)-算法刷题
一.移动零(. - 力扣(LeetCode))

算法思想 :
设置两个指针left,right,将数组分为三块[0,left]为不为0的元素,[left+1,right-1]为0元素,[right,num.size()-1]为未扫描的区域,判断right位置,不为0元素则与left+1位置元素交换,left++和right++;为0则只有right++,这样right扫描到最右侧时保证右侧全是0。

class Solution {
public:void moveZeroes(vector<int>& nums){int cur=0,dest=-1;while(cur<nums.size()){if(nums[cur]){swap(nums[cur],nums[++dest]);}cur++; }}
};
ps:数组分块扫描划分是快排的核心思想
二.排序数组

算法思想:
与移动0相似,不过这里移动指针时将数组分为四块,l,r是当前(子)数组的最左侧与右侧,用i,left,right三个指针,[l,left]为小于随机基准元素key的区域,[left+1,i-1]是key区域,[i,right-1]为未扫描区域,[right,r]为大于key的元素,移动时控制区间即可。

void qsort(vector<int>& nums,int l,int r)
{if(l>=r) return;int key=nums[rand()%(r-l+1)+l];int i=l,left=l-1,right=r+1;while(i<right){if(nums[i]<key){swap(nums[++left],nums[i]);i++;}else if(nums[i]>key){--right;swap(nums[right],nums[i]);}else{i++;}}qsort(nums,l,left);qsort(nums,right,r);
}
class Solution {
public:vector<int> sortArray(vector<int>& nums) {srand(time(NULL));qsort(nums,0,nums.size()-1);return nums;}
};
三.复写零
算法思想:
1.找到最后一个要复写的元素。

cur为扫描指针,dest为移动指针,初始cur为0,dest为-1;当dest移动到最后一个元素时,cur指向最后一个要复写的元素。 但这里dest可能会超出(说明cur此时指向0),所以要先判断边界位置。

2.“从后往前”复写元素。
是0就将cur位置元素赋值给dest位置和dest-1位置,然后dest-=2;非0就将cur直接赋给dest位置,dest-=1;然后都有cur--。
void duplicateZeros(vector<int>& nums){//先找到最后一个数int cur=0,dest=-1;int tmp = nums.size() - 1;while(dest < tmp){if (nums[cur] == 0){dest += 2;}else{dest += 1;}if (dest >= tmp) break;cur++;}//判断边界情况,如果超出,就事先处理if(dest>nums.size()-1){cur--;dest-=2;nums[nums.size()-1]=0;}//从后向前复写for(;cur>=0;cur--){if(nums[cur]==0){nums[dest]=nums[dest-1]=0;dest-=2;}else{nums[dest]=nums[cur];dest--;}}}
四.快乐数(. - 力扣(LeetCode))
算法思想:
快慢指针的思想,因为这里数字最后都会循环,只要看快指针最后在环里与满指针相遇时所在的元素是否为一即可。

int fx(int x)
{int sum=0;while(x){sum+=(x%10)*(x%10);x/=10;}return sum;
}class Solution {
public:bool isHappy(int n) {int fast=n,slow=n;while(1){slow=fx(slow);fast=fx(fast);fast=fx(fast);if(fast==slow){if(fast==1)return true;elsereturn false; }}}
};
五.盛最多水的容器(. - 力扣(LeetCode))

算法思想:
对撞指针,设置left,right指针分别向左右侧,记录盛水量,去除左/右移较小元素的位置(因为移动更大一侧不会改变最大值),记录最大值即可。
class Solution {
public:int maxArea(vector<int>& height) {if(height.size() <= 1) return 0;int res = 0;//保存答案int l = 0, r = height.size() - 1;//开始时,l指向最左边的挡板,r指向最右边的挡板while(l < r)//如果l,r之间还有挡板{res = max(min(height[l], height[r]) * (r - l), res);//计算盛水值if(height[l] <= height [r])//谁小谁以后就不用再考虑 l++;elser--;}return res;}
};
六 .有效三角形的个数(. - 力扣(LeetCode))

算法思想:
先将数组排序,利用单调性使用双指针解决 。如下图a,b,c三个指针,当left,right指向判断区间左右侧,当a+b>c时,说明a右侧的全部元素都和b,c符合,所以right--来继续判断其他组合情况,当a+b<c时,说明此时abc不符合,让left++,重新判断a+b与c。直到left==right时结束这次循环,将c--(重新选择最大数)判断剩下组合。时间复杂度O(N*N);

class Solution {
public:int triangleNumber(vector<int>& nums) {sort(nums.begin(),nums.end());int sum=0;for(int i=nums.size()-1;i>1;i--){int left=0,right=i-1;while(left<right){if(nums[left]+nums[right]>nums[i]){sum+=right-left;right--;}else{left++;}}}return sum;}
};
七.三数之和 (. - 力扣(LeetCode))

算法思想:
先排序,利用单调性用双指针解决问题。即依旧a(left),b(right),c三个指针,c指向当次循环最大值(初始指向数组最大值),判断a+b+c与0的关系,如果a+b+c<0则a++,a+b+c>0则b--,直到找出等于0的组合并记录下来,注意要去重操作(防止相同数字组合在一起)。当次操作完成后c--即可两层循环,时间复杂度依旧是O(N*N)。
class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> ret;sort(nums.begin(),nums.end());for(int i=0;i<=nums.size()-3;i++){int left=i+1,right=nums.size()-1;while(left<right){if(nums[i]+nums[left]+nums[right]<0){left++;}else if(nums[i]+nums[left]+nums[right]>0){right--;}else{//记录 ret.push_back({nums[i],nums[left],nums[right]});//去重left++,right--;while(left<right&&nums[left]==nums[left-1]) left++;while(left<right&&nums[right]==nums[right+1]) right--;}}while(i<=nums.size()-4&&nums[i]==nums[i+1]) i++;}return ret;}
};
八.长度最小的子数组(. - 力扣(LeetCode))

算法解析:
2个指针,扫描(前窗口)指针,尾指针。滑动窗口的步骤:1.扫描元素入窗口。2.判断是否需要出窗口。3.窗口向前滑动。 //记录结果这一步可以根据情况来调整位置。

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums){int left=0,right=0,n=nums.size();int sum=0,len=INT_MAX;while(right<n){//入窗口sum+=nums[right];//判断while(sum>=target){//更新结果len=min(len,right-left+1);//出窗口sum-=nums[left++];}right++;}return len==INT_MAX?0:len;}
};
相关文章:
双指针(滑动窗口)-算法刷题
一.移动零(. - 力扣(LeetCode)) 算法思想 : 设置两个指针left,right,将数组分为三块[0,left]为不为0的元素,[left1,right-1]为0元素,[right,num.size()-1]为未扫描的区域,…...
上位机图像处理和嵌入式模块部署(qmacvisual之ROI设定)
【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱:feixiaoxing 163.com】 ROI,全称是region of interest,也就是感兴趣区域。这里面一般分成两种情况,一种是所有的算法都依赖于这个ROI&a…...
银行监管报送系统介绍(五):金融统计数据大集中自动化报送系统——PBOC Report
人民银行金融统计数据大集中自动化报送系统(简称PBOC Report),是基于现代计算机网络技术应用基础上,由人行总行设置金融统计数据服务器,建立的一个全国统一的金融统计数据库。 人行针对各银行存贷款、中间业务、网点人…...
常用中间件redis,kafka及其测试方法
常用消息中间件及其测试方法 一、中间件的使用场景引入中间件的目的一般有两个:1、提升性能常用的中间件:1) 高速缓存:redis2) 全文检索:ES3) 存日志:ELK架构4) 流量削峰:kafka 2、提升可用性产品架构中高可…...
ROS1通过rosbridge在局域网中控制turtle进行运动(PC和手机)
通过ROSbridge控制小海龟(turtlesim)的具体案例。使用一个简单的Python脚本通过通过局域网上连接上传ROSbridge服务器,并发送速度指令来控制小海龟的移动 功能包的结构如下: HTML文件的编写(界面) html用…...
MQ高级篇---消息可靠性
MQ的一些常见问题 后面内容基于springboot 2.3.9.RELEASE 消息可靠性 生产者确认机制 在publisher微服务中application.yml中添加 spring:rabbitmq:publisher-confirm-type: correlatedpublisher-returns: truetemplate:mandatory: true每个RabbitTemplate只能配置一个Return…...
SpringMVC | SpringMVC中的 “文件上传和下载”
目录: 一、文件上传1.1 文件上传“概述”1.2 文件上传“具体配置” :“前端”中配置“文件上传” ( type“file” 满足3个条件 )“后端”中配置“文件上传” ( 配置id为“CommonsMultipartResolver”的bean 配置“文件上传”的“约束条件” 通过“MultipartFile接口”参数接…...
JVM快速入门(2)HotSpot和堆、新生区、永久区、堆内存调优、JProfiler工具分析OOM原因、GC(垃圾回收)、JVM经典面试笔试题整理
5.6 HotSpot和堆 5.6.1 Hotspot 三种JVM: Sun公司,HotspotBEA,JRockitIBM,J9 VM,号称是世界上最快的Java虚拟机 我们一般学习的是:HotSpot 5.6.2 堆 Heap,一个JVM只有一个堆内存,…...
我的风采——android studio
目录 实现“我的风采”页面要求理论代码生成apk文件 实现“我的风采”页面 要求 要求利用’java框架的边框布局实现“找的风采 ”页而,其中中间为你的生活照,左右和下面为按钮,上面为标签 理论 Java GUI编程是Java程序设计的重要组成部分…...
BMS设计中的短路保护和MOSFET选型(上)
电池管理系统(BMS)是一种能够对电池进行监控和管理的电子装备,是电池与用户之间的纽带。通过对电压、电流、温度以及SOC等数据采集,计算进而控制电池的充放电过程,主要就是为了能够提高电池的利用率,防止电…...
用go实现一个任务调度类 (泛型)
用go实现一个任务调度类 (泛型) 源码地址: https://github.com/robinfoxnan/BirdTalkServer/blob/main/server/core/workmanager.go 1.概述 实现了一个简单的任务管理系统,允许用户定义任务和工作者,并将任务分配给…...
ansible 管理工具以及常用模块
一、前期准备 1、安装 yum install ansible 如果yum源没有ansible,需要提前配置yum源: mv /etc/yum.repos.d/epel.repo /etc/yum.repos.d/epel.repo.backup mv /etc/yum.repos.d/epel-testing.repo /etc/yum.repos.d/epel-testing.repo.backup wget -O…...
javaSSM公司招聘管理系统IDEA开发mysql数据库web结构计算机java编程maven项目
一、源码特点 IDEA开发SSM公司招聘管理系统是一套完善的完整企业内部系统,结合SSM框架和bootstrap完成本系统,对理解JSP java编程开发语言有帮助系统采用SSM框架(MVC模式开发)MAVEN方式加 载,系统具有完整的源代码和…...
蓝桥杯day11刷题日记
P8615 [蓝桥杯 2014 国 C] 拼接平方数 思路:先把数据范围内的平方数打上标记,然后就是遍历这个区间,转成字符串(好拆数据),用substr拆开数据,再强转成整数类型,最后查看拆开的数据是…...
IDEA, Pycharm, Goland控制台乱码
IDEA, Pycharm, Goland控制台乱码 问题描述: 控制台出现����等乱码 复现频率: 总是 解决方案: 以IDEA为例 添加 -Dfile.encodingUTF-8位置 idea64.exe.vmoptions 在安装idea的bin目录idea.vmoptions idea客户端 示意图...
JavaScript单元测试jasmine学习(一)
介绍: jasmine是用于测试JavaScript的一种测试框架,BDD(Behavior Driven Development)行为驱动开发。不依赖于任何其他JavaScript框架,也不需要DOM 准备工作: 1. 首先添加jasmine到自己的项目中 npm install --save-dev jasmine 2. 在项目…...
108、3D Gaussian Splatting for Real-Time Radiance Field Rendering
简介 官网 更少训练时间的同时实现最先进的视觉质量,能在1080p分辨率下实现高质量的实时(≥30 fps)新视图合成 NeRF使用隐式场景表示,体素,点云等属于显示建模方法,3DGS就是显示辐射场。它用3D高斯作为灵活高效的表示方法&…...
PHP之CURL和Socket
文章目录 一、CURL1.基本流程(1)初始化(2)向服务器发送请求(3)向服务器发送请求(4)关闭curl 2.CURLOPT参数记得写一个文件curl上传的例子记得写一个json上传的例子3.CURL批处理 二、…...
【Web】NKCTF 2024 个人wp(部分)
目录 my first cms 全世界最简单的CTF attack_tacooooo 属实太菜了,3/4 my first cms 一眼搜版本2.2.19 CVE -CVE-2024-27622 GitHub - capture0x/CMSMadeSimple 访问/admin/login.php 爆出弱口令,后台登录 admin Admin123 Extensions > User D…...
QT常见布局器使用
布局简介 为什么要布局?通过布局拖动不影响鼠标拖动窗口的效果等优点.QT设计器布局比较固定,不方便后期修改和维护;在Qt里面布局分为四个大类 : 盒子布局:QBoxLayout 网格布局:QGridLayout 表单布局&am…...
shell脚本--常见案例
1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件: 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...
【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)
骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术,它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton):由层级结构的骨头组成,类似于人体骨骼蒙皮 (Mesh Skinning):将模型网格顶点绑定到骨骼上,使骨骼移动…...
3403. 从盒子中找出字典序最大的字符串 I
3403. 从盒子中找出字典序最大的字符串 I 题目链接:3403. 从盒子中找出字典序最大的字符串 I 代码如下: class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...
pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)
目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关࿰…...
CSS | transition 和 transform的用处和区别
省流总结: transform用于变换/变形,transition是动画控制器 transform 用来对元素进行变形,常见的操作如下,它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...
Golang——9、反射和文件操作
反射和文件操作 1、反射1.1、reflect.TypeOf()获取任意值的类型对象1.2、reflect.ValueOf()1.3、结构体反射 2、文件操作2.1、os.Open()打开文件2.2、方式一:使用Read()读取文件2.3、方式二:bufio读取文件2.4、方式三:os.ReadFile读取2.5、写…...
HubSpot推出与ChatGPT的深度集成引发兴奋与担忧
上周三,HubSpot宣布已构建与ChatGPT的深度集成,这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋,但同时也存在一些关于数据安全的担忧。 许多网络声音声称,这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...
【实施指南】Android客户端HTTPS双向认证实施指南
🔐 一、所需准备材料 证书文件(6类核心文件) 类型 格式 作用 Android端要求 CA根证书 .crt/.pem 验证服务器/客户端证书合法性 需预置到Android信任库 服务器证书 .crt 服务器身份证明 客户端需持有以验证服务器 客户端证书 .crt 客户端身份…...
Netty自定义协议解析
目录 自定义协议设计 实现消息解码器 实现消息编码器 自定义消息对象 配置ChannelPipeline Netty提供了强大的编解码器抽象基类,这些基类能够帮助开发者快速实现自定义协议的解析。 自定义协议设计 在实现自定义协议解析之前,需要明确协议的具体格式。例如,一个简单的…...
Ray框架:分布式AI训练与调参实践
Ray框架:分布式AI训练与调参实践 系统化学习人工智能网站(收藏):https://www.captainbed.cn/flu 文章目录 Ray框架:分布式AI训练与调参实践摘要引言框架架构解析1. 核心组件设计2. 关键技术实现2.1 动态资源调度2.2 …...

