当前位置：首页 > article >正文

【算法一周目】双指针（1）

article 2024/11/14 3:22:05

1.双指针介绍

2.移动零

解题思路

C++代码实现

3.复写零

解题思路

C++代码实现

4.快乐数

解题思路

C++代码实现

5.盛水最多的容器

解题思路

C++代码实现

1.双指针介绍

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

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

对撞指针从两端向中间移动。⼀个指针从最左端开始，另⼀个从最右端开始，然后逐渐往中间逼近。
对撞指针的终止条件⼀般是两个指针相遇或者错开（也可能在循环内部找到结果直接跳出循环），也就是：

left == right （两个指针指向同⼀个位置）；
left > right （两个指针错开）；

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

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

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

2.移动零

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

解题思路

这题我们使用双指针解决，需要一个cur指针和一个dest指针，将数组划分成3个区间，[0, dest]的元素全部是非0元素，[dest + 1, cur - 1]的元素全是0，[cur -1, n - 1]的元素是待处理的。

具体流程如下：

1.初始化cur = 0（用于遍历数组），dest = -1（指向非0元素的最后一个位置，由于刚开始我们不知道最后一个非0元素在什么位置，因此初始化为-1）

2.cur依次往后遍历每个元素。

当cur遇到0时，cur++
当cur遇到非0时，dest++，交换dest的位置与cur位置的值

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]);
            }
        }
    }
};

时间复杂度：O(n)

空间复杂度：O(1)

3.复写零

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

解题思路

因为数组的0需要复写2次，有可能会把后面的非0元素覆盖掉，所以从前往后复写是不可取的，所以我们采取从后往前复写。

具体过程如下：

1.找到最后一个需要复写的元素，这一步需要双指针来解决。

初始化两个指针cur = 0， dest = -1。
当cur的位置为0时，dest += 2；非0时，dest++。
判断dest是否大于等于n - 1（数组最后一个位置），若满足则退出循环。
cur++，继续循环，直到找到最后一个复写的元素。

2.处理越界情况，当dest == n时，说明cur在数组n - 2位置且元素是0，这时候就要特殊处理，dest--，将arr[dest]置0，dest--，cur--。

3.从后往前复写，将arr[cur]复写到arr[dest]，若arr[cur]为非0，复写一次，若arr[cur]为0，则复写两次，记得分情况更新cur和dest，直到复写结束。

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++;
            else
                dest += 2;
            
            if(dest >= n - 1) break;
            cur++;
        }                                                                                                                                                                  
        //2.处理越界情况
        if(dest == n)
        {
            dest--;
            arr[dest--] = 0;
            cur--;
        }

        //3.从后往前复写元素
        while(cur >= 0)
        {
            if(arr[cur])
            {
                arr[dest--] = arr[cur--];
            }
            else{
                arr[dest--] = 0;
                arr[dest--] = 0;
                cur--;
            }
        }
    }
};

时间复杂度：O(n)

空间复杂度：O(1)

4.快乐数

题目链接：202. 快乐数

题目描述：编写一个算法来判断一个数 n 是不是快乐数。

对于n = 2，2 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 -> 16，进入到循环了。

解题思路

为了方便分析，将“对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和”这一操作记为f操作。

由题目可知，当我们对一个数不断进行f操作时，最后一定会进入死循环，死循环也分为两种，第一种就是一直在1循环，是快乐数，第二种就是在历史数据中死循环，但始终变不到1。

由于两种情况只会出现一种，所以我们只需判断是否一直在1循环，就可知此数是不是快乐数。

证明

对于INT_MAX（2^31-1=2147483647），取一个更大的数9999999999，进行f操作后得到最大值810，可以得到f操作得到的值范围是[1, 810]
根据“鸽巢原理”，对一个数进行f操作811次后，必定进入循环。

对此，我们可以得知，无论是什么数，对其进行多次f操作后，必定会形成一个环，所以我们可以使用快慢指针来解决。

具体过程：

1.编写f操作的函数bitsum，将该数替换为它每个位置上的数字的平方和。

2 .初始化快慢指针，slow = n，fast = bitsum(n)。

3.当slow != fast时，slow向前走一步，fast先前走两步，直到循环结束。

4.判断slow是否等于1，若等于则该数是快乐数。

C++代码实现

class Solution {
public:

    int bitsum(int n)
    {
        int ret = 0;
        while(n)
        {
            ret += pow(n % 10, 2);
            n /= 10;
        }
        return ret;
    }

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

时间复杂度：O(log n) 在快慢指针法中，求平方和的时间复杂度为对数级别。

空间复杂度：O(1)

5.盛水最多的容器

题目链接：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。

解题思路

对于该题，我们很容易就想到使用暴力解法，用两个for循环暴力枚举能构成的所有容器，找出其中容积最大的值。

容器计算公式：设两个指针i，j，分别指向容器的最左端和最右端，此时容器的宽度为j - 1，由于容器的高度由较短的高度决定，可得容器公式。

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)，如果提交到leetcode上是会超时，所以我们要寻求最优的解法。

利用双指针来解决，具体过程如下：

1.使用两个指针left和right分别指向容器的左右两个端点，初始化left = 0， right = n - 1。

2.通过左边界height[leftt]和右边界height[right]计算出容器的体积v。

3.判断左右边界的大小情况，舍去小的边界，若左边界 < 右边界，left++，反之则right--。

4.通过重复上述过程，可以舍去大量不必要的枚举过程，直到left与right相遇，整个过程中更新出容器体积的最大值。

证明以上的第三点，为什么不用小的边界去枚举剩下的数，而是直接将其舍去？

C++代码实现

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

时间复杂度：O(n)

空间复杂度：O(1)

拜拜，下期再见😏

摸鱼ing😴✨🎞