LeedCode刷题—双指针问题

顾得泉：个人主页

个人专栏：《Linux操作系统》  《C/C++》  《LeedCode刷题》

键盘敲烂，年薪百万！

双指针简介

       常见的双指针有两种形式，一种是对撞指针，一种是左右指针。

对撞指针:一般用于顺序结构中，也称左右指针。

       对撞指针从两端向中间移动。一个指针从最左端开始，另一个从最右端开始。然后逐渐往中间逼近。

       对撞指针的终止条件一般是两个指针相遇或者错开（也可能在循环内部找到拿果直接跳出循
环)，也就是:

       left == right(两个指针指向同一个位置)

       left > right(两个指针错开)

快慢指针:又称为龟兔赛跑算法，其基本思想就是使用两个移动速度不同的指针在数组或链表等序列结构上移动。

       这种方法对于处理环形链表或数组非常有用。

       其实不单单是环形链表或者是数组，如果我们要研究的问题出现循环往复的情况时，均可考虑使用快慢指针的思想。

       快慢指针的实现方式有很多种，最常用的—种就是:在一次循环中，每次让慢的指针向后移动一位，而快的指针往后移动两位，实现一快一慢。

一、移动零

题目链接：移动零

题目描述

       给定一个数组 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

解法

算法思路:

       在本题中，我们可以用一个cur 指针来扫描整个数组，另一个dest指针用来记录非零数序列的最后一个位置。根据cur在扫描的过程中，遇到的不同情况，分类处理，实现数组的划分。在cur遍历期间，使[0， dest]的元素全部都是非零元素，[dest + 1， cur – 1]的元素全是零。

算法流程:

       a.初始化 cur = 0(用来遍历数组)，dest = -1(指向非零元素序列的最后一个位置。因为刚开始我们不知道最后一个非零元素在什么位置，因此初始化为-1)

       b.cur依次往后遍历每个元素，遍历到的元素会有下面两种情况

       i.遇到的元素是0 ，cur直接++。因为我们的目标是让[dest + 1， cur – 1]内的元素全都是零，因此当cur遇到o的时候，直接++，就可以让 o_在cur – 1的位置上，从而在[dest + 1, cur – 1]内;

       ii.遇到的元素不是0，dest++，并且交换cur位置和dest位置的元素，之后让cur++，扫描下一个元素。

       因为dest指向的位置是非零元素区间的最后一个位置，如果扫描到一个新的非零元素，那么它的位置应该在dest +1的位置上，因此dest先自增1;

       dest++之后，指向的元素就是0元素（因为非零元素区间末尾的后一个元素就是0)因此可以交换到cur所处的位置上，实现[0，dest]的元素全部都是非零元素，[dest+ 1， cur – 1]的元素全是零

代码实现

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

二、复写零

题目链接：复写零

题目描述

       给你一个长度固定的整数数组 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

解法

算法思路:

       如果「从前向后」进行原地复写操作的话，由于/的出现会复写两次，导致没有复写的数「被覆盖掉」。因此我们选择「从后往前」的复写策略。

       但是「从后向前」复写的时候，我们需要找到「最后一个复写的数」，因此我们的大体流程分两步:

       i.先找到最后一个复写的数;

       ii.然后从后向前进行复写操作

算法流程:

a.初始化两个指针cur=0, dest = 0;

b.找到最后一个复写的数︰

     i. 当cur <n的时候，一直执行下面循环:

       判断cur位置的元素:

       如果是0的话，dest往后移动两位;。否则，dest往后移动一位

       判断dest时候已经到结束位置，如果结束就终止循环;

       如果没有结束，cur++，继续判断

c.判断dest是否越界到n的位置:

     i.如果越界，执行下面三步:

       1. n – 1位置的值修改成0;

       2. cur向移动一步;

       3. dest向前移动两步

d. 从cur位置开始往前遍历原数组，依次还原出复写后的结果数组:

     i.判断cur位置的值:

       1.如果是0 :dest以及dest – 1位置修改成0,dest -= 2

       2．如果非零:dest位置修改成0,dest -= 1 ;

     ii. cur–，复写下一个位置

代码实现

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

三、快乐数

题目链接：

题目描述

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

「快乐数」 定义为：

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

如果 n 是 快乐数 就返回 true ；不是，则返回 false 

示例 1：

输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

示例 2：

输入：n = 2
输出：false

提示：

• 1 <= n <= 231 - 1

解法

算法思路:

       根据上述的题目分析，我们可以知道;当重复执行的时候，数据会陷入到一个「循环」之中。而「快慢指针」有一个特性。就是在一个圆圈中，快指针总是会追上慢指针的，也就是说他们总会相遇在一个位置上。如果相遇位置的值是1，那么这个数一定是快乐数;如果相遇位置不是1的话，那么就不是快乐数。

补充知识:

       如何求一个数n每个位置上的数字的平方和

a.把数n每一位的数提取出来:

     循环迭代下面步骤:

        i.int t = n % 10提取个位;

        ii. n /= 10干掉个位;

       直到n的值变为0 ;

b.提取每一位的时候，用一个变量tmp记录这一位的平方与之前提取位数的平方和

       tmp = tmp + t * t

代码实现

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

结语：今日的刷题分享到这里就结束了，希望本篇文章的分享会对大家的学习带来些许帮助，如果大家有什么问题，欢迎大家在评论区留言~~~ 

代码007普通

打赏 收藏 海报 链接