力扣算法题——1089.复写零【系统讲解】
目录
💕1.题目
💕2.解析思路
本题思路总览
异地实现探索规律
1. 异地实现过程
2. 关键位置观察
从异地到原地的转化
寻找 cur 位置
1. 快慢指针定义
2. 指针移动规则
3. 终止条件
处理边界情况及复制阶段
1. 边界情况处理
2. 复制阶段
💕3.代码实现
💕4.完结
二十七步也能走完逆流河吗
💕1.题目
💕2.解析思路
本题思路总览
本题要求在原数组上进行操作，将数组中每个零都复写一遍，其余元素向右平移，且不能超出数组长度。我们的整体思路是：先通过异地实现（即借助额外数组）找到关键规律，再将规律应用到原地实现（直接在原数组上操作）。
异地实现探索规律
1. 异地实现过程
假设我们有一个额外的数组来存储修改后的结果。我们从原数组的开头开始遍历，遇到非零元素就直接复制到新数组的对应位置；遇到零元素时，就在新数组中连续放置两个零。当新数组填满时停止遍历原数组。
2. 关键位置观察
在异地实现完成后，我们观察两个指针
cur和des的位置。cur指针指向原数组中最后一个被处理的元素位置，des指针指向新数组中最后一个被填充的位置。此时我们会发现，如果从这两个位置开始，分别从后往前复制元素，即原数组从cur位置开始，新数组从des位置开始，就能得到满足题目要求的修改后的数组。
从异地到原地的转化
既然在两个数组的情况下，从
des和cur位置开始从后往前复制能得到正确结果，那么在同一个数组内也可以采用同样的方法。因为数组元素的覆盖是从后往前进行的，不会丢失前面未处理元素的信息，所以可以直接在原数组上进行操作，且des和cur的位置关系保持不变。
寻找
cur位置现在问题的关键就变成了如何找到
cur的位置。这里我们使用快慢指针的思路来解决。
1. 快慢指针定义
cur指针：作为快指针，用于遍历原数组。des指针：作为慢指针，用于间接确定cur的位置。它模拟了在异地实现时新数组的填充位置。
2. 指针移动规则
- 当
cur指向的元素不为零时，des指针向后移动一位，因为此时只需要在新数组（或原数组的模拟填充位置）放置一个元素。- 当
cur指向的元素为零时，des指针向后移动两位，因为要复写零，需要在新数组（或原数组的模拟填充位置）放置两个零。
3. 终止条件
在移动过程中，不断检查
des指针是否达到或超过原数组的最后一个位置。当des >= arr.size() - 1时，说明已经找到了最后一个需要处理的元素位置cur，停止遍历。
处理边界情况及复制阶段
1. 边界情况处理
如果
des刚好等于arr.size()，说明最后一个零复写后超出了数组长度，此时需要特殊处理。我们将数组的最后一个位置赋值为零，然后将cur和des指针都向前移动一位。
2. 复制阶段
从
cur和des位置开始，从后往前遍历数组。如果cur指向的元素不为零，将其复制到des位置；如果cur指向的元素为零，将零复写到des位置及其前一个位置。每次复制后，cur和des指针都向前移动相应的位置，直到cur小于 0 为止。通过以上步骤，我们就可以在原数组上完成零的复写操作，同时保证不超出数组长度。
💕3.代码实现
class Solution { public: void duplicateZeros(vector<int>& arr) { int des = -1;//最开始不知道位置先设为-1 int cur = 0; //找到cur while(cur<=arr.size()-1) { if(arr[cur]!=0) { des++; }else{ des +=2; } if(des>=arr.size()-1) { break; } cur++; } //特殊处理 if(des == arr.size()) { arr[--des] = 0; cur--; des--; } //复制 while(cur>=0) { if(arr[cur]!=0) { arr[des] = arr[cur]; des--; }else{ arr[des] = arr[cur]; des--; arr[des] = arr[cur]; des--; } cur--; } } };
