双指针优质算法题集
目录
一、双指针算法介绍
这里的指针不是真的指针，是数组下标
常见两种双指针形式：
（1）、对撞指针：从两端向中间移动。⼀个指针从最左端开始，另⼀个从最右端开始，然后逐渐往中间逼近。对撞指针的终⽌条件⼀般是两个指针相遇或者错开。
（2）、快慢指针：⼜称为⻳兔赛跑算法，其基本思想就是使⽤两个移动速度不同的指针在数组或链表等序列结构上移动。这种⽅法对于处理环形链表或数组⾮常有⽤
快慢指针的实现⽅式有很多种，最常⽤的⼀种就是：
在⼀次循环中，每次让慢的指针向后移动⼀位，⽽快的指针往后移动两位，实现⼀快⼀慢。
二、移动0
1、题目链接
283. 移动零 - 力扣（LeetCode）
https://leetcode.cn/problems/move-zeroes/description/
2、题解
这类题通常被称为数组划分或者数组分块，如下：
分析：
（1）、两个指针dest和cur的作用：
cur：从左向右扫描数据，遍历数组；
dest：指向已处理的区间内，非零元素的最后一个位置；
（2）、三个区间：[0,dest] [dest+1,cur-1] [cur,n-1]
（3）、如何做到：
3、代码实现
（1）、初次实现：
class Solution { public: void moveZeroes(vector<int>& nums) { int cur = 0; int dest = -1; while(cur<nums.size()) { if(nums[cur] != 0) { dest++; swap(nums[dest],nums[cur]); } cur++; } } };
（2）、优化后的实现：
class Solution { public: void moveZeroes(vector<int>& nums) { for(int cur = 0,dest = -1;cur<nums.size();cur++) { if(nums[cur] != 0) { swap(nums[++dest],nums[cur]); } } } };
二、复写0
1、题目链接：
2、题解
该题可使用双指针解法：
先根据“异地操作”，即开辟一个新数组，两个数组上进行分析，然后优化成双指针下的“就地”操作。然后一定要多画图分析再进行写代码。
具体步骤可分为三步：先找到最后一个复写的数、处理边界情况、从后往前完成复写操作。
（1）、先找到最后一个复写的数：
该步骤也需要用双指针，指针cur起始值为0，指针dest起始值为-1，然后开始循环比较，如果cur指向的值等于0，则dest += 2，即向后走两步，反之如果不等于0，则dest++，即向后走一步。当dest走完原数组时，cur刚好指向最后一个需要复写的数。
//找最后一个复写的数 int dest = -1,cur = 0; int n = arr.size(); while(cur < n) { if(arr[cur] == 0) { dest += 2; } else { dest++; } if(dest >= n - 1)break; cur++; }（2）、处理边界情况：
在（1）的算法下有个漏洞，即若dest指针走到数组的倒数第二个数时，并且最后一个复写的数为0，那么dest向后走两步就会越界，此时需要进行单独处理，先将最后一个数写为0，然后将dest定位到cur位置，在进行第三步。
//处理边界情况,若进入，提前处理最后一个复写的数 if(dest == n) { dest--; arr[dest--] = 0; cur--; }（3）、从后往前完成复写操作：
前两步完成后就进入一个循环，然后判断cur处的值：若为0，则dest从后往前将两个位置写成0；若不为0，则dest从后往前复写一个位置的数。
//从后往前进行复写 while(cur >= 0) { if(arr[cur] == 0) { arr[dest--] = 0; arr[dest--] = 0; cur--; } else { arr[dest] = arr[cur]; dest--; cur--; } }
3、代码实现
void duplicateZeros(vector<int>& arr) { //找最后一个复写的数 int dest = -1,cur = 0; int n = arr.size(); while(cur < n) { if(arr[cur] == 0) { dest += 2; } else { dest++; } if(dest >= n - 1)break; cur++; } //处理边界情况,若进入，提前处理最后一个复写的数 if(dest == n) { dest--; arr[dest--] = 0; cur--; } //从后往前进行复写 while(cur >= 0) { if(arr[cur] == 0) { arr[dest--] = 0; arr[dest--] = 0; cur--; } else { arr[dest] = arr[cur]; dest--; cur--; } } }
原文地址：https://blog.csdn.net/hffh123/article/details/143199732
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！