https://blog.csdn.net/2601_95366422/article/details/158542816
上节课链接
一.题目
1089. 复写零 – 力扣（LeetCode）
二.思路讲解
2.1 大方向思路讲解
首先，看到“复写”这个概念，我们就得明白：数组里的元素肯定会“被挤走”。看看示例就能发现，原本的5和最后一个0都消失了。那到底挤走了多少个呢？这就得看“有效0”的个数（也就是那些没被挤走、真正被复写的0）。
怎么确定哪些是有效0，哪些元素会被挤掉呢？这里我们还是用快慢双指针。核心技巧在于：快指针遇到0时，要一次性走两步。这样，当快指针刚好走到数组末尾时，慢指针所在的位置，就是最后一个“幸存”下来需要被处理的元素。
第二步是解决“怎么填”的问题。这里有个关键点：我们必须从右往左填！通常双指针都是从左往右扫，但这里不行。为什么？因为如果你从左往右，右边还没处理的数据可能会被你提前改写掉。比如示例里的第二个0，复写的时候会把原本的2覆盖掉。如果你之后还要用这个位置的数据（你以为是2），实际上拿到的却是0，结果就全乱了。所以，从右往左填，能保证我们读取数据的时候，右边还没处理的部分是完好的。
2.2 具体思路讲解
我们先解决第一步：找到要处理的最后一个元素。
根据大方向的思路，我们需要定义快慢双指针。具体怎么定义呢？
- 慢指针很简单，从0开始。
- 快指针这里有个小技巧，我们要把它定义为-1。因为快指针代表的是慢指针元素“即将要插入”的位置，一开始还没有开始插入操作，所以设为-1作为占位。
接下来开始移动：
- 当慢指针指向非0时，说明这个数不需要复写，直接让快慢指针各往前走一步即可。
- 当慢指针指向0时，说明这个0需要被复写（占两个位置），所以快指针走两步，慢指针走一步。
一直这样循环，直到快指针走到数组的最后一个位置时停下来。这时，慢指针刚好就定位到了最后一个需要处理的有效元素上。 
现在开始第二步：从右往左进行填写。
这一步的操作逻辑和上面类似，但方向相反。
- 当慢指针指向非0时，我们把慢指针位置的值赋给快指针位置，然后两个指针各往左走一步。
- 当慢指针指向0时，我们需要把这个0复写两次。所以，快指针位置赋值为0，然后快指针连续往左走两步，慢指针往左走一步。
就这样一直处理，直到慢指针走完所有有效元素，整个过程就完成了！
2.3 重要难点讲解
上面的逻辑虽然通顺，但有个非常隐蔽的边界情况需要特别注意，这也是这道题最大的坑点：
当最后一个有效元素是 0，就可能会超出数组范围！
当超出数组范围怎么办！
这种情况需要单独判断并处理：
- 此时，我们不需要真的去复写两次，只需要把数组的最后一个元素强制设为 0 即可（因为那个位置本来就要被 0 占据）。
- 然后调整指针：
- 慢指针（slow）：往前（左）走一步，跳过这个只复写了一次的 0。
- 快指针（fast）：往前（左）走两步，因为逻辑上我们已经处理完了这个 0 占据的两个位置。
这样处理后，就能完美避开越界错误，同时保证结果的正确性。
三.正确代码
#include <vector>
using namespace std;
class Solution {
public:
void duplicateZeros(vector<int>& arr)
{
int left = 0;
int right = -1;//要写入的位置
int n = arr.size();
//查找最后一个需要处理的元素
while(left < n)
{
if(arr[left] != 0)
right += 1;
else
right += 2;
//不能在往前走到尽头了
if(right >= n – 1)
break;
left++;//right不越界，left才能往前走
}
//最后一个元素是0，且这个0只能复制一次
if(right == n)
{
arr[n-1] = 0;
left –;
right -= 2;
}
//从右往左写
while(left >= 0)
{
if(arr[left] == 0)
{
arr[right] = arr[left];
arr[right-1] = arr[left];
right -= 2;
}
else
{
arr[right] = arr[left];
right -= 1;
}
left –;
}
}
};
关于这道题，其实还是很难的，难度可以逼近中等了，和上一题的难度还是有很明显的区别的！
