LeetCode 1089. Duplicate Zeros-Toy模板网

这篇具有很好参考价值的文章主要介绍了LeetCode 1089. Duplicate Zeros。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Given a fixed-length integer array arr, duplicate each occurrence of zero, shifting the remaining elements to the right.

Note that elements beyond the length of the original array are not written. Do the above modifications to the input array in place and do not return anything.

Example 1:

Input: arr = [1,0,2,3,0,4,5,0]
Output: [1,0,0,2,3,0,0,4]
Explanation: After calling your function, the input array is modified to: [1,0,0,2,3,0,0,4]

Example 2:

Input: arr = [1,2,3]
Output: [1,2,3]
Explanation: After calling your function, the input array is modified to: [1,2,3]

Constraints:

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

这题要求把一个数组中所有的0后面都加一个0，给我看懵了。

首先第一个想法是java里要怎么extend一个数组……然后仔细看了一下题才发现，它让你加了0以后超出数组长度范围的直接不管了，于是，还是不会。于是，就去直接抄答案了。

这个解法比较清晰直观易懂：https://leetcode.com/problems/duplicate-zeros/solutions/312743/java-c-o-n-o-1/

首先先计算一共有多少0，就能知道需要extend这个数组多长。然后巧妙的地方来了。如果我们从后往前来insert 0的话，就不需要像从前往后那样每次都要把后面所有的数字都移动一遍，大大节省了时间。那么问题又来了，从后面开始的话，那最后面的几个数字在加0以后大概率要被遗留在数组外了，咋整？那遗留在数组外就遗留呗，不往里写就完事了，妙啊。

于是搞懂思路以后代码写起来也比较容易了。相当于还是two pointers，一个指向加完0以后的末尾，一个指向原数组的末尾，把原数组的末尾往加完0以后的末尾copy就完事了，就是需要判断一下如果加完0以后的末尾是溢出的部分就不往里写。文章来源地址https://www.toymoban.com/news/detail-679729.html

class Solution {
    public void duplicateZeros(int[] arr) {
        int count = 0;
        for (int num : arr) {
            if (num == 0) {
                count++;
            }
        }

        int newLast = arr.length + count - 1;
        int oldLast = arr.length - 1;
        while (newLast >= 0 && oldLast >= 0) {
            if (newLast < arr.length) {
                arr[newLast] = arr[oldLast];
            }
            newLast--;
            if (arr[oldLast] == 0) {
                if (newLast < arr.length) {
                    arr[newLast] = 0;
                }
                newLast--;
            }
            oldLast--;
        }
    }
}

到了这里，关于LeetCode 1089. Duplicate Zeros的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！