📚 目录

• 1. 题目解析

• 2. 算法原理

• 3. 编写代码

LeetCode 1089.复写零｜Java双指针原地解题详解

原题链接：https://leetcode.cn/problems/duplicate-zeros/description/

1. 题目解析

1. 数组是长度固定的整数数组，要求原地修改，不能额外开辟新数组空间，函数最终不需要返回任何数据；
2. 遍历数组，每遇到一个0就额外复写一个0，该0之后所有元素整体向右平移；
3. 填充元素不可超出原数组长度，溢出的数据直接舍弃。

  数据占用规则：

• 非0数字：仅占用数组1个下标位置；
• 数字0：需要占用连续2个下标位置（原有0 + 复写新增的0）。

2. 算法原理

  首先我们会想到第一种双指针的方法: 从前往后的遍历处理
  我们定义两个指针:dest , cur 这两个指针:

  我们从下标0初始化双指针cur、dest：
  非0元素：cur、dest同步后移1位，原地赋值；
  遇见数字0：cur右移1位，dest向后跳2位，连续填入两个0；

  致命缺陷：原地填充0直接覆盖后面原始数据，cur继续右移只会读取刚填的0，后续所有元素不断被改写为0，算法完全出错。
  因此从前往后的双指针不可行。
  前往后不可行,那么从后往前呢?

  此时:从后往前的方法是可行的。
  那我们是怎么知道要从4位置开始复写呢?
  新问题：我们如何精准计算出cur的起始下标（示例里下标4）？

  第一步：正向双指针，锁定反向填充起始下标cur从0开始,dest从-1开始
  规则：cur、dest从下标0同步出发
  遍历元素非0：cur、dest同步向后+1；
  遍历元素为0：cur+1，dest向后+2（0要占用两个数组位置）；
  终止条件：dest走到数组最后一位下标，此时cur的位置就是倒序填充的起始位置，衔接下一阶段反向复写。
  此时我们还需要处理我们边界情况:

  当cur指向元素0时，dest+2会直接超出数组最大下标n-1，触发越界，需要单独处理：
   一旦dest > n-1，立刻跳出正向统计循环；
  手动把数组最后一位arr[n-1] = 0；
  dest回退两步（dest = n-3），cur左移一格，正式开启反向从后向前填充。

3. 编写代码

class Solution {
    public void duplicateZeros(int[] arr) {
        int n = arr.length;
        int cur = 0;
        int dest = -1;
        //找开始位置
        while(cur<n) {
            if(arr[cur] == 0) {
                dest+=2;
            }else {
                dest+=1;
            }
            if(dest >= n-1) {
                break;
            }
            cur++;
        }
        //处理边界
        if(dest == n) {
            arr[n-1] = 0;
            dest -= 2;
            cur --;
        }

        while(cur >= 0) {
            if(arr[cur]!=0) {
                arr[dest--] = arr[cur--];
            }else{
                arr[dest--] = 0;
                arr[dest--] = 0;
                cur--;
            }
        }
    }
}

  结果: