【双指针】算法题（一）
【双指针】算法题（一）
前言：
本章只有两道算法题：移动零、复写零。
常见的双指针有两种形式，一种是对撞指针，一种是左右指针。
- **对撞指针：**一般用于顺序结构中，也称左右指针。
- 对撞指针从两端向中间移动。一个指针从最左端开始，另一个从最右端开始，然后逐渐往中间逼近。
- 对撞指针的终止条件一般是两个指针相遇或者错开（也可能在循环内部找到结果直接跳出循环），也就是：left==right(两个指针指向同一个位置)、left>right(两个指针错开)
2.**快慢指针：**基本思想就是使用两个移动速度不同的指针在数组或链表等序列结构上移动。（就不如链表使用的快慢指针，每次fast向后移动两步，slow向后移动一位，两个指针速度不同）
题目一：移动零
题目链接在这里，点击即可
题目描述：
算法分析：
- 先定义两个指针，cur 和 dest ,cur 用来遍历数组，dest用来记录数组的最后一个元素的位置。
- 先思考，本题要求在一个数组里面实现把零全部移动到数组的后面，cur 在遍历数组的时候，会遇到不同的情况：使[0, dest] 的元素全部都是非零元素， [dest + 1, cur - 1] 的 元素全是零。
算法流程：
- 定义两个指针，int cur=0（用于遍历数组）;int dest=-1(指向非零元素序列的最后⼀个位置。 因为刚开始我们不知道最后⼀个非零元素在什么位置，因此初始化为-1);cur不大于数组元素个数。
- 开始时，首先移动cur，若cur指向的元素的值为0，dest不变，cur继续向后移动；若cur指向的元素的值不为零，则dest向后移动一位，然后与cur指向的元素进行交换，然后cur再向后移动一位。
算法代码1（这是用for循环的）：
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int dest=-1;
for(int cur=0;cur<nums.size();cur++)
{
if(nums[cur])
{
swap(nums[++dest],nums[cur]);
}
}
}
};
算法代码2（这是用while循环的，思路跟上面一样，只是代码展现形式不一样，用while循环两个指针的起始位置可以是相同的）：
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int cur=0;
int dest=0;
while(cur<nums.size())
{
if(nums[cur])
{
swap(nums[dest],nums[cur]);
dest++;
}
cur++;
}
}
};
题目二：复写零
题目链接在这里
题目描述：
算法分析：
如果从前向后进行原地复写操作的话，由于0 的出现会复写两次，导致没有复写的数被覆盖掉。因此我们选择从后往前的复写策略。 但是从后向前复写的时候，我们需要找到最后一个复写的数，因此我们的大体流程分两步：
- 先找到最后一个复写的数
- 然后再从后向前复写0
算法流程：
- 先定义两个指针，int cur=0;int dest=0;
- 然后找到最后一个复写的数
- cur小于arr.size()，判断cur位置的值，用cur从前往后遍历，当cur遇到0，dest向后移动两位；当cur遇到不为0的数时，dest向后移动一位。
- 判断dest是否到达数组的最后一位，终止循环，若没有到达，则cur继续往后移动一位，继续判断。
- 判断dest是否越界（这里是考虑一种特殊的情况，当cur位置的是0的时候，dest位于数组的倒数第二位，再复写的时候有一个0是越界了的）
- 若dest越界，则让arr[arr.size()-1]=0;
- 然后让cur往前移动一位，dest往前移动两位，即cur–,dest-=2
- 最后从后往前遍历
- 如果cur位置的值为0，则arr[dest–]=0;arr[dest–]=0,（这步复写0，所以写两次arr[dest–]=0）;
- 如果cur位置的值不为0，则将arr[cur–]值赋给arr[dest–]
代码实现：
class Solution {
public:
void duplicateZeros(vector<int>& arr) {
int cur=0;
int dest=-1;
while(cur<arr.size())
{
if(arr[cur]==0)
{
dest+=2;
}
else
{
dest++;
}
if(dest>=arr.size()-1)
{
break;
}
cur++;
}
if(dest==arr.size())
{
arr[arr.size()-1]=0;
cur--;
dest-=2;
}
while(cur>=0)
{
if(arr[cur]==0)
{
arr[dest--]=0;
arr[dest--]=0;
cur--;
}
else
{
arr[dest--]=arr[cur--];
}
}
}
};