【算法】双指针

1、移动零

1.1 题目解析

可以发现,这道题的本质就是通过某一个标准,将数组划分成不同区间(数组划分、数组分块),此时可以用到双指针算法

1.2 算法原理讲解

1.3 代码实现

class Solution {
public:void moveZeroes(vector<int>& nums) {for(int cur = 0,dest = -1;cur<nums.size();cur++)if(nums[cur])swap(nums[++dest],nums[cur]);}
};

2、复写零 

2.1 解法一

利用顺序表,可以定义一个指针cur遍历数组的前n-1个元素,当cur指向的元素是0时,将cur后面所有元素都向后移动一位,在cur+1的位置赋值为0,当cur指向的元素是非0时,cur++

class Solution {
public:void duplicateZeros(vector<int>& arr) {for(int cur = 0;cur<arr.size()-1;cur++){if(arr[cur]==0){int dest = arr.size()-2;while(dest>=cur){arr[dest+1]=arr[dest];dest--;}cur++;}}}
};

2.2 解法二

操作数组中元素的题,一般也会用到双指针

若可以异地操作

可以发现,此时最后一个复制的元素是4

此时当cur指向的值是非0时,dest赋值为cur,并向前移动一位,当cur指向的值是0时,dest将前面两个位置都赋值为0

但问题是,如何找到cur开始的位置呢?

总结:1. 先找到最后一个需要复写的数(双指针算法)

                先判断cur的值,决定dest一次走几步(注意起始时cur=0,dest=-1)

                dest走完后,判断一下是否结束,若未结束,cur++

          2. 从后向前完成复写操作(双指针法)

class Solution {
public:void duplicateZeros(vector<int>& arr) {int cur = 0,dest = -1,n = arr.size();for(cur = 0;cur<=n;cur++)//找到最后一个需要复写的数{if(arr[cur]){dest++;}else{dest+=2;}if(dest>=n-1) break;}if(dest==n)//若最后一个需要复写的数是0{arr[n-1] = 0;dest-=2;cur--;}while(cur>=0)//从后向前复写数组{if(arr[cur]){arr[dest--] = arr[cur--];}else{arr[dest--] = 0;arr[dest--] = 0;cur--;}}}
};

3、快乐数

3.1 题目解析

3.2 算法原理讲解

当是快乐数变成1后,再一直平方,任然会一直是1,所以可以将第一种情况也抽象成有环,这样子就可以定义快慢指针了(与链表中的快慢指针类似),因为两种情况都有环,所以快慢指针一定会相遇,只需要判断相遇时是否是1即可。

注意:这里的指针是用数来当指针

3.3 代码实现

class Solution {
public:int Square(int n){int sum = 0;while(n){int x = n%10;sum+=(x*x);n/=10;}return sum;}bool isHappy(int n) {int slow = n,fast = n;do{slow = Square(slow);fast = Square(fast);fast = Square(fast);}while(slow!=fast);return slow==1;}
};

4、盛最多水的容器

 4.1 算法原理讲解

这道题是可以暴力枚举的,两层循环,但是这样子会超时

正确的做法是定义一个指针在最左端,一个指针在最右端,计算出当前的体积,然后让高度小的那个往里面走,再次计算体积,与先前的体积取大的,直到两指针相遇。

4.2 代码实现

class Solution {
public:int maxArea(vector<int>& height) {int i = 0,j = height.size()-1,V = 0;while(i<j){V = height[i]<height[j]?max(V,(j-i)*height[i++]):max(V,(j-i)*height[j--]);}return V;}
};

5、有效三角形个数

由题意可知,这道题是允许出现重复的

当我们判断一个数组中的3项能否组成一个三角形时,若这个数组无序,则需要判断3次,但若这个数组有序,则只需要判断较小的2项之和是否大于第3项即可,并且这样做的时间复杂度也会更低

以暴力枚举为例,若判断3次,则3*N^3,排序+判断一次,则N^3+N*logN

5.1 代码原理讲解

这样使用双指针算法能让时间复杂度从暴力枚举减小一个量级

5.2 代码实现

class Solution {
public:int triangleNumber(vector<int>& nums) {sort(nums.begin(),nums.end());int n = nums.size(),ans = 0;for(int c = nums.size()-1;c>=2;c--){int a = 0,b = c-1;while(a < b){if(nums[a]+nums[b]>nums[c]){ans += b - a;b--;}else{a++;}}}return ans;}
};

6、查找总价格为目标值的两个商品

此题暴力枚举也是会超时的,可以将数组排成有序,然后利用第5题中的方法解决

class Solution {
public:vector<int> twoSum(vector<int>& price, int target) {sort(price.begin(),price.end());int left = 0,right = price.size() - 1;while(left < right){if(price[left] + price[right] > target)right--;else if(price[left] + price[right] < target)left++;else break;}vector<int> v{price[left],price[right]};return v;}
};

7、三数之和

这道题是不能出现重复的,所以要注意去重

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> vv;if(nums.size() < 3) return vv;sort(nums.begin(),nums.end());for(int i = nums.size() - 1;i>=2;){int left = 0,right = i - 1;while(left < right){if(nums[left] + nums[right] + nums[i] > 0)right--;else if(nums[left] + nums[right] + nums[i] < 0)left++;else{vv.push_back({nums[left],nums[right],nums[i]});// 匿名对象// 更新left和right,要去重int flag1 = nums[left++],flag2 = nums[right--];while(left < right && nums[left] == flag1) left++;while(left < right && nums[right] == flag2) right--;}}// 更新i,要去重int flag = nums[i--];while(i >= 2 && nums[i] == flag) i--;}return vv;}
};

8、四数之和

这道题是不能出现重复的,所以要注意去重

注意,这道题的数据范围较大,四个数相加会发生越界

此时超过了int的范围,前两个相加是没问题的,当第3个加上去的时候就出错了,此时可以让他们类型转换成long long,这样会发生整型提升

只要不是转换最后面的那个就可以,因为 + 是从左向右操作的

class Solution {
public:typedef long long ll;vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> vv;if(nums.size() < 3) return vv;sort(nums.begin(),nums.end());for(int i = nums.size() - 1;i>=3;){for(int j = i - 1;j>=2;){int left = 0,right = j - 1;while(left < right){if((ll)nums[left] + (ll)nums[right] + nums[j] + nums[i] > target)right--;else if((ll)nums[left] + (ll)nums[right] + nums[j] + nums[i] < target)left++;else{vv.push_back({nums[left],nums[right],nums[j],nums[i]});int flag1 = nums[left++] , flag2 = nums[right--];while(left < right && nums[left] == flag1) left++;while(left < right && nums[right] == flag2) right--;}}int flag = nums[j];while(j >= 2 && nums[j] == flag) j--;}int flag = nums[i];while(i >= 3 && nums[i] == flag) i--;}return vv;}
};

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

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

相关文章

强化学习算法

从上图看出&#xff0c;强化学习可以分成价值/策略、随机策略/确定策略、在线策略/离线策略、蒙特卡洛/时间差分这四个维度。这里分析了基础算法中除了在线策略/离线策略以外的其他维度。 &#xff08;一&#xff09;基础知识 一、基础概念 重点概念&#xff1a;状态S、动作A、…

【全网最全】2024电工杯数学建模A题21页初步参考论文+py代码+保奖思路等(后续会更新)

您的点赞收藏是我继续更新的最大动力&#xff01; 一定要点击如下的卡片链接&#xff0c;那是获取资料的入口&#xff01; 【全网最全】2024电工杯数学建模A题21页初步参考论文py代码保奖思路等&#xff08;后续会更新成品论文&#xff09;「首先来看看目前已有的资料&#x…

每周刷题第三期

个人主页&#xff1a;星纭-CSDN博客 系列文章专栏&#xff1a;Python 踏上取经路&#xff0c;比抵达灵山更重要&#xff01;一起努力一起进步&#xff01; 目录 题目一&#xff1a;环形链表 题目二&#xff1a;删除有序数组中的重复项 题目三&#xff1a;有效的括号 题…

HCIP【VRRP、MSTP、VLAN综合实验】

目录 一、实验拓扑图&#xff1a; ​编辑二、实验要求 三、实验思路 四、实验步骤 &#xff08;1&#xff09; eth-trunk技术配置 &#xff08;2&#xff09;vlan 技术配置 &#xff08;3&#xff09;配置SW1、SW2、AR1、ISP的IP地址 &#xff08;4&#xff09;在交换机…

Java+Spring+ MySQL + MyCat云HIS有哪些优势?智慧医疗云(HIS)低成本与安全保障的完美结合

JavaSpring MySQL MyCat云HIS有哪些优势&#xff1f;智慧医疗云(HIS)低成本与安全保障的完美结合 云HIS的优点包括节省成本、便捷高效、稳妥安全等。通过云HIS&#xff0c;医疗机构无需在本地建立机房、购买服务器和应用软件&#xff0c;降低了硬件和人力成本。同时&#xff0…

图片、视频画质增强变清晰工具分享(免费)

生活中可能会修一下模糊图片那么这就有一款用来修图片的管理工具&#xff0c;也有可能会修一下模糊的视频&#xff0c;在吾爱上有大佬开发了这么一款工具&#xff0c;免费的&#xff0c;不需要开任何VIP&#xff0c;我试了一下&#xff0c;好用&#xff0c;分享出来&#xff0c…

antd-vue a-tree 当两个不同一级下二级key相同的时候就会导致两个同时选择, 拿到node.parent的数据也会出问题, 解决办法

一、问题如下图&#xff1a; 当两个不同一级下二级key相同的时候就会导致两个同时选择&#xff0c; 同时拿到node.parent的数据也会出问题, 出现一下问题的原因是因为数据treeData 的key出现相同的了 然后如下图、因为我的查询条件 第二层是给 cloud , 第二层是给 relatedPool…

树洞陪聊系统源码/陪聊/陪玩/树洞/陪陪/公众号开发/源码交付/树洞系统源码

独立版本源码交付&#xff0c;自研UI和前后端代码 平台自带店员&#xff0c;无需自主招募&#xff0c;搭建直接运营 支持三方登录&#xff0c;官方支付、虎皮椒、易支付/码支付 支持首单体验、盲盒订单、指定下单等多个模式 支持钱包预充值、店员收藏、订单评价等功能 支持…

什么样的数据摆渡设备,可以满足不同网间数据的安全传输需求?

数据摆渡设备是用来在不同的网络环境间安全地传输数据的硬件或软件解决方案。它们通常用于确保在具有不同安全级别的网络&#xff08;如内网和外网&#xff09;之间进行数据交换时的安全性和合规性。以下是一些常见的数据摆渡设备和方法&#xff1a; 移动介质拷贝&#xff1a;使…

Python模块、包和异常处理

大家好&#xff0c;在当今软件开发领域&#xff0c;Python作为一种简洁、易读且功能强大的编程语言&#xff0c;被广泛应用于各种领域。作为一名测试开发工程师&#xff0c;熟练掌握Python的模块、包和异常处理是提高代码可维护性和错误处理能力的关键。本文将和大家一起探讨Py…

第七节 ConfigurationClassParser 源码分析

tips&#xff1a; ConfigurationClassParser 是 Springframework 中的重要类。 本章主要是源码理解&#xff0c;有难度和深度&#xff0c;也枯燥乏味&#xff0c;可以根据实际情况选择阅读。 位置&#xff1a;org.springframework.context.annotation.ConfigurationClassPars…

Java方法的重载

Java方法的重载 前言一、为什么要有重载代码示例问题 代码示例 二、重载的使用代码示例 三、重载的规则针对同一个类代码示例 前言 推荐一个网站给想要了解或者学习人工智能知识的读者&#xff0c;这个网站里内容讲解通俗易懂且风趣幽默&#xff0c;对我帮助很大。我想与大家分…

HTML5好看的通用网站模板源码

文章目录 1.设计来源1.1 主界面1.2 模板菜单1 界面1.3 模板菜单2 界面1.4 模板菜单3 界面1.5 下拉菜单1 界面1.6 下拉菜单2 界面1.7 模板菜单4 界面1.8 模板菜单5 界面1.9 界面底部 2.效果和源码2.1 动态效果2.2 源码目录2.3 源代码 源码下载 作者&#xff1a;xcLeigh 文章地址…

django-celery-beat自动调度异步任务

Celery是一个简单、灵活且可靠的分布式系统&#xff0c;专门用于处理大量消息的实时任务调度。它支持使用任务队列的方式在分布的机器、进程、线程上执行任务调度。Celery不仅支持异步任务&#xff08;如发送邮件、文件上传、图像处理等耗时操作&#xff09;&#xff0c;还支持…

深度学习之基于Tensorflow卷积神经网络(CNN)实现猫狗识别

欢迎大家点赞、收藏、关注、评论啦 &#xff0c;由于篇幅有限&#xff0c;只展示了部分核心代码。 文章目录 一项目简介 二、功能三、系统四. 总结 一项目简介 一、项目背景与意义 在人工智能和深度学习的热潮中&#xff0c;图像识别是一个备受关注的领域。猫狗识别作为图像识…

记录Python低代码开发框架zdppy_amcrud的开发过程

实现新增接口 基础代码 import env import mcrud import api import snowflakeenv.load(".env") db mcrud.new_env()table "user" columns ["name", "age"]async def add_user(req):data await api.req.get_json(req)values [d…

跟TED演讲学英文:Do schools kill creativity by Sir Ken Robinson

Do schools kill creativity? Link: https://www.ted.com/talks/sir_ken_robinson_do_schools_kill_creativity Speaker: Sir Ken Robinson Date: February 2006 文章目录 Do schools kill creativity?IntroductionVocabularySummaryTranscriptAfterword Introduction Sir…

[AI Google] 10个即将到来的Android生态系统更新

新的体验带来了更强的防盗保护、手表电池寿命优化&#xff0c;以及对电视、汽车等的娱乐功能改进。 昨天&#xff0c;我们分享了Android如何以人工智能为核心重新构想智能手机。今天&#xff0c;我们推出了Android 15的第二个测试版&#xff0c;并分享了更多我们改进操作系统的…

webSocket+Node+Js实现在线聊天(包含所有代码)

这篇文章主要介绍了如何使用 webSocket、Node 和 Js 实现在线聊天功能。 重要亮点 &#x1f4bb; 技术选型&#xff1a;使用 Node.js 搭建服务器&#xff0c;利用 Express 框架和 Socket.io 库实现 WebSocket 通信。 &#x1f4c4; 实现思路&#xff1a;通过建立数组存储聊天…

Linux 软件包管理器 yum的下载、功能介绍及使用

&#x1fa90;&#x1fa90;&#x1fa90;欢迎来到程序员餐厅&#x1f4ab;&#x1f4ab;&#x1f4ab; 主厨&#xff1a;邪王真眼 主厨的主页&#xff1a;Chef‘s blog 所属专栏&#xff1a;青果大战linux 总有光环在陨落&#xff0c;总有新星在闪烁 Linux下的三种软件安装方…