双指针算法

文章目录

  • 双指针算法
  • leetcode题目


双指针算法

双指针算法可以实现对于时间复杂度降一维度,使得O(n2)的算法时间复杂度变为O(n)

指针类型

  1. 对撞指针
  2. 快慢指针

对撞指针

  • 一般是用于顺序结构中的,也可以称为左右指针,从两端向中间移动,最左、最右,向中间逐渐逼近。
  • 对撞指针的结束条件一般为left==right 或者 left>right

快慢指针

  • 基本思想为使用两个移动速度不同的指针在数组或者链表等序列结构上移动,比如在处理环形链表或者是数组时很有用
  • 只要是我们研究的问题涉及到循环往复的情况,就可以考虑使用快慢指针的思想
  • 快慢指针的实现方式有很多种,但是最为经典的是,在一次循环中,每一次让慢的指针移动一步,快的指针移动两步,如果成环(循环),那么两个指针会相遇

leetcode题目

题目链接:移动零
在这里插入图片描述

class Solution {
public:void moveZeroes(vector<int>& nums) {    //这是数组划分的题目,我们使用双指针的方式来解决//cur=0 dest=-1 dest指向的是最后一个不为0的数//移动cur,查找是否有nums[cur]!=0 那么 与nums[++dest] 交换,使得//[0,dest]  [dest+1,cur-1]  [cur,n-1]//数组分为上述三部分,第一部分为非零部分   第二部分为0部分,第三部分为未处理的部分//我们将非零部分,找到之后就放在当前非零数组的最后一个元素之后的位置,这样就可以实现分块for(int cur=0,dest=-1;cur<nums.size();cur++){if(nums[cur]){//如果不为0swap(nums[++dest],nums[cur]);}}}
};

为什么是swap(nums[++dest],nums[cur]),这是因为我们规定的是dest位置是已处理区域的最后一个非零元素,我们发现在未处理区域cur之后,发现非零元素,将++dest,得到最后一个元素的后一个位置,进行交换,自然实现了0(已处理的零区域)与nums[cur]的移动

题目描述:复写零

在这里插入图片描述

class Solution {
public:void duplicateZeros(vector<int>& arr) {//对于数组的元素进行处理,我们使用双指针//因为复写,遇到0要复写0,所以从前向后的双指针不行,我们使用从后向前指针,这样就不会造成数据被覆盖//从后向前进行双指针,我们首先要确定的是开始判断是否复写的起始位置//起始位置的确定,就是复写完毕之后的数组最后一个元素在原先数组中的下标位置//我们使用双指针进行判断,找到确定的位置//先找到最后一个位置//找到位置之后,可能会有种可能nums[dest]=0 所以我们将这种可能避免int cur=0,dest=-1;   //cur比dest多1,实际上就是先++cur,然后进行判断while(cur<arr.size()){if(arr[cur]){dest++;}else{dest+=2;}if(dest>=arr.size()-1){break;}cur++;}cout<<arr[cur]<<endl;//处理边界问题,dest可能大于arr.size()-1if(dest==arr.size()){arr[arr.size()-1] =0;dest-=2;cur--;}//开始复写 ,从后向前while(cur>=0){if(arr[cur]){//如果不为0arr[dest]=arr[cur];cur--;dest--;}else{//为0 复写arr[dest]=arr[cur];arr[--dest]=arr[cur];--dest;--cur;}}}
};

题目描述:快乐数

在这里插入图片描述

class Solution {
public://得到每一位数字的平方和int func(int n){int ans=0;while(n){ans+=(n%10)*(n%10);n=n/10;}return ans;}bool isHappy(int n) {//根据题意所知,不管如何都会形成一个循环//根据循环,我们知道之前判断循环链表的做法,快慢指针的形式//slow和fast都是指向经过平方之后的数字,来代替指针 //slow走一步平方一次,fast平方两次//实现平方的函数cout<<func(100)<<endl;//检验func函数int slow=n;int fast=n;while(1){//直到相等才停止slow=func(slow);fast=func(fast);fast=func(fast);if(slow==fast){break;}}if(slow==1){return true;}else{return false;}//return true;}
};

题目描述:盛最多水的容器

在这里插入图片描述

class Solution {
public:int maxArea(vector<int>& height) {//使用双指针的算法来解决//在两边设置指针,移动较小的哪一方指针,然后计算此时的体积,不断的移动,直到相遇int left=0,right=height.size()-1,ans=0;while(left<right){//先得到此时的体积int v=(right-left)*min(height[left],height[right]);ans=max(v,ans);if(height[right]>height[left]){left++;}else{right--;}}return ans;}
}

题目描述:有效三角形的个数

在这里插入图片描述

class Solution {
public:int triangleNumber(vector<int>& nums) {sort(nums.begin(),nums.end());int ans=0;for(int i=nums.size()-1;i;i--){int target=nums[i];int left=0,right=i-1;while(left<right){if(nums[left]+nums[right]>target){//满足三角形ans+=right-left;right--;//left++;}else{left++;}}}return ans;}
};

利用数组元素的单调性,先确定一个元素,然后使用双指针,判断当前三者是否符合三角形,如果符合,根据单调性,left左边的所有都符合,所以ans+=right-left,然后向左移动right,如果不符合,那么向右移动left,一直判断,一直ans+=right-left 直到left<right 更换下一位c,最后循环操作,返回ans

题目描述:和为s的两个数字

在这里插入图片描述

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {//因为是 递增的数组   //我们利用双指针算法来解决该问题   利用单调性进行优化vector<int> v;int left=0,right=nums.size()-1;while(left<right){if(nums[left]+nums[right]<target){left++;  //说明当前最大值加上最小值还是小于target}else if(nums[left]+nums[right]== target){v.push_back(nums[left]);v.push_back(nums[right]);return v;}else{right--;}}return v;}
};

题目概述:三数之和

在这里插入图片描述

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {sort(nums.begin(),nums.end());//进行排序,然使用双指针算法,先确定一个数字,然后移动另外两个指针进行加减vector<vector<int>> vv;for(int i=0;i<nums.size();){if(nums[i]>0) break;int left=i+1,right=nums.size()-1;while(left<right){int sum=nums[left]+nums[right];int target=-nums[i];if(sum==target){vector<int> v;v.push_back(nums[i]);v.push_back(nums[left]);v.push_back(nums[right]);//找到一次之后,对于相邻重复的元素进行跨越vv.push_back(v);//去重操作 left 和 rightleft++,right--;while(left<right && nums[left] == nums[left-1]) left++;while(left<right && nums[right] == nums[right+1]) right--;//防止越界}else if(sum>target){right--;}else {left++;}}//去重操作 ii++;while(i<nums.size() && nums[i] == nums[i-1]) i++;}return vv;}
};

题目描述:四数之和

在这里插入图片描述

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {//先固定一个数a,然后剩余三个数字用三数之和 的内容来解决sort(nums.begin(),nums.end());vector<vector<int>> vv;for(int i=0;i<nums.size();){int a=nums[i];for(int j=i+1;j<nums.size();){//三数之和的内容int num=target-a;int left=j+1,right=nums.size()-1;while(left<right){int sum=nums[left]+nums[right];long t=(long)num-nums[j];if(sum>t){right--;}else if(sum<t){left++;} else{vv.push_back({nums[i],nums[j],nums[left],nums[right]});//加入vector后,处理重复问题 left 和 rightleft++, right--;while(left<right && nums[left] ==  nums[left-1]) left++;while(left<right && nums[right] ==  nums[right+1]) right--;}}//去重处理 jj++;while(j<nums.size() && nums[j] == nums[j-1]) j++;}i++;while(i<nums.size() && nums[i] == nums[i-1]) i++; }return vv;}
};

总结:
双指针的使用场景有很多种,使用对撞指针还是快慢指针是根据题意分析的,如果成环我们就使用快慢指针,双指针的算法是根据暴力算法的优化得到的,通过省去不必要的迭代,来实现优化。

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

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

相关文章

【Mysql 连接报错】

文章目录 遇到问题查看用户信息修改加密规则成功连入mysql 遇到问题 socket: auth failed …/…/lualib/skynet/socketchannel.lua:482: errno:1251, msg:Client does not support authentication protocol requested by server; consider upgrading MySQL client,sqlstate:080…

MS Word表格宽度自适应

x.1 问题&#xff1a; 你的表格可能并没有占满整行&#xff0c;且右对齐&#xff0c;例如如下&#xff0c; x.2 解决方式 这个时候你想右对齐&#xff0c;你可以这么操作&#xff0c;点左上角的十字全选表格&#xff0c; 在布局里选择自动对齐&#xff0c; 对齐方式选择居中右…

信息与通信工程面试准备——数学知识|正态分布|中心极限定理

目录 正态分布 正态分布的参数 正态分布的第一个参数是均值 正态分布的第二个参数是标准差SD 所有正态分布的共同特征 标准正态分布&#xff1a;正态分布的特例 中心极限定理 理解定义 示例# 1 示例# 2 知道样本均值总是正态分布的实际含义是什么&#xff1f; 正态分…

设计HTML5列表和超链接

在网页中&#xff0c;大部分信息都是列表结构&#xff0c;如菜单栏、图文列表、分类导航、新闻列表、栏目列表等。HTML5定义了一套列表标签&#xff0c;通过列表结构实现对网页信息的合理排版。另外&#xff0c;网页中还包含大量超链接&#xff0c;通过它实现网页、位置的跳转&…

使用Python批量将Word文件转为PDF文件

说明&#xff1a;在使用Minio服务器时&#xff0c;无法对word文件预览&#xff0c;如果有需要的话&#xff0c;可以将word文件转为pdf文件&#xff0c;再存储到Minio中&#xff0c;本文介绍如何批量将word文件&#xff0c;转为pdf格式的文件&#xff1b; 安装库 首先&#xff…

DaVinci Resolve Studio 18 for Mac 达芬奇调色

DaVinci Resolve Studio 18是一款专业的视频编辑和调色软件&#xff0c;适用于电影、电视节目、广告等各种视觉媒体的制作。它具有完整的后期制作功能&#xff0c;包括剪辑、调色、特效、音频处理等。 以下是DaVinci Resolve Studio 18的主要特点&#xff1a; - 提供了全面的视…

一次Linux中的木马病毒解决经历(6379端口---newinit.sh)

病毒入侵解决方案 情景 最近几天一直CPU100%,也没有注意看到了以为正常的服务调用,直到腾讯给发了邮件警告说我的服务器正在入侵其他服务器的6379端口,我就是正常的使用不可能去入侵别人的系统的,这是违法的. 排查 既然入侵6379端口,就怀疑是通过我的Redis服务进入的我的系统…

Maven官网下载配置新仓库

1.Maven的下载 Maven的官网地址&#xff1a;Maven – Download Apache Maven 点击Download&#xff0c;查找 Files下的版本并下载如下图&#xff1a; 2.Maven的配置 自己在D盘或者E盘创建一个文件夹&#xff0c;作为本地仓库&#xff0c;存放项目依赖。 将下载好的zip文件进行解…

初识Redis

目录 认识Redis分布式系统Redis的特性Redis的应用场景Redis客户端Redis命令 认识Redis 上面一段话是官网给出的对Redis的介绍&#xff0c;in-memory data store表明Redis是在内存中存储数据的&#xff0c;这和我们接触的其他数据库就有很大的不同&#xff0c;比如MySQL&#xf…

02-前端基础第二天-HTML5

01-HTML标签&#xff08;下&#xff09;导读 目标&#xff1a; 能够书写表格能够写出无序列表能够写出3~4个常用input表单类型能够写出下拉列表表单能够使用表单元素实现注册页面能够独立查阅W3C文档 目录&#xff1a; 表格标签列表标签表单标签综合案例查阅文档 02-表格标…

OptaPlanner笔记1

1.1 什么是OptaPlanner 每个组织都面临规划问题&#xff1a;为产品或服务提供有限的受约束的资源&#xff08;员工、资产、时间和金钱&#xff09;。OptaPlanner用来优化这种规划&#xff0c;以实现用更少的资源来做更多的业务。 这被称为Constraint Satisfaction Programming…

【Java】Spring——Bean对象的作用域和生命周期

文章目录 前言一、引出Bean对象的作用域1.普通变量的作用域2.Bean对象的作用域 二、Bean对象的作用域1.Bean对象的6种作用域2.设置Bean对象的作用域 三、Bean对象的生命周期总结 前言 本人是一个普通程序猿!分享一点自己的见解,如果有错误的地方欢迎各位大佬莅临指导,如果你也…

Java实现微信小程序V3支付 (完整demo)

1. 微信小程序支付-开发者文档https://pay.weixin.qq.com/wiki/doc/apiv3/apis/chapter3_5_1.shtml 2. 导入依赖 <!--小程序支付 v3--> <dependency><groupId>com.github.wechatpay-apiv3</groupId><artifactId>wechatpay-apache-httpclient<…

Pytest和Unittest测试框架的区别?

如何区分这两者&#xff0c;很简单unittest作为官方的测试框架&#xff0c;在测试方面更加基础&#xff0c;并且可以再次基础上进行二次开发&#xff0c;同时在用法上格式会更加复杂&#xff1b;而pytest框架作为第三方框架&#xff0c;方便的地方就在于使用更加灵活&#xff0…

Vue2中根据权限添加动态路由

Vue2中根据权限添加动态路由 大概记录一下主要代码 1.根据后端返回的路由列表生成左侧菜单&#xff08;后端返回的数据结构中用id和pid来区别包含关系&#xff09; 大概结构如下&#xff1a; 2.前端需要处理成包含children的树形结构 //动态生成菜单 export const gener…

【Leetcode】102.二叉树的层序遍历

一、题目 1、题目描述 给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。 示例1: 输入:root = [3,9,20,null,null,15,7] 输出:[[3],[9,20],[15,7]]示例2: 输入:root = [1] 输出:[[1]]示例3: 输入:root = [] 输出:[]…

电力应用 | Intewell操作系统新疆特变项目应用案例

近日&#xff0c;科东软件Intewell操作系统在新疆特变项目成功应用&#xff0c;该方案保障了变电站的电力设备在高电压下稳定运行&#xff0c;实现变电站的智能化控制&#xff0c;极大程度上节省了人力、物力和财力资源&#xff1b;可实时监控电力设备的异常情况&#xff0c;及…

【系统架构】系统架构设计之数据同步策略

文章目录 一、介绍1.1、分布式系统中的数据同步定义1.2、为何数据同步如此关键1.3、数据同步策略简介 二、为什么需要数据同步2.1、提高系统可用性2.2、备份与灾难恢复2.3、提高性能2.4、考虑地理位置&#xff08;如使用CDN&#xff09; 三、同步备份3.1、定义和概述3.2、工作原…

Vue3 setup新特性简单应用

去官网学习→组合式 API&#xff1a;setup() | Vue.js 运行示例&#xff1a; 代码&#xff1a;App.vue <template><div class"home"><img alt"Vue logo" src"../assets/logo.png"><!-- msg 组件传递数据 --><Hell…

小象课堂在线授课教育系统

此项目包含后端全部代码&#xff0c;前端包括后台和web界面的源码&#xff0c;数据库用的mysql,可当作课设或者毕设&#xff0c;还可写入自己的简历中 web界面展示&#xff1a; 前端后台界面展示&#xff1a; 用户管理 课程管理 内容配置 订单管理 系统管理 系统监控