1.移动零
题目链接：移动零
- 题目分析
题目要求我们编写一个函数，将所有 0 移动到末尾，其他非零元素的顺序不变，也就是 [0,1,0,3,12]，操作后非零元素的顺序还是 [1,3,12]，而且必须在原地对数组进行操作，也就是要求原地算法。
- 算法原理
对于该问题，我们一般采用双指针算法，通过两个指针对数组进行操作，这里我们就可以通过数组下标的形式对数组进行操作，怎么做呢？
我们定义两个指针，一个是 cur，也就是 current 的缩写，意为“当前”；一个是 dest，是 destination 的缩写，意为“目标”。
根据意思我们知道，dest 应该指向目标数组的最后一个位置，也就是已处理好的数组的末尾，cur 用来遍历这个数组。
目前我们对该数组没有任何操作，所以已处理好的数据不存在，我们让 dest = -1，然后 cur = 0 开始进行操作。
cur 此时指向 0，不做任何操作，cur++，dest 不动。
cur 此时指向 1，为非 0 元素，和 ++dest 位置进行数据交换，使 0 往后移，然后 cur++。
此时 cur 指向 0，dest 不变，cur++。
此时cur指向3，为非0元素，和++dest位置交换数据，然后cur++。
此时cur指向12，为非0元素，和++dest位置交换数据，然后cur++。
此时cur越界，循环结束，移动零操作完成。
通过观察该操作我们可以发现，dest 永远指向已排好的非零元素的末尾，(dest, cur] 区间内都为 0，cur 之后是尚未处理的数据。
此操作可以概括为一步，直到cur越界结束：
cur++找非零元素，找到后和++dest位置交换数据，然后cur++。
- 代码实现
代码实现就很简单了，我们先写一个for循环，给两个指针定义并初始化，int dest = -1,cur = 0，每次操作结束后cur都要++。循环条件为cur < nums.size()。
然后写内部逻辑，当 nums[cur] == 0 时，不做任何操作；当 nums[cur] != 0 时，和 ++dest 位置的数据交换，可以先判断 ++dest 和 cur 位置是否相同，不相同则进行交换，避免元素与自身交换，减少交换次数，提高效率。
完整代码
class Solution {
public:
void moveZeroes(vector<int>& nums) {
for(int dest = -1,cur = 0;cur<nums.size();cur++)
{
if(nums[cur] == 0)
;
else
{
if(++dest != cur)
swap(nums[cur],nums[dest]);
}
}
}
};
2.复写零
题目链接： 复写零
- 题目分析
这道题让我们复写数组，通过示例我们可以看到，非零元素复写一遍，0 复写两遍，其余元素都要向右平移，由 [1,0,2,3,0,4,5,0] 变为了 [1,0,0,2,3,0,0,4]。且不能在超过数组长度的位置写元素，还要就地修改数组。这就要求我们不能另开数组空间，难度增大了不少。
- 算法原理
对于这道题来说，如果我们从前往后复写，一个指针cur用来遍历数组，一个指针dest用来复写元素。就拿示例举例：
一开始复写了0个元素，所以dest = 0，从下标0开始遍历，cur = 0。
当前arr[cur] = 1，dest复写一次，arr[dest++] = arr[cur++]。
当前arr[cur] = 0，dest复写两次，arr[dest++] = 0,arr[dest++] = 0,cur++。
从这步开始就发现了问题，原来下标2位置的元素被0覆盖了，导致cur指向了0，这样从前往后复写，后面的元素就都变成0了，所以从前往后复写行不通，要从后往前复写。
要从后往前复写，就需要确定要复写的最后一个元素，所以解这道题应该分为两步：
1.找到要复写的最后一个元素。
2.从后往前执行复写操作。
我们先来看第一步，找要复写的最后一个元素，我们用cur遍历数组找要复写的最后一个元素，dest根据元素复写次数向右移动，直到移动到数组末尾为止。
cur = 0,dest = -1。目前没有遍历数组元素，没有复写，所以dest从-1开始。
当前arr[cur] = 1，复写一次，dest向后移动一位，dest++， cur++遍历下一个元素。
arr[cur] = 0，复写两次，dest向后移动两位，dest += 2，cur++遍历下一个元素。
当前arr[cur] = 2，复写一次，dest向后移动一位，dest++， cur++遍历下一个元素。
当前arr[cur] = 3，复写一次，dest向后移动一位，dest++， cur++遍历下一个元素。
arr[cur] = 0，复写两次，dest向后移动两位，dest += 2，cur++遍历下一个元素。
当前arr[cur] = 4，复写一次，dest向后移动一位，dest++，这时dest来到数组末尾，说明找到要复写的最后一个元素了，cur不再向后遍历 。
寻找最后一个要复写的元素可以分为两步：
1.cur指向非0元素，dest向后移动一步，反之移动两步。
2.cur++一直往后遍历数组，直到dest移动到数组末尾，找到最后一个要复写的数，cur停止移动。
然后就是从后往前复写元素了，当前arr[cur] = 4，复写一次，复写完成这两个指针都要向前移动，arr[dest--] = arr[cur--]。
当前arr[cur] = 0，需要复写两次，dest要向前移动两步，cur移动一步，arr[dest--] = 0,arr[dest--] = 0,cur--。
当前arr[cur] = 3，复写一次，复写完成这两个指针都要向前移动，arr[dest--] = arr[cur--]。
当前arr[cur] = 2，复写一次，复写完成这两个指针都要向前移动，arr[dest--] = arr[cur--]。
当前arr[cur] = 0，需要复写两次，dest要向前移动两步，cur移动一步，arr[dest--] = 0,arr[dest--] = 0,cur--。
当前arr[cur] = 1，复写一次，复写完成这两个指针都要向前移动，arr[dest--] = arr[cur--]。
dest越界，完成复写操作。
从后往前复写可概括为：
cur指向非零元素,dest复写一次，两个指针同时往前移一步。
cur指向零元素,dest复写两次，dest往前移两步cur往前移一步。
- 注意：当
dest来到数组末尾的前一个位置，而此时arr[cur] = 0，dest需要向后移动两步，也就是来到了数组末尾的后一个位置，dest越界了，复写时需要处理一下边界问题。
当dest =size时，dest--，arr[dest--] = 0，cur--。完成末尾复写操作。
- 代码实现
由上述原理分析可知，代码一共分为三步：找要复写的最后一个数、处理边界情况、从后往前复写元素。
第一步cur遍历要复写的元素，非零dest向右移一位，反之移动两位，直到dest >= arr.size() - 1。
注意这里的arr.size()是size_t类型，而一开始dest = -1，这两个相比较，-1会被转换成非常大的数，不会进入循环，所以需要先把arr.size()存储为int类型。
第二步处理边界情况，当跳出该循环时说明要复写的最后一个数找到了，就是cur指向的数。考虑dest == n(越界的情况)，此时cur一定指向0，则--dest（超数组长度部分不能写入元素），然后在数组末尾位置复写一个0，两个指针同时往前移一步。arr[dest--] = arr[cur--]
处理好后就可以进行复写循环了，当dest >= 0时说明复写操作还未完成，所以进入复写的条件就是dest >= 0。当cur指向非零元素时，dest位置复写一次然后两指针同时往前移一步，arr[dest--] = arr[cur--]；反之dest位置复写一次0然后向前移动一步，再复写一次0然后向前移动一步，cur向前移动一步。
完整代码
class Solution {
public:
void duplicateZeros(vector<int>& arr) {
//找要复写的最后一个数
int cur = 0,dest = -1,n =arr.size();
while(dest < n - 1)
{
if(arr[cur])
dest++;
else
dest+=2;
//判断dest是否到边界，没有则cur++继续遍历
if(dest >= n - 1)
break;
cur++;
}
//处理边界情况
if(dest == n)
{
--dest;
arr[dest--] = arr[cur--];
}
//从后往前复写元素
while(dest >= 0)
{
if(arr[cur])
arr[dest--] = arr[cur--];
else
{
arr[dest--] = 0;
arr[dest--] = 0;
cur--;
}
}
}
};
转载自 CSDN-专业IT技术社区
原文链接：https://blog.csdn.net/l1147195799/article/details/169266550
