【C++】双指针算法

风中的云彩

发布于 2025-03-04 09:00:48

2900

代码可运行

文章被收录于专栏：C/C++的自学之路C/C++的自学之路

运行总次数：0

代码可运行

我们还有更长的路要走，不过没关系，道路就是生活。

前言

这是我自己学习蓝桥杯算法的第一篇博客总结。后期我会继续把蓝桥杯算法学习笔记开源至博客上。

技巧

1. 双指针算法，但实际上是利用数组下标来充当指针，并不是直接使用指针。 2. cur指针(current)，扫描遍历指针，左边是已经扫描遍历的部分，中间及右边是还未扫描遍历的部分。 3. dest指针(destination)，分隔指针，左边是已经排好的序的部分，中间及右边是还未排序的部分。 4. 划分为三个区间：[0,dest-1]，[dest,cur-1]，[cur,n-1]。 5. 双指针算法分为两类：就地操作和异地操作。 6. 异地操作需要从新创建一个数组，但不用考虑覆盖的问题。 7. 双指针算法可以从前到后遍历，又可以从后到前遍历。

例题

1. leetcode-283题： 283. 移动零 - 力扣（LeetCode）

void moveZeroes(vector<int>& nums) 
{
     int cur=0,dest=0;
     while(cur<nums.size())
     {
         if(nums[cur]!=0)
         {
             swap(nums[cur],nums[dest]);
             cur++;
             dest++;
         }
         else
         {
              cur++;
         }
     }
}

2. leetcode-1089题： 1089. 复写零 - 力扣（LeetCode）

https://leetcode.cn/problems/duplicate-zeros/

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