LeetCode 1089. Duplicate zero

1089. Copy zero

 

【 queue 】 Didn't think of a good way , So we can only temporarily store the data in the queue to simulate

1. If the current number is not 0, Directly enter the queue

2. If the current number is 0, Take two. 0 In the queue

3. Modify the current position to the head of the queue

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();
        }
    }
}

【 Double pointer 】 In fact, there is no need to queue , We can use double pointers to see the number of numbers we really need to go through the size of the original array , Then modify the array from back to front .

Take up a ：1,0,2,3,0,4,5,0

Set double pointer i,j When opening, it points to 0,j For the faster pointer

1.i = j = 0,nums[i] != 0,i and j Go back one

2.i = j = 1, nums[i] == 0, i Go back to 1,j Go back to 2

until j Go to the n-1, here i The position of is the limit of the numerical value that the modified array can reach .

【 details 】0,1,0,0 This situation , Should be 0,0,1,0, But we found that i The pointer goes to the third 0 The location of , and j Already exceeded 4, So in this special case, we need to make an extra judgment .

class Solution {
 
    //  Double pointer  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--;
        }
    }
}