【c++算法篇】双指针（上）

🔥个人主页：Quitecoder

🔥专栏：算法笔记仓

朋友们大家好啊，本篇文章我们来到算法的双指针部分

1.移动零

题目链接：283.移动零
题目描述：

算法原理

这里运用的是数据分块的原理，我们将这个数组分为三个部分

两个指针的作用：

• cur：从左往右扫描数组，遍历数组
• dest：已处理的区间内，非零元素的最后一个位置

cur右边的部分是待处理的部分，左边是已经处理好的部分

处理好的区间，分为两个部分，左边为非零元素，右边全部为零，所以dest是一个分界线

所以划分为三个区间，[0,dest],[dest+1,cur-1],[cur,n-1],最左边全为非零元素，中间部分为0，右边为待处理元素，当cur指针移动到n为止时，区间划分完毕

代码如下：

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int dest = -1;  // 初始化 dest 为 -1，表示还没有遇到非零元素
        for (int cur = 0; cur < nums.size(); ++cur) {
            if (nums[cur] != 0)
               swap(nums[++dest],nums[cur]);
            }
        }
};

对于示例一：[0,1,0,3,12]，详细过程如下：

1. dest 初始化为 -1，表示当前还没有处理任何非零元素

2. 开始遍历数组 nums，使用变量 cur 从索引 0 开始：

   • cur = 0：nums[cur] 是 0。由于是零值，它不与 dest + 1 交换。dest 保持 -1。数组不变，仍然是 [0,1,0,3,12]

   • cur = 1：nums[cur] 是 1，非零。由于 dest = -1，先执行 ++dest （现在 dest 为 0），然后把 nums[cur] (1) 和 nums[dest] (0) 交换位置。数组变为 [1,0,0,3,12]。

   • cur = 2：nums[cur] 是 0。由于是零值，它不与 dest + 1 交换。dest 保持 0。数组不变

   • cur = 3：nums[cur] 是 3，非零。dest 递增为 1，然后将 nums[cur] (3) 和 nums[dest] (0) 交换位置。数组变为 [1,3,0,0,12]

   • cur = 4：nums[cur] 是 12，非零。dest 递增为 2，然后将 nums[cur] (12) 和 nums[dest] (0) 交换位置。数组变为 [1,3,12,0,0]

3. 完成遍历后，所有非零数 [1, 3, 12] 都位于数组的前端，并且它们的相对顺序保持不变。所有的零都被移动到了数组末尾 [0,0]

指针 dest 来跟踪最后一个找到的非零元素的位置，每次找到非零元素时，就把这个元素交换到 dest 现在的位置。这样一来，所有的零都会被替换到交换过非零元素位置的后面

2.复写零

题目链接：1089.复写零
题目描述：

遇到0写两遍，不能越界

算法原理

双指针算法，先根据异地操作，然后优化成双指针下的就地操作

我们正面复写的话会覆盖掉需要继续读取的数，所以这道题我们采用反向复写

我们第一步，首先找到最后一个要被复写的数

int dest = -1, cur = 0, n = arr.size();
        while (cur < n) {
            if (arr[cur] != 0) dest++;
            else dest += 2;
            if (dest >= n - 1) break;
            cur++;
        }

while 循环的目的是遍历数组 arr 来判断如果按照题目要求复写零（每个0都复写一次），最终数组中最后一个会被复写的元素是什么。这里，变量 dest 用来估计在复写零后数组可能会达到的索引位置，而变量 cur 是当前正在遍历的原数组中的元素的索引

具体逻辑如下：

1. 初始化两个变量：cur 和 dest。cur 从索引 0 开始向数组 arr 的末端移动，而 dest 初始化为 -1，以适应首次遇到的元素是零的情况

2. 遍历数组，逐项检查每个元素。

   • 如果当前元素 arr[cur] 是非零的，那么在复写过程中，该元素将向右移动一个位置，所以 dest 自增1（dest++）
   • 如果当前元素 arr[cur] 是零，那么在复写过程中，两个零将分别占据 dest 和 dest+1 的位置，因此 dest 需要增加2（dest += 2）

3. 如果 dest 的值达到或超过 n - 1，这更正地表示数组在复写零之后达到或超出它的最大容量索引 n - 1（因为数组索引从0开始，所以最大索引是 n-1）。这时，循环停止，并使我们知道最后一个将被复写的原始数组中的数字和复写零后它的索引位置

4. 在循环的最后，如果 dest 等于 n 或 n-1，则表明最后一个0恰好处在数组的最后一个位置或倒数第二个位置，并且它将被复写。如果 dest 大于 n，最后一个0将不会被复写。

这个逻辑假设所有0都将被复写一次，然而，如果数组的空间不够，某些0可能不会被复写。这就是代码中 dest 可能会超过数组实际长度的情况。最终，cur 还原为最后可复写的元素索引，这样我们就能在下一步的逻辑中从此索引处向前开始复写和移动元素。

对于上面某些零不能复写的情况：

if (dest == n) {
arr[n - 1] = 0;
cur--; dest -= 2;
}

处理一种特殊情况，即当最后一个被处理的元素正好是 0，并且这个 0 被加倍复写后，计算的 dest 索引正好等于数组 arr 的长度 n。由于数组索引是从 0 开始的，有效的最大索引实际上是 n-1。在这种情况下，最后一个 0 只能复写一次（因为在其后已经没有空间放置第二个复写的 0 了），所以数组最后一个元素必须是 0

这样处理以后的操作需要考虑的几个点是：

1. 由于 dest == n，所以 arr[n - 1] = 0; 这一行确保了数组的最后一个位置被设置为 0（符合复写操作的预期）。
2. cur 递减的原因是在逆向复写过程中我们会跳过这个 0，因为它已经被复写并放置在了正确的位置。
3. dest -= 2; 是因为 dest 原来是准备复写两个 0 的，但现在我们知道只能复写一个，所以我们递减两次 dest（将其回退到还未复写这个 0 的位置）。

处理完后，完成剩余的复写即可：

while (cur >= 0) {
       if (arr[cur] != 0) arr[dest--] = arr[cur--];
        else {
          arr[dest--] = 0;
          if (dest >= 0) {  
          arr[dest--] = 0;
          }
        cur--;
      }
}

需要注意几个细节：

1. 边界检查：在复写零的过程中，当 arr[cur] 是 0 时，该代码块将连续两次将 0 写入 dest 指向的位置和它前一个位置（dest - 1）。在进行第二次写入之前，需要检查 dest >= 0 以确保不会对数组进行越界写入

2. 双重减量：在处理零元素时，dest 指针需要减少两次，因为我们正在复写两个 0（前提是 dest >= 0），cur 只需要减少一次，因为我们只处理了一个 0。

3. 非零元素的移动：如果当前元素 arr[cur] 是非零元素，它只需要移动到 dest 指向的位置，并且 cur 和 dest 各自减一次。

4. 处理数组开头的0：对于数组开头连续的零，它们在复写后可能只有有限的空间，所以对索引 dest 进行边界检查就显得尤为重要。例如，数组 [0,0,1,...] 开头的两个零，当 dest 为 0 时，第二个零只会被复写一次

完整代码如下：

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

3.快乐数

题目链接：202.快乐数
题目描述：

对于2这个数，最后会进入循环

对于快乐数，最后也可以当做进入循环，不过循环都是1，这里与我们链表是否有环就思路相似了，当快慢指针相遇，判断是否为1即可

如果不是快乐数，它一定会进入一个循环

我们来系统地推导为什么一个不是快乐数的数最终会进入循环。这个推导包括分析数字变化的过程以及如何必然导致循环。下面是详细的步骤：

1. : 定义快乐数的操作
   快乐数的操作定义为：对一个正整数，重复执行将该数替换为其各位数字的平方和的过程。例如，对于数字 19:

   • (1^2 + 9^2 = 82)
   • 继续对 82 操作，(8^2 + 2^2 = 68)，以此类推。

2. : 分析结果的可能性
   在每一步操作中，一个数将被转换为其各位数字的平方和。因此，我们可以观察到：

   • 这一操作将数字转换为一个新的数，其最大值取决于原数字的位数。例如，四位数的最大平方和为 (9² * 4 = 324)。
   • 随着操作的进行，如果数字不立即收敛到1，它们会逐渐降低到一个更小的范围

3. : 有限状态和抽屉原理
   因为每步操作后的数字大小有上限，并且数字的总数是有限的（如最大999的平方和也只有243），所以可以推断状态空间（即可能的数字）是有限的。考虑到这个操作是重复执行的：

   • 根据抽屉原理（Pigeonhole Principle），如果你有更多的项（这里是操作次数）比抽屉（可能的数字结果）多，至少有一个抽屉必须包含不止一个项。这意味着至 少有一个数字会被重复
   • 一旦一个数字在操作过程中重复出现，后续的操作将重复之前的操作，从而形成一个循环。

所以我们先完成每一个位平方和的函数：

int bitsum(int n)
{
    int sum=0;
    while(n)
    {
       int t=n%10;
       sum+=t*t;
       n/=10;
    }
    return sum;
}

接着完成主要函数，slow一次走一步，fast一次走两步，直到相遇：

 bool isHappy(int n) {
    int slow=n;
    int fast=bitsum(slow);
    while(slow!=fast)
    {
        slow=bitsum(slow);
        fast=bitsum(bitsum(fast));
    }
    return slow==1;
}

最后判断相遇位置是否为1即可

4.盛水最多的容器

题目链接：11.盛水最多的容器
题目描述：

要解决这个问题，我们使用双指针的方法。一开始，我们将一个指针放在数组的最左边（即 left 指向索引 0），另一个指针放在数组的最右边（即 right 指向索引 n-1）。然后，我们计算由这两个指针指向的线和 x 轴构成的长方形的面积，并尝试找出能够获得更大面积的线对

具体地说，我们将指针向对方移动，并在每一步更新最大面积。由于容器的宽度随着指针的移动而减小，所以为了有可能增加面积，我们只移动指向较短线的指针（因为如果移动指向较长线的指针，面积只会减小或不变）。

实现 maxArea 函数，代码如下：

class Solution {
public:
    int maxArea(vector<int>& height) {
        int max_area = 0; // 存储最大面积
        int left = 0;     // 左指针
        int right = height.size() - 1; // 右指针

        while (left < right) {
            // 计算当前指针所围成的面积
            int current_area = (right - left) * min(height[left], height[right]);
            // 更新最大面积
            max_area = max(max_area, current_area);
            
            // 移动指向较短线的指针
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }

        return max_area; // 返回最大面积
    }
};

这个解法的时间复杂度为 O(n)，因为每个元素只被访问了一次。当 left 指针和 right 指针相遇时，所有可能的容器都已经检查过了。这是一个优化解法，它避免了 O(n²) 的暴力解法，后者需要检查所有可能的线对

本节内容到此结束！！感谢阅读！