??前言

常?的雙指針有兩種形式，?種是對撞指針，?種是左右指針
對撞指針：?般?于順序結(jié)構(gòu)中，也稱左右指針。

• 對撞指針從兩端向中間移動。?個指針從最左端開始，另?個從最右端開始，然后逐漸往中間逼近。

• 對撞指針的終?條件?般是兩個指針相遇或者錯開（也可能在循環(huán)內(nèi)部找到結(jié)果直接跳出循環(huán)），也就是：

left == right （兩個指針指向同?個位置）
left > right （兩個指針錯開）

快慢指針：?稱為?兔賽跑算法，其基本思想就是使?兩個移動速度不同的指針在數(shù)組或鏈表等序列結(jié)構(gòu)上移動。

這種?法對于處理環(huán)形鏈表或數(shù)組?常有?。其實不單單是環(huán)形鏈表或者是數(shù)組，如果我們要研究的問題出現(xiàn)循環(huán)往復(fù)的情況時，均可考慮使?快慢指針的思想。快慢指針的實現(xiàn)?式有很多種，最常?的?種就是：

• 在?次循環(huán)中，每次讓慢的指針向后移動?位，?快的指針往后移動兩位，實現(xiàn)?快?慢

??移動零

??題?描述：

給定?個數(shù)組nums ，編寫?個函數(shù)將所有 0 移動到數(shù)組的末尾，同時保持?零元素的相對順序。
請注意，必須在不復(fù)制數(shù)組的情況下原地對數(shù)組進?操作。

• ?例1:
  輸?: nums = [0,1,0,3,12]
  輸出: [1,3,12,0,0]
• ?例2:
  輸?: nums = [0]
  輸出: [0]

class Solution {
    public void moveZeroes(int[] nums) {

    }
}

??算法思路

在本題中，我們可以??個cur 指針來掃描整個數(shù)組，另?個 dest 指針?來記錄?零數(shù)序列的最后?個位置。根據(jù) cur 在掃描的過程中，遇到的不同情況，分類處理，實現(xiàn)數(shù)組的劃分。在cur 遍歷期間，使[0, dest] 的元素全部都是?零元素， [dest + 1, cur - 1] 的元素全是零

??算法流程

初始化 cur = 0 （?來遍歷數(shù)組）， dest = -1 （指向?零元素序列的最后?個位置。因為剛開始我們不知道最后?個?零元素在什么位置，因此初始化為 -1 ）

cur 依次往后遍歷每個元素，遍歷到的元素會有下?兩種情況：

1. 遇到的元素是0 ， cur 直接 ++ 。因為我們的?標是讓 [dest + 1, cur - 1] 內(nèi)的元素全都是零，因此當cur 遇到0 的時候，直接cur ++ ，就可以讓0 在cur - 1 的位置上，從?在[dest + 1, cur - 1] 內(nèi)；

2. 遇到的元素不是0 ， dest++ ，并且交換cur位置和dest位置的元素，之后讓cur++ ，掃描下?個元素。

• 因為des指向的位置是?零元素區(qū)間的最后?個位置，如果掃描到?個新的?零元素，那么它的位置應(yīng)該在dest + 1的位置上，因此 dest 先?增1 ；
• dest++ 之后，指向的元素就是 0元素（因為?零元素區(qū)間末尾的后?個元素就是0 ），因此可以交換到cur所處的位置上，實現(xiàn) [0, dest] 的元素全部都是?零元素， [dest + 1, cur - 1] 的元素全是零。

??代碼實現(xiàn)

class Solution
{
    public void moveZeroes(int[] nums)
    {
        for(int cur = 0, dest = -1; cur < nums.length; cur++)
            // 僅需處理?零元素
            if(nums[cur] != 0) {
                dest++; // dest 先向后移動?位
				// 交換
                int tmp = nums[cur];
                nums[cur] = nums[dest];
                nums[dest] = tmp;
            }
    }
}

??復(fù)寫零

??題?描述：

給你?個?度固定的整數(shù)數(shù)組 arr ，請你將該數(shù)組中出現(xiàn)的每個零都復(fù)寫?遍，并將其余的元素向右平移。
注意：請不要在超過該數(shù)組?度的位置寫?元素。請對輸?的數(shù)組就地進?上述修改，不要從函數(shù)返回任何東西。

• ?例1：
  輸?： arr = [1,0,2,3,0,4,5,0]
  輸出： [1,0,0,2,3,0,0,4]
  解釋：調(diào)?函數(shù)后，輸?的數(shù)組將被修改為： [1,0,0,2,3,0,0,4]

• 示例 2：
  輸入：arr = [1,2,3]
  輸出：[1,2,3]
  解釋：調(diào)用函數(shù)后，輸入的數(shù)組將被修改為：[1,2,3]

class Solution {
    public void duplicateZeros(int[] arr) {

    }
}

??算法思路

如果「從前向后」進?原地復(fù)寫操作的話，由于0的出現(xiàn)會復(fù)寫兩次，導(dǎo)致沒有復(fù)寫的數(shù)「被覆蓋掉」。

因此我們選擇「從后往前」的復(fù)寫策略。但是「從后向前」復(fù)寫的時候，我們需要找到「最后?個復(fù)寫的數(shù)」，因此我們的?體流程分兩步：

• 先找到最后?個復(fù)寫的數(shù)；

• 然后從后向前進?復(fù)寫操作

??算法流程：

1. 初始化兩個指針 cur = 0 ， dest = 0 ；

2. 找到最后?個復(fù)寫的數(shù)：
   當cur < n的時候，?直執(zhí)?下?循環(huán)：

• 判斷cu位置的元素:
  ? 如果是0的話， dest 往后移動兩位；
  ? 否則， dest 往后移動?位。
• 判斷dest時候已經(jīng)到結(jié)束位置，如果結(jié)束就終?循環(huán)；
• 如果沒有結(jié)束， cur++ ，繼續(xù)判斷。

3. 判斷dest 是否越界到 n 的位置： 如果越界，執(zhí)?下?三步：

• n - 1 位置的值修改成 0 ；
• cur 向移動?步；
• dest 向前移動兩步。

4. 從 cur 位置開始往前遍歷原數(shù)組，依次還原出復(fù)寫后的結(jié)果數(shù)組：
   判斷 cur位置的值：

• 如果是0 ： dest 以及 dest - 1位置修改成0 ， dest -= 2 ；
• 如果?零： dest 位置修改成 0 ， dest -= 1 ；

cur-- ，復(fù)寫下?個位置

??代碼實現(xiàn)

class Solution {
    public void duplicateZeros(int[] arr) {
        int cur = 0, dest = -1, n = arr.length;
        // 1. 先找到最后?個需要復(fù)寫的數(shù)
        while(cur < n) {
            if(arr[cur] == 0) {
                dest += 2;
            } else {
                dest += 1;
            }
            if(dest >= n - 1) {
                break;
            }
                cur++;
        }
        // 2. 處理?下邊界情況
        if(dest == n)  {
            arr[n - 1] = 0;
            cur--;
            dest -= 2;
        }
        // 3. 從后向前完成復(fù)寫操作
        while(cur >= 0) {
            if(arr[cur] != 0) {
                arr[dest--] = arr[cur--];
            } else {
                arr[dest--] = 0;
                arr[dest--] = 0;
                cur--;
            }
        }
    }
}

?總結(jié)

關(guān)于《【算法優(yōu)選】雙指針專題——壹》就講解到這兒，感謝大家的支持，歡迎各位留言交流以及批評指正，如果文章對您有幫助或者覺得作者寫的還不錯可以點一下關(guān)注，點贊，收藏支持一下！一起加油文章來源地址http://www.zghlxwxcb.cn/news/detail-717434.html

到了這里，關(guān)于【算法優(yōu)選】雙指針專題——壹的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！