优先算法——复写零（双指针）
目录
题目：复写零
1. 题目解析
2. 算法原理
一. 先找到最后一个“复写”数
处理边界情况
二. 复写操作
3. 代码实现
题目：复写零
1. 题目解析
题目截图：
该题目要求的与移动零相似，都要在一个数组上进行操作，它还要要求的是，这个数组长度大小不会被改变，在原有的数组上遇到0就复写一遍，遇到非零就不用复写。
这道题直接上来就在一个数组上考虑情况稍微会困难一些，可以假设让它可以开辟额外一个数组（两个数组）来考虑，最后在结合双指针到一个数组上会好解答。
题目大致情况双数组的话是上图所示，接下来转化到一个数组上双指针操作。
2. 算法原理
上述的介绍，这道题也是用双指针算法，不过这种双指针算法是先根据“异地“操作（也就是在额外开辟的数组操作），然后优化成双指针下的”就地“操作（在当前数组操作，不额外开辟数组）。
融入一个数组上就是：
但是这出现了一个问题，下面cur就指向0了，遇0是要复写一遍的（也就是要写两遍）
此时，就造成数据被覆盖导致丢失数据了，所以顺序遍历数组操作还是有问题的，要解决此问题，可以考虑尝试逆序操作。
然后按照上面逻辑，遇到0就抄写两遍，遇到非零直接抄写一遍即可，再统一向后移动1位。
这样可以避免出现顺序时候后面未被复写的数据被覆盖的情况了。
大致思路如上面图所示，归纳一下：
一. 先找到最后一个“复写”数
这个也要用双指针算法来去寻找它，我们把dest定义为最后需要复写的位置（结果中数组最后一个位置），因此刚开始时，并不知道最后位置在哪，让dest指向-1；cur的作用：从前往后遍历数组，决定dest走1步还是2步。所以可以仅需要判断dest是否走向最后位置来判断是否找到最后要复写的数。
// 先找到最后一个要复写的数
int dest = -1; // 复写位置
int cur = 0; // 遍历数组
while (cur < arr.size()) {if (arr[cur] == 0) { //遇到0，dest移动两位dest += 2;}else {++dest;}if (dest >= arr.size() - 1) { //判断dest是否走向结尾break;}++cur;
}处理边界情况
也就是说，因为遇到0，dest要加2，这样的话会导致上图情况。越界时，一定是cur等于0导致的，所以就可以单独处理它。
//单独处理边界情况--cur走到最后要复写的数为0,dest复写就导致越界访问的情况
if (dest == arr.size()) {arr[arr.size() - 1] = 0;--cur;dest -= 2;
}总结：
- 先判断cur的值（是0或非0元素）
- 根据cur的值决定dest向后移动1步或2步。
- 先判断dest是否已经走到结束的位置
- 判断后，若没有结束，cur再向后移动1位
- 特殊情况，cur走到最后要复写的数为0，单独处理越界情况。
二. 复写操作
既然是逆序，那么就是要从后向前完成复写操作
注意：遇到0要多写一遍0
//从后向前复写while (dest >= 0) {if (arr[cur] == 0) {// 遇到0要记得复写两遍0arr[dest--] = 0;}arr[dest--] = arr[cur--];}3. 代码实现
题目链接
class Solution {
public:void duplicateZeros(vector<int>& arr) {// 先找到最后一个要复写的数int dest = -1; // 复写位置int cur = 0; // 遍历数组while (cur < arr.size()) {if (arr[cur] == 0) {dest += 2;} else {++dest;}if (dest >= arr.size() - 1) {break;}++cur;}// 从后往前复写// 还要单独处理边界情况--cur走到最后要复写的数为0,dest复写导致越界访问的情况if (dest == arr.size()) {arr[arr.size() - 1] = 0;--cur;dest -= 2;}while (dest >= 0) {if (arr[cur] == 0) {// 遇到0要记得复写两遍0arr[dest--] = 0;}arr[dest--] = arr[cur--];}}
};提交记录：
制作不易,若有不足之处或出问题的地方，请各位大佬多多指教 ，感谢大家的阅读支持！！！