1.移動(dòng)零

????????

題目鏈接：移動(dòng) 0_?？皖}霸_?？途W(wǎng) (nowcoder.com)

算法原理：

? ? ? ? 像這樣子的將一整塊數(shù)組劃分很多部分可以稱為數(shù)組劃分，常用的解法可以是雙指針。

說是雙指針，但操作的對(duì)象是數(shù)組，因此下標(biāo)就是指針。?

? ? ? ? 雙指針的精華就是通過倆個(gè)指針將數(shù)組劃分成三個(gè)部分：

那我們讓其這個(gè)規(guī)則貫徹就完成了

想要保證上述劃分的區(qū)域不變的話，那就可以這樣做：

? ? ? ? 先讓left指向 -1 ，right進(jìn)行掃描整個(gè)數(shù)組。

? ? ? ? right遇到0繼續(xù)++，遇到非0的話，然后swap(nums[left+1] ,nums[right]left++, right++

    public int[] moveZeroes (int[] nums) {
        // write code here
        int left = -1;
        int right = 0;
        for(int i = 0;i < nums.length;i++){
            if(nums[right] == 0){
                right++;
            }else{
                swap(left+1,right,nums);
                left++;
                right++;
            }
        }
        return nums;
    }

    public void swap(int left,int right,int[] nums){
        int num = nums[left];
        nums[left] = nums[right];
        nums[right] = num;
    }

2.復(fù)寫零

????????

算法原理：?

? ? ? ? 看到這個(gè)題第一個(gè)想到的是：創(chuàng)建一個(gè)新的數(shù)組，遍歷原數(shù)組然后普通數(shù)字直接復(fù)制到新數(shù)組上，0就復(fù)制倆次唄。

? ? ? ? 但是有沒有可以實(shí)現(xiàn)在這數(shù)組上直接進(jìn)行操作呢？

? ? ? ? 我們先從前往后試著模擬一下：

????????我們發(fā)現(xiàn)left會(huì)往前越過right，并且覆蓋掉了 2這顯然不可以的，那我們就試著從后往前遍歷。

? ? ? ? 那如果從后往前遍歷的話，right指標(biāo)肯定要先指向原數(shù)組最后的一個(gè)位置就比如上述的數(shù)據(jù)，right應(yīng)該指向 val數(shù)據(jù)是 4 。left指向的是最后的元素。然后往前進(jìn)行遍歷，就不會(huì)出現(xiàn)覆蓋的情況了。

? ? ? ? 那就還有個(gè)問題，就是如何找到原數(shù)組最后出現(xiàn)的數(shù)呢？也可以用雙指針從前往后，找到right最后的位置，然后left不需要進(jìn)行換數(shù)據(jù)啥的，主要就是為了找到位置。

具體的步驟如下：

????????

????????

?文章來源地址http://www.zghlxwxcb.cn/news/detail-693882.html

public void duplicateZeros(int[] arr) {
        //1.先找到原數(shù)組最后出現(xiàn)的位置 right就是目標(biāo)位置
        int n = arr.length;
        int top = 0;
        int i = -1;
        while(top < n){
            i++;
            if(arr[i] != 0){
                top++;
            }else{
                top += 2;
            }
        }
        //邊界問題
        int j = n - 1;
        if(top == n + 1){
            arr[j] = 0;
            j--;
            i--;
        }
        //從后往前遍歷
        while(j >= 0){
            arr[j] = arr[i];
            j--;
            if(arr[i] == 0){
                arr[j] = arr[i];
                j--;
            }
            i--;
        }
    }

到了這里，關(guān)于算法專欄——雙指針的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！