复写零 ---- 双指针

题目链接

题目:

分析:

• 就地对数组进行操作, 肯定是需要双指针的 
• 那么我们从左往右进行复写, 定义一个cur用来遍历数组, 一个dest用来修改数组的值, 如果cur下标的值不为零, 那么将cur的值写到dest位置, cur++, dest++; 如果cur下标的值为0, 那么就将dest下标的值写为0, dest++, 再将dest的值写为0, dest再++;如果这样做, 就会将数组原来的值覆盖为0 , 就会丢失数据
• 从左往右不行, 那么我们就想到用从右往左的方式复写, 这样就不会覆盖掉数组原来的值

思路:

1. 先找到最后一个复写的数, 因为如果数组中有零, 题目要求不能超出数组的长度, 所以所有的数据不可能都被复写, 所以我们要找到最后一个需要复写数
   1. 我们要模拟一下复写的过程, 所以定义双指针, 一个cur 遍历数组, 找到最后一个被复写的数, 一个dest, 模拟复写的位置, 这个位置不能超过数组的长度
   2. 如果cur == 0, dest++,cur++;
   3. 如果cur != 0, dest +=2;
   4. 特殊:如果最后一个被复写的数是0, 那么dest可能会超过数组的下标, 那么就会越界访问, 所以当dest == 数组的长度时, 我们直接跳过复写这个0, 即, arr[arr.length-1] = 0, dest-= 2, cur--;
2. 这样, 我们就需要对cur前面的数依次进行复写, 如果cur下标的值不为零, 那么将cur的值写到dest位置, cur--, dest--; 如果cur下标的值为0, 那么就将dest下标的值写为0, dest--, 再将dest的值写为0, dest再--, cur--;

代码:

class Solution {
    public void duplicateZeros(int[] arr) {
        int cur = 0;
        int dest = -1;
        for(cur = 0;cur<arr.length;cur++){
            if(arr[cur] == 0){
                dest += 2;
            }else dest++;
           
            if(dest >= arr.length-1 ){
                break;
            }
        }
        if(dest == arr.length){
            arr[arr.length -1] = 0;
            dest -=2;
            cur--;
        }
        while(cur >= 0){
            if(arr[cur] == 0){
                arr[dest--] = 0;
                arr[dest--] = 0;
                cur--;
            }else arr[dest--] = arr[cur--];
        }
    }
}