走进算法大门---双指针问题(一)

server/2024/12/2 16:46:14/

一.双指针算法介绍

概念:双指针是指在遍历数据结构(如数组、链表等)时使用两个指针,通过特定的移动规则来解决问题。这两个指针可以同向移动,也可以相向移动。

  • 同向双指针:常用于解决需要两个位置信息的问题。例如,在一个有序数组中查找两个数的和等于目标值的情况。一个指针从数组头部开始,另一个指针从当前指针的后面开始,通过不断调整指针位置来找到符合条件的数对。
  • 相向双指针:典型应用是在排序数组中查找满足某种条件的子数组。比如,在一个递增的数组中,一个指针从数组开头,一个指针从数组末尾,根据两个指针所指元素的和、差等关系,向中间移动指针,直到满足特定条件。
  • 优势:双指针算法可以降低时间复杂度,将原本需要嵌套循环的问题简化为单循环或更高效的遍历方式。例如,在某些情况下,可以将时间复杂度从n^2 降低到n 。

二.移动0

题目链接
在这里插入图片描述

class Solution {public void moveZeroes(int[] nums) {for(int cur = 0,dest = -1;cur<nums.length;cur++){if(nums[cur]!=0){dest++;int tmp = nums[cur];nums[cur]=nums[dest];nums[dest] =tmp;}}}
}

在这里插入图片描述

解题思路:主要把数组分为3个区间,已经处理过的非0区间,0元素区间和未处理的区间。

把数组分为3部分:

  • [0,dest] :处理过的非0元素
  • [dest+1,cur-1] 处理过的0元素
  • [cur,arry,length-1] 未被处理的元素

在这里插入图片描述

初始化时让cur 指向0元素位置,dest指向-1。刚开始所有元素都未处理,按照划分区间,未被处理的元素区间为【0,dest】,所以dest不能等于0,等于0说明第一个元素已经被处理过,边界不好区分,因此让dest=-1。
在这里插入图片描述

当cur的值等于0时,cur++;cur的值不等于0,让dest先走一步接着dest和cur 对应元素的值互相交换,每次都能保证数组的3个范围的划分。
在这里插入图片描述

在代码执行中,非零元素会依次覆盖零元素的位置,最终达到将所有零移动到数组末尾的目的。此方法的时间复杂度为 O(n),空间复杂度为 O(1),即为原地操作,不占用额外空间。如果暴力求解时间复杂度n方,双指针确实比暴力求解时间复杂度低。

三.快乐数

快乐数
在这里插入图片描述

class Solution {public int Num(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 slow = n;int fast = Num(n);while (fast!= slow) {slow = Num(slow);fast = Num(Num(fast));}return slow == 1;}
}

解法:前面学习链表的时候我们学过判断链表是否带环,让快指针一次走2步,慢指针一次走一步,如果存在环它们总能相遇。

以19为例是该树快乐数,通过对19的运算结果确实是1,说明是快乐数。
在这里插入图片描述

以2为例判断不是快乐数。4和20形成了一个环,说明不是快乐数。
在这里插入图片描述
把这个环想象成链表带环,让快指针在环里面一次走2步,慢指针一次走一步总会在环里面的某个位置相遇,相遇后跳出循环判断相遇点的值是否为1,如果是1说明是快乐数,不是1说明不是。

关于是否会陷入死循环
在这个算法中,实际上是利用了快慢指针的思想。对于一个正整数,如果它不是快乐数,那么在不断计算各位数字平方和的过程中,最终会陷入一个循环。
由于数字的范围是有限的(对于给定的正整数,经过有限次的数字平方和计算后,得到的结果一定在一个有限的范围内)。
假设存在一个非快乐数,在计算过程中会进入一个循环,那么快慢指针一定会在这个循环中相遇。因为快指针每次移动两步,慢指针每次移动一步,在一个有限的循环中,快指针必然会追上慢指针。
如果这个数是快乐数,那么最终会得到1,此时快慢指针也会相等(因为最终都会到达1这个结果)。

四.盛最多容器的水

盛最多容器的水
在这里插入图片描述
在这里插入图片描述

class Solution {public int maxArea(int[] height) {int left = 0;int right = height.length - 1;int v = 0;while (left < right) {int min = Math.min(height[left], height[right]);v = Math.max(v, min*(right - left));if (height[right] > height[left]) {left++;} else {right--;}}return v;}
}

在这里插入图片描述

解法:如果本题暴力求解去枚举算最大值比较大小,那么时间复杂度太高。

简单方法是去掉一些没必要的值。举个例子:算8和5的容积。该容器高度是5,宽度为(right-left)=6。因此v=5*6=30。

在这里插入图片描述
接着枚举该数组v的最大值那么宽度必然是减少的,因为求下一个容积会让left++,或者right–,那么(right-left)的值必然减少。因此宽度会减少。
在这里插入图片描述

对于v=宽度*高度,宽度减少要想体积增大必须高度增加。8和5的最小值是5,要想高度增加,那么right的值必然要大于5,所以可以看做舍弃5,让right减减。计算容器8和9容积
在这里插入图片描述

v=5*8=40,v上次的值是30,40大于30,所以v的值更新为40。求下一个容积也是同样的做法,要想v在宽度减少的情况下增大,那么高度的最小值一定要增大,也就是比较left和right的对应值的最小值,把这个最小值舍弃掉,在去求v。每次比较和上次v值的大小看是否更新v的值。
在这里插入图片描述

这道题考察了如何通过合理的指针移动来减少不必要的计算,双指针法的精髓在于每次有目的地舍弃一些不可能产生最大值的组合,从而将时间复杂度降至线性。在实际解题时,双指针法是一种非常高效的解法,特别适用于涉及到对区间或边界的遍历优化问题。


http://www.ppmy.cn/server/140585.html

相关文章

线性代数:Matrix2x2和Matrix3x3

今天整理自己的框架代码&#xff0c;将Matrix2x2和Matrix3x3给扩展了一下&#xff0c;发现网上unity数学计算相关挺少的&#xff0c;所以记录一下。 首先扩展Matrix2x2&#xff1a; using System.Collections; using System.Collections.Generic; using Unity.Mathemati…

释放专利力量:Patently 如何利用向量搜索和 NLP 简化协作

作者&#xff1a;来自 Elastic Matt Scourfield, Andrew Crothers, Brian Lambert 组织依靠知识产权 (IP) 来推动创新、保持竞争优势并创造收入来源。对于希望将新产品推向市场的公司来说&#xff0c;弄清楚谁拥有哪些专利是一项必不可少的能力。搜索数百万项专利可能既困难又耗…

C++ 的发展

目录 C 的发展总结&#xff1a;​编辑 1. C 的早期发展&#xff08;1979-1985&#xff09; 2. C 标准化过程&#xff08;1985-1998&#xff09; 3. C 标准演化&#xff08;2003-2011&#xff09; 4. C11&#xff08;2011年&#xff09; 5. C14&#xff08;2014年&#xf…

基于SpringBoot的“乐校园二手书交易管理系统”的设计与实现(源码+数据库+文档+PPT)

基于SpringBoot的“乐校园二手书交易管理系统”的设计与实现&#xff08;源码数据库文档PPT) 开发语言&#xff1a;Java 数据库&#xff1a;MySQL 技术&#xff1a;SpringBoot 工具&#xff1a;IDEA/Ecilpse、Navicat、Maven 系统展示 系统首页界面图 用户注册界面图 二手…

游戏网络(1)——网络发送间隔和滴答率等概念

与以下相混淆:滴答(Tick)、帧同步(Lockstep)、Timestep、滴答率(Tickrate)、Server Tick、客户端更新率(Client Update Rate)、刷新率、帧率、同步刻度、命令帧,让我们找出其中的关系。 如果你从事与游戏编程相关的工作,你会随处听到这些术语。有很多术语相关或含义…

打响反对人工智能的第一枪

序言&#xff1a;人工智能的讨论不能只有一片叫好的声音&#xff0c;一味的追捧反而可能隐藏巨大的危机。因此&#xff0c;必须有反对的声音&#xff0c;且越强烈越能激发深入思考。本篇文章的作者就以犀利的视角&#xff0c;漂亮地打响了反对人工智能应用的第一枪。 我以前一…

Python可视化绘图基础

Python绘图基础 【代码框2-19】——matplotlib绘图的一些基本操作 # 图2-2的绘制代码 # 导入相关模块 import numpy as np import matplotlib.pyplot as plt plt.rcParams[font.sans-serif] SimHei # 显示中文 plt.rcParams[axes.unicode_minus]False # 显示负号…

lua入门教程:lua函数

1. 定义函数 在 Lua 中&#xff0c;你可以使用 function 关键字来定义一个函数。以下是一个简单的例子&#xff1a; -- 定义一个名为 add 的函数&#xff0c;接受两个参数 a 和 b function add(a, b)return a b end你也可以使用匿名函数&#xff08;lambda 函数&#xff09;…