双指针(滑动窗口)-算法刷题

一.移动零

算法思想 :

设置两个指针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--;}}}

四.快乐数

算法思想: 

快慢指针的思想,因为这里数字最后都会循环,只要看快指针最后在环里与满指针相遇时所在的元素是否为一即可。

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;        }}}
};

五.盛最多水的容器

算法思想:

对撞指针,设置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;}
};

六 .有效三角形的个数

算法思想:

先将数组排序,利用单调性使用双指针解决 。如下图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;}
};

七.三数之和 

 算法思想:

先排序,利用单调性用双指针解决问题。即依旧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;}
};

八.长度最小的子数组(滑动窗口) 

算法解析:

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;}
};

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

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

相关文章

使用jupyter-Python进行模拟股票分析

tushare财经数据接口包 pip install tushare作用&#xff1a;提供相关指定的财经数据 需求&#xff1a;股票分析 使用tushare包获取某股票的历史行情数据 输出该股票所有收盘比开盘上涨3%以上的日期 输出该股票所有开盘比前日收盘跌幅超过2%的日期 假如我从2015年1月1日开…

人像抠图HumanSeg——基于大规模电话会议视频数据集的连接感知人像分割

前言 人像抠图将图像中的人物与背景进行像素级别的区分的技术。通过人像分割&#xff0c;可以实现诸如背景虚化、弹幕穿人等各种有趣的功能&#xff0c;为视频通话和影音观看提供更加优质和丰富的体验。由于广泛部署到Web、手机和边缘设备&#xff0c;肖像分割在兼顾分割精度的…

TinyEMU源码分析之虚拟机初始化

TinyEMU源码分析之虚拟机初始化 1 初始化结构参数2 配置RAM地址空间3 初始化设备4 拷贝BIOS和Kernel5 手动写入5条指令6 体验第一条指令的执行 本文属于《 TinyEMU模拟器基础系列教程》之一&#xff0c;欢迎查看其它文章。 本文中使用的代码&#xff0c;均为伪代码&#xff0c…

【LeetCode】--- 动态规划 集训(一)

目录 一、1137. 第 N 个泰波那契数1.1 题目解析1.2 状态转移方程1.3 解题代码 二、面试题 08.01. 三步问题2.1 题目解析2.2 状态转移方程2.3 解题代码 三、746. 使用最小花费爬楼梯3.1 题目解析3.2 状态转移方程3.3 解题代码 一、1137. 第 N 个泰波那契数 题目地址&#xff1a…

Python中的线程池与进程池:并行编程的高效选择【第145篇—并行编程】

&#x1f47d;发现宝藏 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。【点击进入巨牛的人工智能学习网站】。 Python中的线程池与进程池&#xff1a;并行编程的高效选择 在Python编程中&#xff0c;实现…

[Linux]条件变量:实现线程同步(什么是条件变量、为什么需要条件变量,怎么使用条件变量(接口)、例子,代码演示(生产者消费者模式))

目录 一、条件变量 1.什么是条件变量 故事说明 2、为什么需要使用条件变量 竞态条件 3.什么是同步 饥饿问题 二、条件变量的接口 1.pthread_cond_t 2.初始化&#xff08;pthread_cond_init&#xff09; 3.销毁&#xff08;pthread_cond_destroy&#xff09; 4.等待&…

联发科MT8797迅鲲1300T规格参数_MTK5G安卓核心板方案定制

联发科MT8797&#xff08;迅鲲1300T&#xff09;平台采用Arm Cortex-A78和Cortex-A55组成的八核架构CPU&#xff0c;以及Arm Mali-G77MC9九核GPU&#xff0c;集成了AI处理器MediaTek APU&#xff0c;支持5G Sub-6GHz全频段和5G双载波聚合,支持1.08亿像素拍照和多镜头组合,以及1…

《逆水寒》“公费追星”被骂上热搜,玩家为何如此抗拒剧游联动?

游戏行业最近真是风波不断。 《逆水寒》手游因为和武侠剧《莲花楼》深入联动而遭到玩家抵制&#xff0c;网易游戏测评总监被质疑“公费追星”&#xff0c;还波及到了成毅、陈都灵等多位演员。 尤其是《莲花楼》的男主角成毅&#xff0c;遭到大量《逆水寒》手游玩家的吐槽调侃…

Java项目:70 ssm小学生课外知识学习网站+vue

作者主页&#xff1a;源码空间codegym 简介&#xff1a;Java领域优质创作者、Java项目、学习资料、技术互助 文中获取源码 项目介绍 管理员&#xff1b;首页、个人中心、医护人员管理、科室管理、病人管理、病房管理、病人信息管理、病历管理、医嘱管理、手术安排管理、药品信…

Shell脚本学习-if循环

最小化的if语句 无实际用途 if [ ] ;then echo fi 脚本解释 if 判断 [ ] 里面的条件是否成立 后面跟then&#xff0c;代表条件成立 如果在一行则使用分号隔离&#xff08;;&#xff09; 如果不在一行使用则直接在下一行驶入then即可。 如果条件成立则输出echo 后面…

GEC6818——QT开发之两个UI界面切换与表格显示DHT11数据

GEC6818——QT开发之两个UI界面切换与表格显示DHT11数据 使用环境: ubantu16 QT5.7 开发板GEC6818 实现要求&#xff1a; 利用A53按键1、按键2与温湿度传感器完成QT界面动态显示温湿度记录&#xff0c;并指定温湿度记录超过指定范围&#xff0c;进行报警&#xff08;LED&#…

企业网络基础设施物理安全面临全新挑战

企业网络基础设施的物理安全是确保业务连续性和数据完整性的关键组成部分。随着技术的发展和环境的变化&#xff0c;这些基础设施面临着新的挑战。以下是一些主要的挑战和的解决方案 一、机房、仓库、档案馆物理安全事件频发的挑战&#xff1a; 1.电力安全事件&#xff1a;市…

HTML5+CSS3+JS小实例:创意罗盘时钟

实例:创意罗盘时钟 技术栈:HTML+CSS+JS 效果: 源码: 【HTML】 <!DOCTYPE html> <html lang="zh-CN"><head><meta charset="UTF-8"><meta name="viewport" content="width=device-width, initial-scale=…

优惠:阿里云4核16G服务器优惠价格26.52元1个月、149.00元半年

阿里云4核16G服务器优惠价格26.52元1个月、79.56元3个月、149.00元半年&#xff0c;配置为阿里云服务器ECS经济型e实例ecs.e-c1m4.xlarge&#xff0c;4核16G、按固定带宽 10Mbs、100GB ESSD Entry系统盘&#xff0c;活动链接 aliyunfuwuqi.com/go/aliyun 活动链接打开如下图&a…

网络安全实训Day5

写在前面 昨天忘更新了......讲的内容不多&#xff0c;就一个NAT。 之前记的NAT的内容&#xff1a;blog.csdn.net/Yisitelz/article/details/131840119 网络安全实训-网络工程 NAT 公网地址与私网地址 公网地址 可以在互联网上被寻址&#xff0c;由运营商统一分配全球唯一的I…

苹果手机更换国内IP地址的方法

在网络世界中&#xff0c;IP地址扮演着极为重要的角色&#xff0c;是互联网通信的基础。很多人在使用苹果手机时&#xff0c;有时候需要更换国内IP地址以获取更多网络资源或保护隐私。那么&#xff0c;是否可以更换国内ip地址&#xff1f;苹果手机更换国内ip地址的方法是怎样的…

阿兹特克帝国社会结构和政治农业和经济宗教和文化西班牙征服和遗产特诺奇提特兰(Tenochtitlán)地理位置和建筑社会和经济水上花园和农业西班牙征服巴斯克人

目录 阿兹特克帝国 社会结构和政治 农业和经济 宗教和文化 西班牙征服和遗产 特诺奇提特兰&#xff08;Tenochtitln&#xff09; 地理位置和建筑 社会和经济 水上花园和农业 西班牙征服 巴斯克人 语言 历史 文化和社会 政治和自治 1. 新南威尔士大学最新资讯 …

vue学习日记14:工程化开发脚手架Vue CLI

一、概念 二、安装 1.全局安装&查看版本 注意启动cmd输入命令 要以管理员运行哦 安装了一次就行以后不用再创建了 yarn global addvue/cli vue --version 显示了版本号即可 2.创建项目架子 创建项目的路径在哪 项目就在哪 项目名字不能用中文 vue create project-n…

Legacy|电脑Windows系统如何迁移到新安装的硬盘?系统迁移详细教程!

前言 前面讲了很多很多关于安装系统、重装系统的教程。但唯独没有讲到电脑换了新的硬盘之后&#xff0c;怎么把旧系统迁移到新的硬盘上。 今天小白就来跟各位小伙伴详细唠唠&#xff1a; 开始之前需要把系统迁移的条件准备好&#xff0c;意思就是在WinPE系统下&#xff0c;可…

子组件自定义事件$emit实现新页面弹窗关闭之后父界面刷新

文章目录 需求弹窗关闭之后父界面刷新展示最新数据 实现方案AVUE 大文本默认展开slotVUE 自定义事件实现 父界面刷新那么如何用呢? 思路核心代码1. 事件定义2. 帕斯卡命名组件且在父组件中引入以及注册3. 子组件被引用与父事件监听4.父组件回调函数 5.按钮弹窗事件 需求 弹窗…