【C++ leetcode 】双指针问题

1. 183. 移动零

题目

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

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

 

题目链接 

. – 力扣（LeetCode）

画图 和 文字 分析

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

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

非0：[0,dest]

0 : [dest + 1,cur – 1]

未处理 ：[cur , n – 1]

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

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

现在问题只有两个：

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

对于第一个问题：

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 的位置开始

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

注意：

1. 但是这里会碰到一种情况，cur 指针最后可能走两步，直接到下标为 n 的位置了，在倒退的时候，这种情况一定要单独处理，防止发生越界访问现象
2. 因为 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--;
        }
    }
};