我要评论前言：
目录
1. 题⽬链接：1089.复习0 - 力扣（leetcode）
基础入门知识：
对撞指针：⼀般⽤于顺序结构中，也称左右指针。
快慢指针：⼜称为⻳兔赛跑算法
💨这种⽅法对于处理环形链表或数组⾮常有⽤。
其实不单单是环形链表或者是数组，⭕如果我们要研究的问题出现循环往复的情况时，均可考虑使⽤快慢指针的思想。
📍快慢指针的实现⽅式有很多种，最常⽤的⼀种就是：
• 在⼀次循环中，每次让慢的指针向后移动⼀位，⽽快的指针往后移动两位，实现⼀快⼀慢
1. 复写零（easy）
1. 题⽬链接：1089.复习0 - 力扣（leetcode）
2. 题⽬描述：
给你⼀个⻓度固定的整数数组 arr ，请你将该数组中出现的每个零都复写⼀遍，并将其余的元素向右平移。
注意：请不要在超过该数组⻓度的位置写⼊元素。请对输⼊的数组就地进⾏上述修改，不要从函数返回任何东西。
⽰例 1：
解释：
调⽤函数后，输⼊的数组将被修改为： [1,0,0,2,3,0,0,4]
3.算法原理：
这题需要用到双指针算法，但这不是凭空来的，原题目需要我们对原数组进行操作，
异地操作
📚但是为了方便如何理解复写 0 的过程，我们先画出异地操作的过程：
原图：
复写过程：
cur用于遍历原数组，dest指向了异地操作的数组，
当cur指向的元素为非0时，dest此时要复写一次cur指向的非0元素，cur++,dest++
当cur指向的元素为 0 时，dest要先复写一次0,之后dest++，再复写一次0，复写两次完毕之后cur++，dest++
复写完成：
本地操作
优化为本地操作后，尝试从前往后操作：
验证【从后往前】操作的可行性:
因此我们选择「从后往前」的复写策略，cur指向最后一个需要复写的元素，dest指向最后一个需要复写的位置(结果中的最后一个位置)
这同时也是上面异地操作的结果：
【从后向前的复写过程】
结果：我们可以看到，原地操作和异地操作最终的复写结果是一样的
在这个示例里面，我们可以看到cur指向的4是最后一个需要复写的元素，但是在其他示例里面我们不清楚，那么我们如何找到最后一个需要复写的元素呢？
整体思路：
🎯1.先找到最后一个“复写”的数;
但是思考一下，此时如果cur指向的数组倒数第二个元素是0，那么dest此时指向的位置将会是数组最后一个元素的位置的下一个位置,因为上面遍历的方式是遇到 0 则++两次，非0是一次，那么必定会造成数组越界：
1.5 处理一下边界情况:
📌2."从后向前"完成复写操作（前面已经验证)
代码实现：
class solution {
public:
void duplicatezeros(vector<int>& arr) {
int cur = 0,dest = -1,n=arr.size();
//1.先找到最后一个需要复写的数
while(cur<n)
{
if(arr[cur])
dest++;
else
dest+=2;
if(dest>=n-1)//数组最后一个位置或者最后一个位置的下个位置
break;
cur++;
}
//2.处理一下边界情况
if(dest == n)
{
arr[n-1] = 0;
cur--;
dest-=2;
}
//3.从后往前完成复写操作
while(cur >= 0)
{
if(arr[cur])
{
arr[dest--] = arr[cur--];
//arr[dest] = arr[cur],cur--,dest--
}
else
{
arr[dest--] = 0;
arr[dest--] = 0;
cur--;
}
}
}
};
本篇完结。
发表评论