---

题目：

一· 移动零

1.题目链接：移动零

2. 分析

解法一：暴力求解

就是新开一个数组，大小与原数组大小一致，只要不是数字0就进行写入，若是数字0，统计出现的

次数，最后把所有非0元素写入之后，在写入0元素。

对于一些没有思路的，老铁，刚刚看到此题，或许都会这样

但是，题目要求空间复杂度必须是O（N），所以这个想法就 “pass ” 掉了。

 解法二：双指针算法

3. 原理

双指针：注意这里可不是真正意义上的指针：int*,char* ,float* …… 而是指向元素的下标

cur 指针：指向当前要扫描的元素

dest指针：指向已经被扫描过的元素

初始位置：dest  = 0； cur = 0 （表示从左向右依次进行判断是否为数字0）

 cur 指向元素为0，则++cur

cur 指向元素非0，交换 cur，dest对应位置的元素，同时++cur，++dest

 

 这里建议，咱还是先根据自己的理解，来编写程序，看看自己上手能力咋样哈~~~

 

4.OJ代码

class Solution {
public:void moveZeroes(vector<int>& nums){int dest = 0,cur = 0;int n = nums.size();for(;cur < n;++cur){if(nums[cur] ){swap(nums[dest++],nums[cur]);}}}
};

二· 复写零

1.题目链接：复写零

2. 分析

解法一：暴力求解

还是老样子：新开一个数组，对于非0元素进行“复写”一遍，0元素，“复写” 两遍，可以解决问题，

但是不符合要求：必须原地修改数组（也就是说时间 复杂度 O（N））

解法二：双指针

先模拟“异地”元素的移动：开一个与原始数组大小一样 的空间，对于非0元素进行“复写”一遍，0元

素，“复写” 两遍，我们可以找到新数组的最后一个元素，

假设我们知道“复写”之后的数组的最后一个元素，这个问题就简化了许多。此时就是对元素进行“复

写”的问题了：从前往后还是从后往前进行写入？？？

误区一：从前往后遍历

定义2个指针：cur = 0，dest = 0；

当cur 指向非0元素，arr[dest ]  = arr [ cur ] ,++dest,++cur

当cur 指向0元素:arr[dest ]  = arr [ cur ] ,++dest,  arr[dest ]  = arr [ cur ] ,++dest,++cur

 这样势必会造成数据覆盖，

所以说应该从后往前进行写入。

问题又来了：如何找到数组写入之后的最后一个元素呢？还是借助双指针

3. 原理

1）先模拟找到需写入数组的最后一个元素

图解：

双指针： dest = -1，cur = 0，cur 对应元素0，dest += 2,++cur 

注意：避免dest 越界，所以一个判读dest 是否 越界 dest >= n-1 

cur 对应非0元素：++dest，++cur

 结束之后：cur 位置对应的一定是写入数组的最后一个元素的位置

注意：结束之后dest 可能不是数组的有效位置

当cur 对应位置是元素0，会导致dest 越界，此时应该在dest 原有位置 前移动 2步，同时把最后一

个位置写入0即可

对于这个问题：可能会说直接让  dest = n-1 ，不就完了吗，反正最后dest  也是从数组的最后一个

位置开始“复写”

但是：可能恰好，cur 对应位置是元素0，写入数组的时候，就还只有一个位置，如果只是简单的

让dest = n- 1 ，对于这个临界情况就搞不了

临界情况判断：

 if (arr[cur] == 0 && dest > n-1)//注意这里后面的dest 的判断必须加上；也有可能复写的最后一个元素是0同时dest向后移动，刚刚到了n-1对应位置{arr[n - 1] = 0;dest -= 2;//注意永远指向下一个要填写的位置--cur;}

4.OJ代码

class Solution {
public:void duplicateZeros(vector<int>& arr)
{// 1:需要找到新数组最后一个元素，以方便复写从哪里开始int cur = 0, dest = -1;int n = arr.size();while (cur <= n - 1){if (arr[cur] != 0){++dest;}else{dest += 2;}if (dest >= n - 1){//对dest 需要判断是否越界break;}++cur;}//cur 一定是复写元素的最后一个，同时dest 永远指向的是要复写下一个元素位置// // 2:临界判断：可能结束的时候恰好cur遍历到原始数组元素为0//导致dest 越界//注意不能简单的让dest = n-1 ，这样就可能存在数据覆盖if (arr[cur] == 0 && dest > n-1)//注意这里后面的dest 的判断必须加上；也有可能复写的最后一个元素是0同时dest向后移动，刚刚到了n-1对应位置{arr[n - 1] = 0;dest -= 2;//注意永远指向下一个要填写的位置--cur;}// 3: 双指针：从后往前进行复写while (cur >= 0){if (arr[cur]){arr[dest--] = arr[cur--];}else{arr[dest--] = arr[cur];arr[dest--] = arr[cur--];}}}
};

三· 快乐数

1.题目链接：快乐数

2. 分析

对于数字n  ，就是拿到每一位的数字，并把每一位数字的平方进行相加求得平方之和，一直重复这

个过程，当变为1，就是快乐数，否则就不是快乐数。

 通过画图我们知道，对于一个数字是快乐数也好，不是快乐数也好，最终都会进入一个环，此时

问题就变成了判断是否为数字1 了。

不知道到这里，是否想起链表里面的一个OJ题目：判断链表是否有环？

对于这个题目感到陌生的友友们，可以看看之前我写的这个题解：判断链表是否有环

 所以对于这个问题的思路：快慢指针

3. 原理

定义2个指针：

slow 指针初始位置指向 n 所得的数字平方之和

fast 指针 初始位置指向 ：slow 指针初始位置指向 n 所得的数字平方之和的平方之和

最终2指针一定相遇，所以就只需要判断其中一个指针是否为1即可

4.OJ代码

class Solution {//求当前数字每一位的平方和int num_sum(int n){int sum = 0;while(n){int x = n%10;sum += (x*x);n /= 10;}return sum;}
public:bool isHappy(int n){//题型：判断链表是否有环//快慢指针(也不一定就是指针)int slow = n;int fast = num_sum(n);while(fast != slow){//fast 走2步//slow 走1步slow = num_sum(slow);fast = (num_sum(num_sum(fast)));}return fast == 1;}
};

总结：

对于快慢指针这一思想的应用关键在于：初始位置下标的确定；如何迭代；还是需要注意一些临界

情况判断以及特例