力扣网-复写零-EW帮帮网

1.题目要求

2.题目链接

1089. 复写零 - 力扣（LeetCode）

3.题目解答

class Solution {
    public void duplicateZeros(int[] arr) {
        int cur=0,dest=-1,n=arr.length;
        while(cur<n){
            //遇到0就dest走两步
            if(arr[cur]==0){
                dest+=2;
            }
            //遇到非零元素dest就走一步
            else{
                dest+=1;
            }
            //如果dest发生越界或者出现边界情况，就break跳出循环
            if(dest>=n-1){
                break;
            }
            //不跳出循环的情况下，cur++;
            cur++;
       }
       //判断边界情况，也就是dest==n，倒数第二个元素是0，dest+=2,导致越界。
       if(dest==n){
        arr[n-1]=0;
        dest-=2;cur-=1;
       }
       //找到cur和dest的初始位置后，开始从后往前遍历。
       while(cur>=0){
        if(arr[cur]!=0){
            arr[dest--]=arr[cur--];
        }
        //这里如果是if(arr[cur]==0)的话，就会报错，因为两个if语句是存在顺序关系的，会从上而下的依次判断条件并执行，有可能会重复执行导致数组越界。
        else{
            arr[dest--]=0;
            arr[dest--]=0;
            cur--;
        }   
       }
    }
}

4.解题思路

（1）遍历顺序

首先我们应该知道的是，这道题使用的是双指针算法，并且，如果是按从前往后的顺序执行的话，是无法达到题目要求的。这是因为双指针从前往后执行的过程中，会覆盖掉一些值导致错误。

所以这道题应该是使用双指针算法从后往前的遍历，那么，双指针的起始位置应该怎么找呢？

（2）双指针的起始位置：嵌套双指针

这里我们在双指针从后往前遍历前，嵌套一个双指针来先找到起始位置。我们可以先模拟题目的过程：即遇到0复写2次0，我们先不考虑数组值的变化，单纯模拟题目流程，也就是指针dest+=2，cur+=1。遇到非零元素，单纯抄写一遍即可，也就是dest++，cur++。

while(cur<n){
            //遇到0就dest走两步
            if(arr[cur]==0){
                dest+=2;
            }
            //遇到非零元素dest就走一步
            else{
                dest+=1;
            }
            //如果dest发生越界或者出现边界情况，就break跳出循环
            if(dest>=n-1){
                break;
            }
            //不跳出循环的情况下，cur++;
            cur++;
       }

遇到dest=arr.length-1时，也就是dest遍历到在最后一个元素时，停止遍历。得到双指针的初始位置。

（3）特殊情况

如果数组的倒数第二个元素时0，也就是arr【n-2】=0时，这时dest+=2，dest=n，发生数组越界，导致报错。所以这里我们和上面一样，在break跳出循环后，要判断一下。

//判断边界情况，也就是dest==n，倒数第二个元素是0，dest+=2,导致越界。
       if(dest==n){
        arr[n-1]=0;
        dest-=2;cur-=1;
       }

这时，我们把数组最后一个元素置为0，并且dest指针后退两步，cur指针后退一步，即可正确得到初始位置。

（4）双指针从后往前遍历

 //找到cur和dest的初始位置后，开始从后往前遍历。
       while(cur>=0){
        if(arr[cur]!=0){
            arr[dest--]=arr[cur--];
        }
        //这里如果是if(arr[cur]==0)的话，就会报错，因为两个if语句是存在顺序关系的，会从上而下的依次判断条件并执行，有可能会重复执行导致数组越界。
        else{
            arr[dest--]=0;
            arr[dest--]=0;
            cur--;
        }   
       }

这里比较巧妙地运用了arr【dest--】=arr【cur--】和arr【dest--】=0，使得赋值的同时也完成了指针的移动。

5.代码细节

（1）代码简洁

   while(cur>=0){
        if(arr[cur]!=0){
            arr[dest--]=arr[cur--];
        }
        //这里如果是if(arr[cur]==0)的话，就会报错，因为两个if语句是存在顺序关系的，会从上而下的依次判断条件并执行，有可能会重复执行导致数组越界。
        else{
            arr[dest--]=0;
            arr[dest--]=0;
            cur--;
        }   
       }

这里的两种情况要采用if-else，而不可以使用两个if语句进行判断。因为如果使用两个if语句判断，他们会形成先后顺序，在第一个if语句进入后，有可能触发第二个if语句，从而导致数组越界。

（2）越界处理

//判断边界情况，也就是dest==n，倒数第二个元素是0，dest+=2,导致越界。
       if(dest==n){
        arr[n-1]=0;
        dest-=2;cur-=1;
       }

在dest==n这种情况下，是因为cur检测到数组倒数第二个元素是0，导致dest走两步到n，发生数组下标越界。为了处理这种情况，我们可以手动覆写数组最后一个元素为0，这样就等于复写了倒数第二个元素0。

完成复写倒数第二个元素后，我们把双指针对应前移，也就是dest-=2，cur-=1。这样我们就可以忽略倒数第二个元素，从而从后往前进行复写操作（因为我们已经通过arr【n-1】=0操作手动复写了n-2下标的0元素）。

力扣网-复写零