Hoshiᅟᅠ     

Hoshiᅟᅠ     

C++ 双指针详解:基础题解与思维分析


前言

双指针方法是一种常见且高效的算法技巧,常用于数组和链表问题的优化解决。在这一篇博客中,我们将通过详细的讲解和题目解析,帮助大家理解双指针的基础用法及其应用场景。


第一章:对撞指针

1.1 移动零

题目链接283. 移动零
题目描述:给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

解题思路
  1. 初始化两个指针

    • cur:遍历整个数组。
    • dest:指向最后一个非零元素的位置,初始化为 -1。(因为不知道数组第一个元素是不是0
  2. 遍历数组

    • 如果 cur 指向非零元素,并且++dest!=cur,则将其放置在 dest + 1 的位置。
    • cur 遇到 0 时,不做任何操作,只移动 cur
  3. 结束条件

    • cur 遍历完整个数组后,dest + 1 后的所有位置自动归零,完成所需操作。
图解分析

假设数组初始为 [0, 1, 0, 3, 12]

  1. 初始状态

    • cur = 0dest = -1
    • 因为 nums[cur]0cur 右移,dest 保持不动。
  2. 步骤 1

    • cur = 1nums[cur] = 1
    • dest = -1,非零元素 1 应插入到 dest + 1 = 0 位置上。
    • 交换 nums[++dest]nums[cur],即 nums[0]nums[1],数组变为 [1, 0, 0, 3, 12]
  3. 步骤 2

    • cur = 3nums[cur] = 3
    • 此时 dest = 1
    • 3 插入 dest + 1 = 2 位置上,交换后数组变为 [1, 3, 0, 0, 12]
  4. 步骤 3

    • cur = 4nums[cur] = 12
    • 此时 dest = 2
    • 12 插入 dest + 1 = 3 位置上,交换后数组变为 [1, 3, 12, 0, 0]

步骤图解

C++代码实现
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        for (int cur = 0, dest = -1; cur < nums.size(); cur++) {
            if (nums[cur] != 0&&++dest!= cur) {
                swap(nums[dest], nums[cur]);
            }
        }
    }
};
易错点提示
  1. 指针初始化dest-1 开始,以便于将第一个非零元素移动到 0 位置。
  2. 交换顺序:应确保 ++destcur 指向的元素交换,否则会造成非零元素错位。
  3. 理解条件判断nums[cur] 为非零时才交换,避免多余的操作。
代码解读

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


1.2 复写零

题目链接1089. 复写零
题目描述:给定一个固定长度的整数数组 arr,在遇到每个零时,将其右移并插入一个零,同时保持数组长度不变。

解题思路
  1. 找出最后一个需要复写的元素:从头到尾遍历数组,计算复写位置。
  2. 逆序复写数组:从最后一个元素开始向前,将每个零复写到目标位置,同时不覆盖后续元素。
算法步骤
  1. 初始化指针

    • cur:用来找到被复写后数组的最后一个数在原来数组的位置,初始化为0
    • dest:用于模拟复写过程,初始为 -1
  2. 寻找最后一个需要复写的元素

    • 使用 cur 遍历数组:
      • 如果 arr[cur] 非零,则 dest++
      • 如果 arr[cur] 为零,则 dest += 2
    • dest 大于或等于 n - 1(数组最后一个位置),则退出循环。
  3. 处理越界情况

    • 如果 dest == n,表示需要在最后填入一个零。
    • 此时,将 arr[n - 1] 设置为零,并调整 cur--dest -= 2 以适应边界复写。
  4. 从后向前完成复写操作

    • 使用逆序遍历从 cur 开始复写至 dest,若 arr[cur] 为零则复写两次,否则只复写一次。
C++代码实现
class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int cur = 0, dest = -1, n = arr.size();
        
        // 1. 寻找最后一个需要复写的数
        while (cur < n) {
            if (arr[cur]) dest++;        // 非零元素,dest 右移一位
            else dest += 2;              // 遇零时,dest 右移两位
            if (dest >= n - 1) break;    // 越界则退出循环
            cur++;
        }
        
        // 2. 处理边界情况,dest == n 时需在末尾填零
        if (dest == n) {
            arr[n - 1] = 0;
            cur--;
            dest -= 2;
        }
        
        // 3. 从后向前复写元素
        while (cur >= 0) {
            if (arr[cur]) {
                arr[dest--] = arr[cur];  // 非零元素,复写到 dest 位置
            } else {
                arr[dest--] = 0;         // 遇到零时,连续写两次
                arr[dest--] = 0;
            }
            cur--;
        }
    }
};
  • 初始化 cur = 0dest = -1n = 8
  • 遍历数组,遇到零元素时 dest 向后移动两位,遇到非零元素时 dest 向后移动一位。目标是找到最后一个需要复写的元素位置 cur
int cur = 0, dest = -1, n = arr.size();
while (cur < n) {
    if (arr[cur]) dest++;   // 非零元素
    else dest += 2;         // 零元素,移动两位
    if (dest >= n - 1) break;
    cur++;
}

遍历示例:

  • cur = 0arr[0] = 1dest++,所以 dest = 0
  • cur = 1arr[1] = 0dest += 2,所以 dest = 2
  • 依此类推,最终 cur = 5dest = 7,在此位置结束循环。

在此时,cur5dest7。从这两个位置开始逆序复写,以避免前面的零覆盖其他元素:

具体操作解释:

  1. 开始cur = 5dest = 7,将 arr[5] 的值 4 复制到 arr[7]
  2. 遇到零cur = 4,在 arr[6]arr[5] 连续填入 0
  3. 复写非零元素cur = 3,将 arr[3] 的值 3 复制到 arr[4]
  4. 继续填充非零和零元素cur = 2cur = 1 分别填入 2 和两个 0
  5. 最终结果:通过逆序复写确保零元素不覆盖其他元素,得到 [1, 0, 0, 2, 3, 0, 0, 4]
易错点提示
  1. 目标位置初始化dest-1 开始,以保证cur准确定位复写后数组最后一个元素在原来数组的位置。
  2. 越界处理:若 dest 超出数组边界时,最后一个位置设为零,并调整 curdest
  3. 逆序复写逻辑:确保零元素复写两次、非零复写一次,保证整个过程的准确性。
代码复杂度
  • 时间复杂度:O(n),只需遍历两次。
  • 空间复杂度:O(1),仅使用少量额外变量。

1.3 盛最多水的容器

1. 题目链接

11. 盛最多水的容器

2. 题目描述

给定一个长度为 n 的整数数组 height,有 n 条垂线,第 i 条线的两个端点是 (i, 0)(i, height[i])
找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。

【优选算法篇】双指针的优雅舞步:C++ 算法世界的浪漫探索-LMLPHP

说明:你不能倾斜容器。

示例 1

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

算法思路

  • 枚举出所有可能构成的容器,找出其中容积最大的值。
  • 容器容积的计算方式:
    • 设指针 ij 分别指向容器的最左端和最右端,此时容器的宽度为 j - i
    • 由于容器的高度由两条边中较短的决定,因此容积的公式为:
      v = (j - i) * min(height[i], height[j])
      
  • 遍历所有可能的组合,计算每次的容积,并找出最大值。

代码实现

class Solution {
public:
    int maxArea(vector<int>& height) {
        int n = height.size();
        int ret = 0;
        // 两层 for 循环枚举出所有可能出现的情况
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // 计算容积,找出最大的那一个
                ret = max(ret, min(height[i], height[j]) * (j - i));
            }
        }
        return ret;
    }
};

复杂度分析

  • 时间复杂度O(n^2)。需要遍历所有的可能组合,计算每个组合的容积,因此时间复杂度为平方级别。
  • 空间复杂度O(1)。只使用了常数个变量存储结果和中间值。

缺点

解法二(对撞指针)

算法思路

  • 使用两个指针 leftright 分别指向容器的左右两个端点。
  • 容器的初始状态为 left 在最左侧,right 在最右侧。
  • 容积公式
    v = (right - left) * min(height[right], height[left])
    
  • 通过移动两个指针来寻找最大的容积:
    • 如果左边界小于右边界,则移动左边界 left++。因为固定左边界且继续移动右边界,只会使得容器宽度减小,而高度仍然由左边的短板决定,因此容积只能减小。
    • 同理,如果右边界小于左边界,则移动右边界 right--,以尝试找到更高的边界,从而可能获得更大的容积。
  • 重复以上过程,直到 leftright 相遇,整个过程中不断更新最大容积的值。

代码实现

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0, right = height.size() - 1, ret = 0;
        while (left < right) {
            int v = min(height[left], height[right]) * (right - left);
            ret = max(ret, v);
            // 移动指针
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return ret;
    }
};

复杂度分析

  • 时间复杂度O(n)。只需要遍历整个数组一次,两个指针分别从头和尾相向而行。
  • 空间复杂度O(1)。只使用了常数个变量存储结果和指针位置。

核心思想与证明

  • 双指针法的有效性:通过每次移动较短边界的方式,可以确保不会遗漏任何可能的最大容积的组合。因为容器的高度由两侧较短的一边决定,通过移动较短的那一边,我们尝试找到更高的边界,保持或增加容积。
  • 为什么移动短板?
    • 当左右边界不相等时,容器的高度取决于较短的一边。如果固定较短边界而移动较长边界,容器的高度不会增加,宽度还会减小,因此容积一定会减少。
    • 而如果移动较短的边,可能找到一个更高的边,从而在宽度减少的情况下保持或增加高度,从而有可能获得更大的容积。
易错点提示
  1. 指针移动逻辑

    • 在指针移动过程中,不是随机移动,而是根据较短边界的高度决定移动哪个指针。目的是通过增加高度的可能性来找到更大的容积。
  2. 边界条件的处理

    • 初始状态 left = 0right = height.size() - 1,要注意判断数组的长度不能为零,否则无法构成容器。
复杂度对比与结论
  • 暴力求解法:时间复杂度为 O(n^2),对于较大的输入会导致超时,适合小规模数据。
  • 对撞指针法:时间复杂度为 O(n),只需线性遍历,适合大规模输入,能够有效解决性能问题。
小结

通过这两种方法的对比,我们可以看到,暴力法虽然简单,但在性能上存在很大的不足,而通过双指针策略,我们能够有效地减少重复计算,找到问题的最优解。

第二章:快慢指针


2.1 复写零

题目链接

202. 快乐数

题目描述

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

快乐数定义

  • 对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。
  • 然后重复这个过程,直到这个数变为 1,或者进入无限循环但始终无法变为 1
  • 如果这个过程结果为 1,那么这个数就是快乐数。
  • 如果 n 是快乐数就返回 true;否则返回 false

示例 1

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

示例 2

  • 输入:n = 2
  • 输出:false
  • 解释:
    • 2 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 -> 16
    • 出现了重复的数字,因此进入了无限循环,不是快乐数。
题目分析

为了方便叙述,将“对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和”这一操作记为 x 操作

题目告诉我们,当我们不断重复 x 操作 时,计算一定会进入“死循环”,而“死循环”的方式有两种:

  • 情况一:不断循环到 1,即 1 -> 1 -> 1 -> 1...,这是“快乐数”。
  • 情况二:在某个历史数值中循环,始终变不到 1

由于上述两种情况只会出现一种,因此,只要我们能确定循环是在“情况一”还是“情况二”,就能判断该数是否是快乐数。

简单证明

  • 变化值范围:经过一次变化后的最大值为 9^2 * 10 = 810(即最大的情况是 9999999999(实际上这道题没有这么大),由鸽巢原理,这个值最终的范围在 [1, 810] 之间)。
  • 循环保证:根据“鸽巢原理”,一个数变化 811 次之后,必然会形成一个循环。
  • 因此,变化的过程最终会进入一个圈里,可以使用快慢指针来判断是否进入循环。
解法(快慢指针)

算法思路
根据题目分析,我们可以知道,当重复执行 x 操作 时,数值会陷入某种“循环”之中。而快慢指针有一个特性,就是在一个环中,快指针总是会追上慢指针,也就是说它们总会相遇在某个位置上。

  • 如果相遇的位置是 1,则这个数是快乐数;
  • 如果相遇的位置不是 1,则这个数不是快乐数。

补充知识:如何求一个数 n 每个位置上的数字的平方和:

  • 把数 n 每一位的数字提取出来,使用以下步骤:
    • 提取个位:int t = n % 10
    • 去掉个位:n /= 10
    • 重复上面的步骤,直到 n 的值为 0
  • 在提取每一位时,用一个变量 sum 记录平方和:sum += t * t
C++代码实现

以下是 C++ 的代码实现,使用快慢指针来解决该问题:

class Solution {
public:
    int bitSum(int n) { // 返回 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 = bitSum(n);
        while (slow != fast) {  // 使用快慢指针,直到二者相遇
            slow = bitSum(slow);                // 慢指针每次走一步
            fast = bitSum(bitSum(fast));        // 快指针每次走两步
        }
        return slow == 1;  // 判断相遇点是否为 1
    }
};
代码解析
  • bitSum 函数
    • 用于求一个数 n 的每位数字平方和。
    • 通过循环不断提取个位,计算平方和,直到 n0
  • isHappy 函数
    • 初始化两个指针 slowfast,分别为 nbitSum(n)
    • 使用 快慢指针 的方式来进行循环,slow 每次只走一步,而 fast 每次走两步。
    • 如果 slowfast 相遇,退出循环。
    • 最后判断是否相遇在 1 上,若是则返回 true,表示为快乐数,否则返回 false
易错点提示
  1. 快慢指针相遇判断

    • 需要注意的是,当 slowfast 相遇时,如果该值为 1,则为快乐数;如果不是 1,则表明进入了其他循环。
  2. 平方和计算函数的实现

    • 在实现 bitSum 函数时,需要注意提取个位后立即对其平方,并累加到总和中,最后在循环结束后返回结果。
复杂度分析
  • 时间复杂度O(log n)。在快慢指针法中,求平方和的时间复杂度为对数级。
  • 空间复杂度O(1)。没有使用额外的数据结构,只使用了固定数量的变量。

写在最后

以上就是关于【C++篇】虚境探微:多态的流动诗篇,解锁动态的艺术密码的内容啦,各位大佬有什么问题欢迎在评论区指正,或者私信我也是可以的啦,您的支持是我创作的最大动力!❤️

【优选算法篇】双指针的优雅舞步:C++ 算法世界的浪漫探索-LMLPHP

10-14 05:16