[数据结构与算法]LeetCode 1089. 复写零

1089. 复写零

?

【队列】没想出太好的方法来，所以只能先把数暂存到队列中模拟了

1.如果当前数字非0，直接进队列

2.如果当前数字为0，把两个0进队列

3.修改当前位置为队列的头

class Solution {
    public void duplicateZeros(int[] arr) {
        Queue<Integer> queue = new LinkedList();
        for(var i = 0; i < arr.length; i++){
            if(arr[i] != 0) queue.offer(arr[i]);
            else {
                queue.offer(0); queue.offer(0);
            }
            arr[i] = queue.poll();
        }
    }
}

【双指针】其实可以不用队列，我们可以通过双指针来看走原数组的大小真正需要的数字个数，然后从后向前修改数组。

举个🌰：1，0，2，3，0，4，5，0

设置双指针i，j一开时都指向0，j为较快的那个指针

1.i = j = 0，nums[i] != 0，i和j都往后走一个

2.i = j = 1, nums[i] == 0, i向后走1，j向后走2

直到j走到n-1，此时i的位置就是修改后数组能达到的数字值的极限了。

【细节】0，1，0，0 这种情况，应该是0，0，1，0，但是我们发现i指针走到了第三个0的位置，而j已经超过了4，所以这种特殊情况要额外判断一下。

class Solution {
 
    // 双指针 9:44 10

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

??