我要成为算法高手-双指针篇

目录

  • 什么是双指针?
  • 问题1:移动零
  • 问题2:复写零
  • 问题3:快乐数
  • 问题4:盛最多水的容器
  • 问题5:有效三角形个数
  • 问题6:查找总价格和为目标值的两个商品(两数之和)
  • 问题7:三数之和
  • 问题8:四数之和
  • 总结

什么是双指针?

双指针算法是一种常见的解决问题的技巧,通常使用两个变量在链表或者数组中进行迭代、遍历,从而达到解决问题的目的。光说理论太抽象,我们来几道题目吧~~

问题1:移动零

力扣链接:移动零
在这里插入图片描述
分析一下题目要求: 将给定数组中所有的0移动到数组的末尾,也就是将数组分成两个区域,前半部分是非零元素,后半部分都是零,并且保持非零元素的相对顺序,如示例1,非零元素的顺序:1,3,12,处理之后非零元素的顺序也要是1,3,12,在这里插入图片描述

解题思路:
既然是双指针算法,那我们就定义两个"指针"咯,这里的"指针",我们是指数组下标
定义两个"指针",dest,cur,
dest:已经处理好的区间内,非0元素的最后一个位置
cur:从左往右遍历数组
dest初始为-1,表示刚开始还没非0元素,cur初始为0
在扫描的过程中,一直让数组保持下面这个状态就好了
在这里插入图片描述
图解:
在这里插入图片描述
代码实现:

public void moveZeroes(int[] nums) {//双指针:定义dest和cur,dest初始值为-1//dest的作用:非0元素的最后一个位置,也就是[0,dest]的区间是非0元素//cur的作用:从左往右扫描数组,遍历数组int dest = -1;for (int cur = 0; cur < nums.length; cur++) {if (nums[cur] != 0) {//cur遇到非0元素,先交换dest+1位置和cur位置的元素,再dest++,cur++int tmp = nums[dest + 1];nums[dest + 1] = nums[cur];nums[cur] = tmp;         dest++;}}
}

问题2:复写零

力扣链接:复写零
在这里插入图片描述
分析一下题目要求: 所谓复写,也就是让我们抄一遍数组的内容,遇到非零的直接抄这个数,遇到零抄两遍零,题目要求我们在原数组上进行操作,也就是说不能重新开辟一个新的数组
在这里插入图片描述
解题思路:
先找到最后一个需要被复写的数,然后从后往前进行复写,如果从前往后,后面的数会被覆盖掉。
如何找到最后一个被复写的数?还是利用双指针算法,如图
在这里插入图片描述
根据cur位置的值,判断dest向前走一步还是两步,走完判断dest是否到达结束位置(dest是否>=arr.length-1),如果dest没有到达结束位置,则让cur++。重复上面的步骤,当dest到达最后位置时,cur指向的就是最后一个被复写的数,要注意的是,dest的位置可能是arr.length-1,也可能是arr.length,如果dest=arr.length(如下图),需要处理这个边界问题,
在这里插入图片描述
处理办法:arr[arr.length - 1] = 0;dest -= 2;cur- -;
在这里插入图片描述
接下来就可以从后往前开始复写了,拿下图举例
在这里插入图片描述

代码实现:

    public void duplicateZeros(int[] arr) {int cur = 0;//指向最后一个位置int dest = -1;//dest指结果中,最后需要复写的位置,开始时不知道dest在哪,所以-1//先找到最后一个被复写的数while (cur < arr.length) {if (arr[cur] == 0) {dest += 2;} else {dest++;}if (dest >= arr.length - 1) {break;}cur++;}//边界情况,可能出现:最后要复写两个0,第二个0在arr.length这个位置if (dest == arr.length) {arr[arr.length - 1] = 0;dest -= 2;cur--;}while (cur >= 0) {if (arr[cur] != 0) {arr[dest] = arr[cur];dest--;} else {arr[dest--] = 0;arr[dest--] = 0;}cur--;}}

问题3:快乐数

力扣链接:快乐数
在这里插入图片描述
题目要求:题目让我们判断给定的数是不是快乐数,快乐数:每次都对这个数进行一次操作(让它的值替换为它每一位的数的平方之和),重复这个操作,判断最终结果是不是变成1或者无限循环变不到1
解题思路:有点类似之前写过的判断链表是否成环,题目说明了结果是1或者无限循环,但是其实1也是无限循环,1重复上述操作结果永远都是1,所以我们可以使用快慢指针的思想,当两个指针相遇时,判断两个指针指向的数是不是1即可(如果不熟悉判断链表是否成环,可以看这篇哦链表OJ)
在这里插入图片描述
代码实现:

//返回n的每一位的平方之和
public int func(int n) {int sum = 0;while (n != 0) {int t = n % 10;sum += t * t;n /= 10;}return sum;
}public boolean isHappy(int n) {int fast = func(n);int slow = n;while (fast != slow) {slow = func(slow);fast = func(func(fast));}return fast == 1;
}

问题4:盛最多水的容器

力扣链接:盛最多水的容器
在这里插入图片描述
题目要求: 给定了n条垂线,题目要找出两条线,与X轴构成的容器最多能盛水的容积
解题思路: 容积V = h*w,其中,h指高度,也就是两条线的最短的那条,w指宽度
在这里插入图片描述
如图:
在这里插入图片描述

代码实现

public int maxArea(int[] height) {//根据规律:向内枚举时,要么宽度肯定减小,但是高度只能是不变或减小(木桶效应)int left = 0;int right = height.length - 1;int maxV = 0;int V = 0;while (left < right) {V = (right - left) * Math.min(height[left], height[right]);if (V > maxV) {maxV = V;}//让高度小的移动,高度小也叫说明容积小,不符合要求if (height[left] <= height[right]) {left++;} else {right--;}}return maxV;
}

问题5:有效三角形个数

力扣链接:有效三角形个数
在这里插入图片描述
题目要求:
给定非负整数数组,在数组中挑3个能组成三角形数,求有几种挑法
解题思路:
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

代码实现:

    public int triangleNumber(int[] nums) {// 利用单调性,使用双指针算法int count = 0;int[] ret = nums;Arrays.sort(ret);// 先排个序int flg = ret.length - 1;//固定好flg,表示最大的数while (flg >= 2) {//固定好flg之后,再利用双指针int left = 0;int right = flg - 1;while (left < right) {if (ret[left] + ret[right] > ret[flg]) {count += (right - left);right--;} else {left++;}}flg--;}return count;}

问题6:查找总价格和为目标值的两个商品(两数之和)

力扣链接:查找总价格和为目标值的两个商品
在这里插入图片描述
题目要求: 给定数组和target(题目说明了已经排好序了),求数组中和为target的两个数,以数组的形式返回这两个数即可
解题思路: 定义双指针left,right分别指向第一个和最后一个元素,求两个指针指向的元素之和如果小于target,说明,要大一点!让left++,同理如果大于target,说明要小一点~~,让right–,当两个值等于target,此时可以返回了
代码实现:

    public int[] twoSum(int[] price, int target) {int[] ret = new int[2];//返回的数组//定义双指针left,rightint left = 0;int right = price.length - 1;while (left < right) {int sum = price[left] + price[right];if (sum < target) {left++;} else if (sum > target) {right--;} else {ret[0] = price[left];ret[1] = price[right];break;}}return ret;}

问题7:三数之和

力扣链接:三数之和
在这里插入图片描述
题目要求:
给定整数数组,判断是否存在相加和为0的三个数,这三个数的下标不能重复,也就是说这三个数下标是不一样的,返回所有的三元组,答案不能是重复的三元组
解题思路:
在这里插入图片描述
找到之后left和right继续移动,解决了不漏的问题,能够把所有的三元组都找出来,但是并没有满足题目要求:不能重复,解决办法就是:当找到两个数后,记录left和right的值,left和right跳过重复的数,另外,固定的数a(下标是flg)也要跳过重复的数
代码实现:

    public List<List<Integer>> threeSum(int[] nums) {Arrays.sort(nums);//先排序int flg = 0;//固定一个的数List<List<Integer>> ret = new ArrayList<>();// 返回的Listwhile (flg <= nums.length-2) {//双指针算法,left,rightint left = flg + 1;//左指针int right = nums.length - 1;//右指针int a = nums[flg];//双指针找目标值和为-a的两个数if(a>0) {//小优化,大于0了,后面的都是>0的数,肯定找不到-abreak;}//双指针算法,思路和求两数之和一样while (left < right) {if (nums[left] + nums[right] < (-a)) {left++;} else if (nums[left] + nums[right] > (-a)) {right--;} else {List<Integer> list = new ArrayList<>();list.add(a);list.add(nums[left]);list.add(nums[right]);ret.add(list);//// 找到结果之后,left,right跳过重复元素,避免越界int leftNumber = nums[left];int rightNumber = nums[right];while (nums[left] == leftNumber && left < nums.length - 1) {left++;}while (nums[right] == rightNumber && right > 0) {right--;}}}// flg也要跳过重复的元素,flg不能越界while (nums[flg] == a&&(flg <= nums.length-2)) {flg++;}}return ret;}

问题8:四数之和

力扣链接:四数之和
在这里插入图片描述
题目要求:
在给定数组中,找出4个和为target的数,这四个数的下标不能重复
解题思路:
明白了两数之和跟三数之和后,四数之和的思路就很简单了,先排序,固定一个数a(最左边或者最右边的数,都是一样的),然后在后面的区间按照三数之和的思路:固定一个数b,按照两数之和找出和为target-a-b的两个数
在这里插入图片描述
同样的,left、right、flg1、flg2也要跳过重复的数
代码实现:

    public List<List<Integer>> fourSum(int[] nums, int target) {Arrays.sort(nums);List<List<Integer>> ret = new ArrayList<>();// 返回的Listfor (int i = 0; i < nums.length; ) {//固定数afor (int j = i + 1; j < nums.length; ) {//固定数bint left = j + 1;int right = nums.length - 1;long aim = (long) target - (nums[i] + nums[j]);//a+bwhile (left < right) {if (nums[left] + nums[right] < aim) {left++;} else if (nums[left] + nums[right] > aim) {right--;} else {List<Integer> list = new ArrayList<>();list.add(nums[left]);list.add(nums[right]);list.add(nums[i]);list.add(nums[j]);ret.add(list);//处理细节,去重int leftNumber = nums[left];int rightNumber = nums[right];while (nums[left] == leftNumber && left < nums.length - 1) {left++;}while (nums[right] == rightNumber && right > 0) {right--;}}}j++;while ((j < nums.length - 2) && nums[j - 1] == nums[j]) {j++;}}i++;while ((i < nums.length - 3) && nums[i - 1] == nums[i]) {i++;}}return ret;

总结

遇到数组划分问题(按要求将数组分划分几个区域)或者如果数组存在单调性(有序的)时,我们可以考虑双指针算法~~

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

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

相关文章

德克萨斯大学奥斯汀分校自然语言处理硕士课程汉化版(第六周) - 预训练模型

预训练模型 1. 预训练模型介绍 1.1. ELMo1.2. GPT1.3. BERT 2. Seq2Seq 2.1. T52.2. BART 3. Tokenization 1. 预训练模型介绍 在预训练语言模型出现之前&#xff0c;统计语言模型&#xff08;如N-gram模型&#xff09;是主流方法。这些模型利用统计方法来预测文本中的下一个…

Docker系列.Docker Desktop中如何启用Kubernetes

Docker技术概论 Docker Desktop中如何启用Kubernetes - 文章信息 - Author: 李俊才 (jcLee95) Visit me at CSDN: https://jclee95.blog.csdn.netMy WebSite&#xff1a;http://thispage.tech/Email: 291148484163.com. Shenzhen ChinaAddress of this article:https://blog.…

【wiki知识库】06.文档管理接口的实现--SpringBoot后端部分

目录 一、&#x1f525;今日目标 二、&#x1f388;SpringBoot部分类的添加 1.调用MybatisGenerator 2.添加DocSaveParam 3.添加DocQueryVo 三、&#x1f686;后端新增接口 3.1添加DocController 3.1.1 /all/{ebokId} 3.1.2 /doc/save 3.1.3 /doc/delete/{idStr} …

嵌入式系统概述

嵌入式系统是为了特定应用而专门构建的计算机系统&#xff0c;其嵌入式软件的架构设计与嵌入式系统硬件组成紧密相关。 1.嵌入式系统发展历程 嵌入式系统的发展大致经历了五个阶段&#xff1a; 第一阶段&#xff1a;单片微型计算机&#xff08;SCM&#xff09;&#xff0c;及…

贷款业务——LPR、APR、IRR

文章目录 LPR&#xff08;Loan Prime Rate&#xff09;贷款市场报价利率APR&#xff08;Annual Percentage Rate&#xff09;年化百分比利率IRR&#xff08;Internal Rate of Return&#xff09;内部收益率 LPR、APR 和 IRR 是三个不同的金融术语&#xff0c;LPR 是一种市场利率…

干货分享!2024年Instagram营销必备插件

Instagram是营销人员常用的社交媒体平台&#xff0c;通过提升品牌知名度来推动业务增长。今天给大家分享一些超实用的Instagram营销插件&#xff0c;无论是下载图片视频&#xff0c;还是预先发布帖子&#xff0c;这些工具都可以是你的得力助手&#xff0c;让你的INS运营效率蹭蹭…

Unity2D游戏制作入门 | 12(之人物受伤和死亡的逻辑动画)

上期链接&#xff1a;Unity2D游戏制作入门 | 11(之人物属性及伤害计算)-CSDN博客 上期我们聊到了人物的自身属性和受伤时的计算&#xff0c;我们先给人物和野猪挂上属性和攻击属性的代码&#xff0c;然后通过触发器触发受伤的事件。物体&#xff08;人物也好敌人也行&#xff…

如何使用免费的 Instant Data Scraper快速抓取网页数据

Instant Data Scraper 是一款非常简单易用的网页数据爬虫工具&#xff0c;你不需要任何代码知识&#xff0c;只需要点几下鼠标&#xff0c;就可以把你想要的数据下载到表格里面。以下是详细的使用步骤&#xff1a; 第一步&#xff1a;安装 Instant Data Scraper 打开谷歌浏览…

基于蚁群算法的二维路径规划算法(matlab)

微♥关注“电击小子程高兴的MATLAB小屋”获得资料 一、理论基础 1、路径规划算法 路径规划算法是指在有障碍物的工作环境中寻找一条从起点到终点、无碰撞地绕过所有障碍物的运动路径。路径规划算法较多&#xff0c;大体上可分为全局路径规划算法和局部路径规划算法两大类。其…

js之简单轮播图

今天给大家封装一个简单的轮播图,可以点击下一张上一张以及自动轮播 <!DOCTYPE html> <html><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>走马…

catia零件装配中通过指南针移动零件

1 将零件导入进来后 2 把指南针移动到零件上 具体移动哪个可以通过模型树点击选中&#xff0c;选中那个就可以移动那个。 这种情况需要注意的是 需要双击选择要移动零件的父节点 如下图&#xff0c;Product2蓝色表示是激活的&#xff0c;这样才可以单击选中下面的零件后通过…

线程介绍及其Java如何用Thread 类创建线程和操作线程方法

目录 一、进程和线程1.1 进程特征 2.2 线程特征 2.3 区别 二、利用Thread类创建线程2.1 通过创建Thread子类&#xff0c;重写run()方法2.2 通过实现Runnable接口&#xff0c;重写run()方法2.3. Callable接口 FutureTask 创建线程2.3 三种方法区别1. 通过创建Thread子类&#x…

Interview preparation--RabbitMQ

AMQP AMQP(Advanced Message Queueing protocol). 高级消息队列协议&#xff0c;是进程之间床底一步新消息的网络协议AMQP工作原理如下&#xff1a; 发布者&#xff08;Publisher&#xff09;发布消息&#xff08;Message&#xff09;经过交换机&#xff08;Exchange&#xff…

Django 里实现表格内容上传

先看效果图&#xff1a; 当没有添加数据&#xff0c;就按 提交 键就会出现报错 下面是操作步骤 1. 先在 views.py 文件里做添加 # 在 views.py class AssetModelForm(forms.ModelForm):#newField forms.CharField()class Meta:model models.AssetSet fields [name, pri…

Nginx+Tomcat负载均衡、动静分离原理

目录 一.Nginx负载均衡 1.负载均衡概念 2.负载均衡原理 3.Nginx反向代理 3.1.反向代理概念 3.2.Nginx实现负载均衡的主要配置项 二.Nginx动静分离 1.什么是动静分离 2.动态页面与静态页面区别 3.动静分离原理 三.NginxTomcat负载均衡的实验设计 1.部署nginx负载均衡…

超详解——深入详解Python基础语法——基础篇

目录 1 .语句和变量 变量赋值示例&#xff1a; 打印变量的值&#xff1a; 2. 语句折行 反斜杠折行示例&#xff1a; 使用括号自动折行&#xff1a; 3. 缩进规范 缩进示例&#xff1a; 4. 多重赋值&#xff08;链式赋值&#xff09; 多重赋值的应用&#xff1a; 5 .多…

基数排序详解

目录 一、桶排序思想 1.1 什么是桶排序 1.2 桶排序的步骤 二、基数排序思想 2.1 什么是基数排序 2.2 实现方式 2.3 图解 三、代码思路 3.1 前置工作 3.2 映射 3.3 排序 四、C语言源码 一、桶排序思想 1.1 什么是桶排序 桶排序(Bucket sort)是一种排序算法&#xff…

Windows 系统下 JDK 1.8 与 17 版本的相互切换

目录 一、当前本机已安装的 JDK 版本&#xff1a;1.8 二、下载 JDK 17 三、修改系统配置&#xff0c;将 JDK 版本切换为 17 1、新建 JAVA17_HOME 2、编辑 Path 3、验证是否切换成功 4、之后想再切换成 JDK 1.8 一、当前本机已安装的 JDK 版本&#xff1a;1.8 二、下载 J…

flask基础知识1

目录 1.介绍 2.体验一下 3.配置参数&#xff1a; 4.路由和URL 1.路由 2.动态路由&#xff1a; 自定义转换器&#xff1a; 3.使用自定义转换器 5.url_for函数 6.request参数 7.处理响应&#xff1a; 1.重定向&#xff1a; 2.返回json数据&#xff1a; 3.返回模板&…

笨蛋学算法之LeetCodeHot100_1_两数之和(Java)

package com.lsy.leetcodehot100;public class _Hot1_两数之和 {//自写方法public static int[] twoSum1(int[] nums, int target) {//定义存放返回变量的数组int[] arr new int[2];//遍历整个数组for (int i 0; i < nums.length; i) {//从第二个数开始相加判断for (int j…