【C++ leetcode 】双指针问题

1. 183. 移动零

题目

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

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

 

题目链接 

. - 力扣（LeetCode）

画图 和 文字 分析

这种题，它有一种很明显的划分区间的行为（划分成 非0 和 0 的区间）

这里我们用双指针划分区域

非0：[0,dest]

0 : [dest + 1,cur - 1]

未处理 ：[cur , n - 1]

我们让 dest 一直指向最后一个 非0 的位置

cur遍历一遍数组，一直指向未处理区域的第一个位置

现在问题只有两个：

dest , cur 最开始指向哪 ？如果移动保证区域划分不会出问题 ?

对于第一个问题：

cur 因为要遍历一遍数组，所以它从 0 下标开始，而 dest开始没有区间，就从 -1 下标开始

对于第二个问题：

cur 在遍历数组的时候只会遇到两者情况，要么碰到 0 ,要么碰到 非0

如果碰到 0：cur++

如果碰到 非0 ：先 dest++ (此时dest所指的位置一定是 0 或者未处理的第一个位置)，再将此时 cur 和 dest 所指向的位置交换（保证了顺序不变），最后 cur++ (cur 又指向未处理区域)

代码

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

2. 1089 复写零

题目

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

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

 

题目链接 

. - 力扣（LeetCode）

画图 和 文字 分析

这道题考虑到时间复杂度和空间复杂度的情况下，我们决定用双指针来做

现在就是考虑两个指针的位置关系，首先，思考一下，如果两个指针都从下标 0 开始的话，很可能会发生把 0 把没有处理过的数据覆盖住了，所以换一种思路，两个指针从后开始覆盖

举例： 1 0 2 3 0 4 5 0

我们用 dest 指向最后一个要复写的位置

那么怎么找到最后一个要复写的位置呢？

我们可以知道，另一个指针cur 遇到 非0 跨一步，遇到 0 跨两步，而 dest 一直在跨一步，当大于等于总数组的长度时，dest 指向最后一个位置，这里我们让 cur 从下标为 -1 位置开始，dest 从下标为 0 的位置开始

如果我们要倒这覆盖，就按指针就从如图所示的位置开始

注意：

但是这里会碰到一种情况，cur 指针最后可能走两步，直接到下标为 n 的位置了，在倒退的时候，这种情况一定要单独处理，防止发生越界访问现象因为 dest 开始从 -1 开始找，类似是 int，而 vector 的size() 是 size_t 类型的，比较大小时，一定要记得发生类型转换

代码

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

 

本文链接：https://www.kjpai.cn/news/2024-03-27/149747.html，文章来源：网络cs，作者：言安琪，版权归作者所有，如需转载请注明来源和作者，否则将追究法律责任！