首页 > 编程语言 >双指针算法专题(1)

双指针算法专题(1)

时间:2024-09-13 21:53:16浏览次数:12  
标签:arr 专题 cur int fast dest 算法 指针

找往期文章包括但不限于本期文章中不懂的知识点:

个人主页:我要学编程(ಥ_ಥ)-CSDN博客

所属专栏: 优选算法专题

目录

双指针算法的介绍 

283. 移动零

1089. 复写零

202. 快乐数

11.盛最多水的容器


双指针算法的介绍 

在正式做题之前,得先了解:什么是双指针? 

双指针一般是指两个不同的变量,它们分别指向数据的不同位置。这两个指针可以根据特定的问题需求以不同的方式移动和操作,从而实现高效的算法和数据处理。

先来了解一个最简单的双指针。

上面这种事最简单的方法,但是其有一个缺点:需要另外申请一份内存空间,也就是只能 “异地” 操作,如果想要在原地修改就做不到,因此,这里就引出了我们的双指针算法。

这里我们就可以得出一个结论:双指针算法可以将 “异地” 操作,转变为 “原地” 操作。

常见的双指针有两种:一种是对撞指针,也称为左右指针;另一种是快慢指针。

什么是对撞指针呢?对撞指针从两端向中间移动。一个指针从最左端开始,另一个从最右端开始,然后逐渐往中间逼近。对撞指针的终止条件一般是两个指针相遇或者错开(也可能在循环内部找到结果直接跳出循环),也就是:left == right(两个指针指向同一个位置)  left > right(两个指针错开)。其实就是 当 left >= right 时,循环就可以停止了。最常见的对撞指针就是我们前面学习的快速排序和二分查找算法。

什么是快慢指针呢?其又称为龟兔赛跑算法,其基本思想就是使用两个移动速度不同的指针在数组或链表等序列结构上移动。这种方法对于处理环形链表或数组非常有用。其实不单单是环形链表或者是数组,如果我们要研究的问题出现循环往复的情况时,均可考虑使用快慢指针的思想。
快慢指针的实现方式有很多种,最常用的一种就是:在一次循环中,每次让慢的指针向后移动一位,而快的指针往后移动两位,实现一快一慢。我们前面在原地删除值为 val 的元素的方法就类似于快慢指针,只不过我们没有设置指针的速度而已。

双指针算法对于数组分块的问题的处理是非常有效的。

下面我们就来实战一些题目: 

283. 移动零

题目:

给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

请注意 ,必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]输出: [1,3,12,0,0]

示例 2:

输入: nums = [0]输出: [0]

提示:

  • 1 <= nums.length <= 104
  • -231 <= nums[i] <= 231 - 1

思路: 

题目已经明确地告诉我们了,不能申请一个新的数组,只能原地进行修改。在做题之前,我们最好能画图。通过画图来揣摩出该用哪种算法来解决。

上面这种采用的是对撞指针,但很明显不行,因此我们就只能采用快慢指针。

理想是丰满的,现实是骨感的。上述情况虽然在画图时确实好解决,但是在实际编码时,会出现很多种不确定的情况。因此优化成这样:fast找非零元素,直接和slow进行交换。

有的小伙伴这里可能会有疑惑:slow万一也是非零数呢?它们一交换,不就会影响非零数的相对顺序吗?其实这种情况是不存在的,假设两种极端情况:

1、数组中全部是非零数,那么全部就只是自己和自己进行交换;

2、数组中全部是零,这就更不可能了,if 语句的进不去,咋交换呢? 

代码实现:

class Solution {
    public void moveZeroes(int[] nums) {
        for (int fast = 0, slow = 0; fast < nums.length; fast++) {
            // fast走到非零位置就进行交换,走到零位置什么也不处理,让其++即可
            if (nums[fast] != 0) {
                int temp = nums[fast];
                nums[fast] = nums[slow];
                nums[slow] = temp;
                slow++;
            }
        }
    }
}

总结:一次性做不到完美没关系,多试几次就好啦!算法就是在不断的犯错中学习进步的。 

1089. 复写零

题目:

给你一个长度固定的整数数组 arr ,请你将该数组中出现的每个零都复写一遍,并将其余的元素向右平移。

注意:请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改,不要从函数返回任何东西。

示例 1:

输入:arr = [1,0,2,3,0,4,5,0]
输出:[1,0,0,2,3,0,0,4]
解释:调用函数后,输入的数组将被修改为:[1,0,0,2,3,0,0,4]

示例 2:

输入:arr = [1,2,3]
输出:[1,2,3]
解释:调用函数后,输入的数组将被修改为:[1,2,3]

提示:

  • 1 <= arr.length <= 104
  • 0 <= arr[i] <= 9

思路:首先,想要的就是去遍历这个数组,遇到0就复写,否则就不作处理。如果是在另外一个数组上根据上面的做法可行,但是在一个数组里面的话,就会出现覆盖的情况。

原地修改的话,就是去遍历数组,但是直接从头开始遍历的话,肯定是不行的,因为会出现覆盖的情况,那我们就尝试着从后开始遍历。但问题来了:从那个位置开始呢?因为复写的问题,导致我们不能够正确的找到最后一个元素的位置,因此这里就得解决找到最后一个元素的问题。

找到最后一个元素之后,就从该位置开始往前遍历去往原数组中进行复写操作。

代码实现:

错误版本:

class Solution {
    public void duplicateZeros(int[] arr) {
        // 开始找最后一个位置
        int count = 0;
        int cur = 0;
        for (; cur < arr.length; cur++) {
            if (arr[cur] != 0) {
                count++;
            } else {
                count += 2;
            }
            if (count >= arr.length) { // 一次走两步,可能出现 > 的情况
                // 说明此时已经找到最后一个元素了
                break;
            }
        }
        int dest = arr.length-1;
        while (cur >= 0 && dest >= 0) {
            if (arr[cur] != 0) {
                // 复写一次
                arr[dest--] = arr[cur--];
            } else {
                // 得复写两次
                cur--;
                arr[dest--] = 0;
                if (dest < 0) { // 这里可能会出现越界的情况
                    break;
                }
                arr[dest--] = 0;
            }
        }
    }
}

上面的代码在大多数测试用例下都能正常通过,但是有一个特殊的测试用例要注意:

在这个测试用例中 cur 指向数组下标为5的地方,后续在进行复写的时候,会出现一种情况:dest 的位置出现在了 cur 的前方,也就导致了最后复写的结果全为0了。也就是 dest 指针走到 cur 指针的前方,覆盖了原来的值,致使出错。那为什么会出现这种情况呢?很简单,只有 dest 一次 走两步才会超过 cur 的位置,因此我们可以设置一下让 dest 最开始的位置只走一步,也就是值复写一次0即可。那么问题又来了:什么时候让 dest 在最开始的位置只走一步呢?仔细观察一下:是不是刚刚的这种情况是 count > arr.length 才出现的,而 count == arr.length 的时候是正常进行的。因此当 count > arr.length 时,就让两者都只走一步。其实这种情况(count > arr.length)也就是因为数组空间不足,不能够将那个多余的0给存起来,就导致了覆盖。因此我们也只是让这个dest 值走一步,另一步我们认为其在不存在的地方走完了即可。

正确版本:

class Solution {
    public void duplicateZeros(int[] arr) {
        // 开始找最后一个位置
        int count = 0;
        int cur = 0;
        for (; cur < arr.length; cur++) {
            if (arr[cur] != 0) {
                count++;
            } else {
                count += 2;
            }
            if (count >= arr.length) { // 一次走两步,可能出现 > 的情况
                // 说明此时已经找到最后一个元素了
                break;
            }
        }
        int dest = arr.length-1;
        if (count > arr.length) {
            // 减少 dest 移动的次数(和 cur 一样暂时只移动一次)
            arr[dest--] = arr[cur--];
        }
        while (cur >= 0 && dest >= 0) {
            if (arr[cur] != 0) {
                // 复写一次
                arr[dest--] = arr[cur--];
            } else {
                // 得复写两次
                cur--;
                arr[dest--] = 0;
                if (dest < 0) { // 这里可能会出现越界的情况
                    break;
                }
                arr[dest--] = 0;
            }
        }
    }
}

202. 快乐数

题目:

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为:

  • 对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。
  • 然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。
  • 如果这个过程 结果为 1,那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ;不是,则返回 false 。

示例 1:

输入:n = 19
输出:true
解释:
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

示例 2:

输入:n = 2
输出:false

提示:

  • 1 <= n <= 2^31 - 1

思路: 根据快乐数的定义,我们可以知道:在进行转换过程中只会出现两种情况:1、无限循环但结果并不为1;2、在转换过程中出现结果为1。其实第二种情况也是无限循环,只不过循环的结果一直是1而已。

因此可以总结出下面的规律:

这里的思路也就出来了:通过快慢指针找到环, 接着判断环的元素值是否为1即可。

代码实现:

class Solution {
    public boolean isHappy(int n) {
        // 通过快慢指针来进行判断环值是否为1
        int fast = n;
        int slow = n;
        // 注意得让它们先走,否则两者就还是相等的
        slow = waterFlower(slow);
        fast = waterFlower(fast);
        fast = waterFlower(fast);
        while (slow != fast) {
            // slow一次走一步,fast一次走两步
            slow = waterFlower(slow);
            fast = waterFlower(fast);
            fast = waterFlower(fast);
        }
        return slow == 1; // 看相遇的值是否为1,是1就是快乐树,否则就不是快乐数
    }

    private int waterFlower(int n) {
        // 先计算出n的位数
        int temp = n;
        int count = 0;
        while (temp != 0) {
            count++;
            temp /= 10;
        }
        int sum = 0;
        // 通过位数确定循环的次数
        for (; count != 0; count--) {
            sum += (int) Math.pow((n%10),2);
            n /= 10;
        }
        return sum;
    }
}

注意:这里去转换的方法是模拟 计算水仙花数 的方法写的,我们也可以直接通过计算每一位的值平方,然后再相加也可以。 

11.盛最多水的容器

题目: 

给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明:你不能倾斜容器。

示例 1:

输入:[1,8,6,2,5,4,8,3,7]
输出:49 
解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。

示例 2:

输入:height = [1,1]
输出:1

提示:

  • n == height.length
  • 2 <= n <= 105
  • 0 <= height[i] <= 104

思路:题目是让我们求最大盛水量,其实也就是最大的容积。对于这个的话,直接遍历去找最大容积即可。容积公式 = 容器之间的长度 * 容器的最小高度(容器可能不是高度相等的)。

代码实现:

错误版本:直接暴力枚举,双层循环遍历。

class Solution {
    错误解法:暴力枚举
    public int maxArea(int[] height) {     
        int max = 0;
        for (int i = 0; i < height.length; i++) {
            for (int j = i+1; j < height.length; j++) {
                // 计算最大值并更新
                int temp = (j-i) * (height[j] > height[i] ? height[i] : height[j]);
                if (temp > max) {
                    max = temp;
                }
            }
        }
        return max;
    }
}

很显然,上面这个代码的时间复杂度达到了O(N^2),会超出时间限制的。但是肯定是使用这种方式来计算的,只不过我们的时间复杂度过大,因此这里就得找到减少遍历次数的问题。我们可以尝试从数组的两头开始遍历,降低时间复杂度。

注意:

1、这里之所以不让left 和 right 同时往"后"遍历,是因为如果同时遍历的话,可能会漏掉最大值的情况(会有情况被漏掉)。 

2、每一次只移动最小的指针值,就保证了下一次的容积可能不会小于这次的。但如果移动最大值的话,容积就肯定小于这次了。因为 最小值没有变(容器高度),然后 两者之间的距离变小了,那么最终的结果也就变小了。

正确版本:使用对撞指针减少遍历的次数。

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

好啦!本期 双指针算法专题(1)的学习之旅就到此结束啦!我们下一期再一起学习吧!

标签:arr,专题,cur,int,fast,dest,算法,指针
From: https://blog.csdn.net/2301_80854132/article/details/141891723

相关文章

  • 【数据挖掘】分类算法
    目录一、分类算法概述二、分类算法优缺点和改进2.1 分类算法优点2.2分类算法缺点2.3 分类算法改进三、分类算法实现3.1 分类算法C语言实现3.2 分类算法JAVA实现3.3分类算法python实现四、分类算法应用五、分类算法发展趋势一、分类算法概述       ......
  • PC算法详解
    基于约束的方法(PC(Peter-Clark)算法)基于约束的方法大多数是在经验联合分布上测试条件独立性,来构造一张反映这些条件独立性的图。通常会有多个满足一组给定的条件独立性的图,所以基于约束的方法通常输出一个表示某个MEC(边缘计算)的图(例如,一个PAG)。最有名的算法是PC算法,从一......
  • 多目标优化算法求解36个多目标测试函数(ZDT1、ZDT2、ZDT3、ZDT4、ZDT6、DTLZ1-DTLZ9、W
    36个多目标测试函数(ZDT1、ZDT2、ZDT3、ZDT4、ZDT6、DTLZ1-DTLZ9、WFG1-WFG9、UF1-UF10、LSMOP1-LSMOP3)是专门为了测试和比较不同多目标优化算法的性能而设计的。下面是每个函数集的简要介绍:ZDT(Zitzler-Deb-Thiele)函数集:ZDT系列是一组经典的多目标优化测试函数,由EckartZit......
  • 重生之我在代码随想录刷算法第一天 | 704.二分查找、27.移除元素
    参考文献链接:代码随想录本人代码是Java版本的,如有别的版本需要请上代码随想录网站查看。704.二分查找力扣题目链接解题思路这道题明确规定了数组是有序并且不重复的,要在这样的数组中寻找一个给定值的位置不由得让我想起来以前的数学知识二分查找。所以很快确定了思路......
  • [独家原创]基于(开普勒)KOA-Transformer-LSTM多特征分类预测【24年新算法】 (多输入单
    [独家原创]基于(开普勒)KOA-Transformer-LSTM多特征分类预测【24年新算法】(多输入单输出)Matlab代码你先用你就是创新!!!(鳑鲏鱼)KOA优化的超参数为:隐藏层节点数、正则化系数、初始化学习率1.程序已经调试好,无需更改代码替换数据集即可运行!!!数据格式为excel!2.Transformer作为......
  • CSP-J 算法基础 快速排序
    文章目录前言分治思想快速排序具体例子步骤1:选择基准值步骤2:分区步骤3:递归排序左边部分`[3,1,7,0,2]`步骤4:递归排序`[1,0,2]`步骤5:合并左边部分步骤6:合并整个数组快速排序的步骤总结:快速排序的第二个例子初始状态第一步:分区第二步:递归排序右边部分`[10,......
  • A*算法.
    A算法*保证一定有解,不然算法不如dfs;无解会很慢,只能先写写去试试179.八数码在一个3×3的网格中,1∼8这8个数字和一个x恰好不重不漏地分布在这3×3的网格中。例如:123x46758在游戏过程中,可以把x与其上、下、左、右四个方向之一的数字交换(如果存在)。我们......
  • 代码随想录算法 - 二叉树3
    题目1513.找树左下角的值给定一个二叉树的根节点root,请找出该二叉树的最底层最左边节点的值。假设二叉树中至少有一个节点。示例1:输入:root=[2,1,3]输出:1示例2:输入:[1,2,3,4,null,5,6,null,null,7]输出:7提示:二叉树的节点个数的范围是[1,104]-......
  • 文心一言 VS 讯飞星火 VS chatgpt (346)-- 算法导论23.2 5题
    五、假定图中边的权重取值全部为整数,且在范围内。Prim算法最快能多快?如果边的权重取值范围在1到某个常数之间呢?如果要写代码,请用go语言。文心一言:Prim算法是一种用于寻找加权无向图的最小生成树的贪心算法。其时间复杂度主要取决于实现方式。在标准实现中,Prim算法通常使用优先队列(......
  • 行驶证识别算法以及在中科麒麟系统的离线部署
    行驶证作为车辆合法上路的证明文件,包含车辆的基本信息和车主的详细资料,是政府部门、保险公司、租赁公司以及交通管理系统中常用的文档。在日常业务操作中,快速、准确地录入行驶证信息对于提高工作效率、减少人工错误有着重要意义。然而,传统的手工输入过程不仅费时,还存在一定的错误......