力扣1089 的本手妙手俗手

力扣1089 的本手妙手俗手 2022-06-22 1067

的本手妙手俗手

题目

本手：模拟遍历数组arr，当arr[i]为0的时候数组右移动，并且i++,避免右移之后下一个还是0又继续右移，代码如下

class Solution {
          
   
    public void duplicateZeros(int[] arr) {
          
   
        for(int i=0;i<arr.length;i++){
          
   
            if(arr[i]==0){
          
   
                rightMove(arr,i);
                i++;//避免重复右移
            }
        }
    }
    //右移
    public void rightMove(int[] arr,int x){
          
   
        for(int i=arr.length-1;i>x;i--){
          
   
            arr[i]=arr[i-1];
        }
    }
}

时间复杂度遍历为n，右移为n，所以复杂度为O(n^2),空间复杂度为O(1)

妙手：使用双指针，设两个指针p,q为0开始遍历数组,当arr[p]=0时，q+=2,p++，否则q++，p++，当

指针p大于或者等于数组长度时遍历结束，然后通过双指针的对应回溯把数组进行修改。

class Solution {
          
   
    public void duplicateZeros(int[] arr) {
          
   
        int len=arr.length;
        int p=0,q=0;
        while(q<len){
          
   
            if(arr[p]==0){
          
   
                q+=2;
            }else{
          
   
                q++;
            }
            p++;
        }
        //因为在上个遍历中最后p++，q可能+1，可能+2,所以取最小的回退，避免值对应的值丢失
        p--;
        q--;
        while(q>=0){
          
   
          if(q<len) arr[q]=arr[p];
          if(arr[p]==0 && --q>0) arr[q]=0;
          q--;
          p--;
        }
    }
}

两次遍历每次遍历时间复杂度为n,所以时间复杂度为O(n)，空间复杂度为O(1)

俗手: 将数组转为字符串，让后将字符串的“0”替换成为“00”，最后截取数组长度的字符串转为int数组

class Solution {
          
   
    public void duplicateZeros(int[] arr) {
          
   
        String str=Arrays.stream(arr).mapToObj(String::valueOf).collect(Collectors.joining()).replaceAll("0","00");
        for(int i=0;i<arr.length;i++){
          
   
            arr[i]=str.charAt(i)-0;
        }
    }
}