双指针算法（一）

一、移动零

题目链接

题目详情:

1.算法分析

这道题采用的算法原理是双指针算法：利用数组下标当做指针。

利用双指针算法的目的就是进行数组划分、数组分块。

我们先定义一个下标cur和一个下标dest。

两个指针的作用：

cur：从左至右的进行遍历数组。

dest：指向已经处理的区间的最后一个非零元素的位置。

这样区间就被分为三块：

已经处理过的区间的非零元素：[0, dest]

已经处理过的区间的为0的元素：[dest + 1, cur - 1]

未处理区间：[cur, size - 1]， size是数组长度

2.具体做法

在cur从左到右的遍历过程中：
1.如果cur所指向的元素为0，就cur++

2.如果cur所指元素不为0，就swap(dest + 1, cur) , dest++, cur++

3.代码实现

这道题目的代码实现也挺简单，首先让cur指向下标为0的位置， dest指向下标-1的位置，也就是数组第一个元素的前一个位置。

class Solution {
public:void moveZeroes(vector<int>& nums) {//先定义两个下下标，一个指向数组第一个元素的前一个位置//另一个指向数组的第一个元素的位置int dest = -1;int cur = 0;//通过循环遍历数组while(cur < nums.size()){//如果cur所指向的位置为0的话就++curif(nums[cur] == 0){++cur;}//不为零的话就停下，然后交换dest + 1所指向位置的元素以及cur所指向的元素//交换之后++dest,++curelse{swap(nums[dest + 1], nums[cur]);++dest;++cur;}}}
};

二、复写零

题目链接

题目详情：

1.算法分析

这道题和上道题的类型差不多，也是可以使用双指针算法解决的，但是这个题的难度要比上一个题大一些。

首先，我们看题目的要求，将数组中的每个零都复写一遍，将其余元素右移，复写后被挤出数组范围的元素就舍弃，对数组进行就地修改，也就是不能使用辅助数组。

我们先定义两个下标一个是cur指向数组第一个位置，也就是0下标，还有就是dest指向数组第一个元素的前一个位置，就是-1下标的位置。

2. 具体做法

1.先找到最后一个复写的数

使用cur进行遍历，如果cur所指位置不为0， dest++，否则dest += 2

2.处理边界情况

当初循环后dest == size时，说明最后一个需要复写的数是0， arr[size - 1] = 0, cur–, dest -= 2

3.从后往前对数组进行复写

1.cur所指位置不为0，复写一次， arr[dest] = arr[cur] , dest–, cur–

2.cur所指位置为0，复写两次, arr[dest] = arr[cur], arr[dest - 1] = arr[cur], dest -= 2, cur–

3.代码实现

class Solution {
public:void duplicateZeros(vector<int>& arr) {int dest = -1, cur = 0;int size = arr.size();//先找到最后一个需要复写的数while(dest < size){if(arr[cur] != 0){dest++;}else{dest += 2;}if(dest >= size - 1)break;cur++;}//处理边界情况if(dest == size){arr[size - 1] = 0;cur--;dest -= 2;}//从后往前进行复写while(cur >= 0){if(arr[cur] != 0){arr[dest] = arr[cur];dest--;}else{arr[dest] = arr[cur];arr[dest - 1] = arr[cur];dest -= 2;}cur--;}}
};

三、快乐数

题目链接

题目详情：

1.算法分析

我们先来看题目要求，题目取得很好快乐数，但是对于做题的人快乐不快乐就不一定了。

题目里说到，快乐数就是一直计算这个数的各位的平方和，如果这个数字到最后能够变为1，那么就快乐，否则不快乐。

这道题是比较简单的，也是可以使用我们的双指针算法来进行解决的。

2.具体做法

定义一个快慢指针，实际上就是一个int类型的数字，快指针一次走两步，慢指针一次走一步，我们在尝试计算平方和的时候可以发现，如果它的平方和走到为1 时，后面在怎么求也都是1，如果不是一出了循环那么这个数永远则始终变不到1。

我们先实现一个计算平方和的函数，然后，慢指针走一步就是调用一次这个函数，快指针一回调用两次这个函数。

3.代码实现

class Solution {
public:void duplicateZeros(vector<int>& arr) {int dest = -1, cur = 0;int size = arr.size();//先找到最后一个需要复写的数while(dest < size){if(arr[cur] != 0){dest++;}else{dest += 2;}if(dest >= size - 1)break;cur++;}//处理边界情况if(dest == size){arr[size - 1] = 0;cur--;dest -= 2;}//从后往前进行复写while(cur >= 0){if(arr[cur] != 0){arr[dest] = arr[cur];dest--;}else{arr[dest] = arr[cur];arr[dest - 1] = arr[cur];dest -= 2;}cur--;}}
};