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

注意：请不要在超过该数组长度的位置写入元素。

要求：请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。

示例 1：

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

示例 2：

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

提示：

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

方法一：直接移动

直接按照题目要求，我们直接数组中的元素右移

    public void duplicateZeros(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            if (arr[i] == 0) {
                for (int j = n - 1; j > i ; j--) {
                    arr[j] = arr[j - 1];
                }
                i++;
            }
        }
    }

image.png

这种效率不高

方法二：字符串替换

public void duplicateZeros(int[] arr) {
        StringBuilder stringBuilder = new StringBuilder();
        for (int i : arr) {
            stringBuilder.append(i);
        }
        String s = stringBuilder.toString().replace("0", "00");
        for (int i = 0; i < arr.length; i++) {
            arr[i] = s.charAt(i) - '0';
        }
    }

image.png

方法三：双指针

image.png

 public void duplicateZeros(int[] arr) {
        int n = arr.length;
        int top = 0;
        int i = -1;
        while (top < n) {
            i++;
            if (arr[i] != 0) {
                top++;
            } else {
                top += 2;
            }
        }
        // 如果top = n + 1，说明移动之后最后一个是0
        int j = n - 1;
        if (top == n + 1) {
            arr[j] = 0;
            j--;
            i--;
        }
        while (j >= 0) {
            arr[j] = arr[i];
            j--;
            if (arr[i] == 0) {
                arr[j] = arr[i];
                j--;
            }
            i--;
        }
    }

看官方答案：中间那边步当 top = n + 1的时候，为什么要 i--,j--
我们来画图分析下

image.png

top = n + 1，说明有个0多复制了一个，这种就会导致，后面替换的时候出现，j < i的情况，所以我们直接忽略掉一个0的替换。

  if (top == n + 1) {
            arr[j] = 0;
            j--;
            i--;
        }

image.png

这种情况感觉不好想。所以这个题正常上面两种解法记住记性了

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/duplicate-zeros
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。