【算法】双指针(二)-复写零

目录

一、题目介绍

二、双指针原理

1.当前维护指针

1.2维护要求

(1)不能覆盖掉未产效元素

三、提交代码

一、题目介绍

1089. 复写零 - 力扣（LeetCode）

给你一个长度固定的整数数组 arr ，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。

注意：请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。

示例 1：

输入：arr = [1,0,2,3,0,4,5,0] 输出：[1,0,0,2,3,0,0,4] 解释：调用函数后，输入的数组将被修改为：[1,0,0,2,3,0,0,4]

示例 2：

输入：arr = [1,2,3] 输出：[1,2,3] 解释：调用函数后，输入的数组将被修改为：[1,2,3]

提示：

• 1 <= arr.length <= 104
• 0 <= arr[i] <= 9

二、双指针原理

扩容遍历指针、当前维护指针从小维护到大1.当前维护指针

1.1维护方向-双指针(一)移动零1.2维护要求(1)不能覆盖掉未产效元素

超前式覆盖 就从结果后位开始 往回变回 在后追赶 逆序维护

三、提交代码

public void duplicateZeros(int[] arr) { //省去维护的覆盖 到结果后位，就成直接数步子了： int cur = 0; int dest = 0; while(dest < arr.length) { if(arr[cur] == 0) { dest += 2; }else { dest += 1; } cur++; } //从结果后位开始 往回在后追赶 逆序维护： if(dest == arr.length) { //两指针指向的 都是自然再向后移动到的，指向的 并未展开 对着覆值操作的，此时都往回一步就到 数组末尾操作值位置 dest--; cur--; } if(dest > arr.length) { dest--; cur--; //两指针都往回移回一步后 就可以对着开始 往回覆值操作了，但这里dest指向的是越界处，得手动 覆值调一下 arr[dest - 1] = arr[cur];//一定是之前cur指向了0的连续导致的，往回一步后的此时arr[cur]一定是0，连续覆两次 dest -= 2; cur--; } while(cur >= 0) { if(arr[cur] == 0) { arr[dest] = 0; arr[dest-1] = 0; dest -= 2; }else { arr[dest] = arr[cur]; dest--; } cur--; } }

public void duplicateZeros(int[] arr) { int dest = -1, cur = 0; while (dest < arr.length - 1) { // 希望dest留指在数组最后一个元素，是往回覆盖的位置起始位置 // 不用也行，dest上面保护到的，不会越界的：if(cur == arr.length) // cur已经遍历完 最后一个的动作区间也使完了;这是一个0都没有遇到，得cur越界判断一下的动作区间里 做了才移到 数组的最后一个元素位置 if(arr[cur] == 0) dest += 2; else dest++; cur++; // 维护的cur 就指在 留下有用元素的 最后一个 } cur--; if(dest == arr.length) { // cur结尾时遇到0，dest连移到数组外了 而不是刚好数组最后一个位置，如果越界可以赋值，也是正确维护完的 // 手动覆盖一次，不能对越界位置赋值 arr[dest - 1] = 0; // (越界位置一个0)、最后一个位置一个0 dest -= 2; cur--; } while (cur >= 0) { if(arr[cur] == 0) { arr[dest] = 0; arr[dest - 1] = 0; dest -= 2; }else { arr[dest] = arr[cur]; dest--; } cur--; } }