柚子快報激活碼778899分享：c++ 算法魅力-雙指針的實戰(zhàn)
柚子快報激活碼778899分享：c++ 算法魅力-雙指針的實戰(zhàn)
目錄
1.雙指針的介紹
?1. 左右指針（對撞指針）
?2. 快慢指針
2.題目練習(xí)講解
?2.1 移動零
?算法思路
代碼展示
畫圖效果效果
2.2 復(fù)寫零
算法思路
?代碼展示
2.3 快樂數(shù)
算法思路
代碼展示
2.4 盛最多水的容器
算法思路
代碼展示
結(jié)束語
1.雙指針的介紹
雙指針?biāo)惴ㄊ且环N常用的算法技巧，通常用于解決數(shù)組或鏈表相關(guān)的題目。雙指針?biāo)惴ǖ暮诵乃枷胧鞘褂脙蓚€指針在數(shù)組或鏈表上移動，這里的指針并不是只是指指針，我們可以用數(shù)組下標(biāo)來代替，以達到解決問題的目的。根據(jù)具體問題，雙指針可以分為以下幾種類型：
?1. 左右指針（對撞指針）
左右指針通常用于處理數(shù)組中的問題，其中一個指針從數(shù)組的開始位置向后移動，另一個指針從數(shù)組的結(jié)束位置向前移動。
指針從兩端向中間移動。一個指針從最左端開始，另一個從最右端開始，然后逐漸往中間逼
近。
對撞指針的
終止條件一般是兩個指針相遇或者錯開（也可能在循環(huán)內(nèi)部找到結(jié)果直接跳出循環(huán)），也就是：
left == right （兩個指針指向同一個位置）
left > right （兩個指針錯開）
典型問題： 二分查找：在有序數(shù)組中查找一個特定的元素。 兩數(shù)之和：在數(shù)組中找到兩個數(shù)，使它們的和等于一個給定的數(shù)。
?2. 快慢指針
快慢指針主要用于處理鏈表中的問題，兩個指針從同一位置出發(fā)，一個指針（快指針）每次移動兩個節(jié)點，另一個指針（慢指針）每次移動一個節(jié)點。 ?典型問題： 判斷鏈表中是否有環(huán)：Floyd 判圈算法（龜兔賽跑算法）。 找到鏈表的中間節(jié)點：快指針到達終點時，慢指針正好在中間。 雙指針?biāo)惴ǖ年P(guān)鍵在于指針的移動策略和終點的判斷條件，根據(jù)具體問題，雙指針的移動策略和判斷條件可能會有所不同。
2.題目練習(xí)講解
?2.1 移動零
283. 移動零 - 力扣（LeetCode）
給定一個數(shù)組?nums，編寫一個函數(shù)將所有?0?移動到數(shù)組的末尾，同時保持非零元素的相對順序。
請注意?，必須在不復(fù)制數(shù)組的情況下原地對數(shù)組進行操作。
示例 1:
輸入: nums = [0,1,0,3,12]
輸出: [1,3,12,0,0]
示例 2:
輸入: nums = [0]
輸出: [0]
?算法思路
在本題中，我們可以用一個 cur 指針來掃描整個數(shù)組，另一個 dest 指針用來記錄非零數(shù)序列
的最后一個位置。根據(jù) cur 在掃描的過程中，遇到的不同情況，分類處理，實現(xiàn)數(shù)組的劃分。
在 cur 遍歷期間，使 [0, dest] 的元素全部都是非零元素， [dest + 1, cur - 1] 的元素全是零。
[cur,n-1]是待處理的元素。
首先，我們，我們讓dest指向-1的位置，cur指向數(shù)組的首元素，通過循環(huán)控制cur的移動，無論cur指向誰，一次循環(huán)過后都要++，而當(dāng)cur指向的數(shù)據(jù)是非0元素時，我們就讓dest++,讓加之后的dest與cur進行元素交換。
詳細就是：
?cur 依次往后遍歷每個元素，遍歷到的元素會有下面兩種情況：
i. 遇到的元素是 0 ， cur 直接 ++ 。因為我們的目標(biāo)是讓 [dest + 1, cur - 1] 內(nèi)
的元素全都是零，因此當(dāng) cur 遇到 0 的時候，直接 ++ ，就可以讓 0 在 cur - 1
的位置上，從而在 [dest + 1, cur - 1] 內(nèi)；
ii. 遇到的元素不是 0 ， dest++ ，并且交換 cur 位置和 dest 位置的元素，之后讓
cur++ ，掃描下?個元素。
? 因為 dest 指向的位置是非零元素區(qū)間的最后一個位置，如果掃描到一個新的非零元
素，那么它的位置應(yīng)該在 dest + 1 的位置上，因此 dest 先自增 1 ；
? dest++ 之后，指向的元素就是 0 元素（因為非零元素區(qū)間末尾的后一個元素就是
0 ），因此可以交換到 cur 所處的位置上，實現(xiàn) [0, dest] 的元素全部都是非零
元素， [dest + 1, cur - 1] 的元素全是零。
代碼展示
class Solution
{
public:
void moveZeroes(vector
{
for(int cur = 0, dest = -1; cur < nums.size(); cur++)
if(nums[cur]) // 處理?零元素
swap(nums[++dest], nums[cur]);
}
};
?當(dāng)然，我們也可以讓dest指向首元素，后續(xù)算法邏輯類似，只是變成了先交換在++。
class Solution
{
public:
void moveZeroes(vector
{
for(int cur = 0, dest = 0; cur < nums.size(); cur++)
if(nums[cur]) // 處理?零元素
swap(nums[dest++], nums[cur]);
}
};
畫圖效果效果
2.2 復(fù)寫零
1089. 復(fù)寫零 - 力扣（LeetCode）
算法思路
同樣這道題我們用雙指針的算法，我們首先普遍會想到定義兩個指針，從前向后開始復(fù)寫，從首元素開始移動，在移動過程中由于0會寫兩次，我們會發(fā)現(xiàn)后一個數(shù)據(jù)會被覆蓋就會達不到效果。
故當(dāng)我們換成從后向前復(fù)寫時，可以避免這種情況，但是我們需要找到復(fù)寫的最后一個元素。
我們還是定義兩個指針：
初始化兩個指針 cur = 0 ， dest = -1?；
b. 找到最后一個復(fù)寫的數(shù)：
i. 當(dāng) cur < n 的時候，一直執(zhí)行下面循環(huán)：
? 判斷 cur 位置的元素:
? 如果是 0 的話， dest 往后移動兩位；
? 否則， dest 往后移動一位。
? 判斷 dest 時候已經(jīng)到結(jié)束位置，如果結(jié)束就終止循環(huán)；
? 如果沒有結(jié)束， cur++ ，繼續(xù)判斷。
從 cur 位置開始往前遍歷原數(shù)組，依次還原出復(fù)寫后的結(jié)果數(shù)組：
i. 判斷 cur 位置的值：
1. 如果是 0 ： dest 以及 dest - 1 位置修改成 0 ， dest -= 2 ；
2. 如果?零： dest 位置修改成 0 ， dest -= 1 ；
ii. cur-- ，復(fù)寫下一個位置。
while(cur>=0){
if(arr[cur])
arr[dest--]=arr[cur--];
else{
arr[dest--]=0;
arr[dest--]=0;
cur--;
}
}
我們發(fā)現(xiàn)有些情況會數(shù)組越界，超出一位，當(dāng)我們往前遍歷復(fù)寫的時候就會出現(xiàn)問題，因為數(shù)組外賦值了。
所以我們要處理數(shù)組越界的情況
?如果越界，n - 1 位置的值修改成 0 ； ?cur 向移動一步； dest 向前移動兩步。
?代碼展示
class Solution {
public:
void duplicateZeros(vector
int cur=0,dest=-1;
int n=arr.size();
while(cur if(arr[cur]) dest++; else dest+=2; if(dest>=n-1) break; cur++; } if(dest==n){ arr[n-1]=0; dest-=2; cur--; } while(cur>=0){ if(arr[cur]) arr[dest--]=arr[cur--]; else{ arr[dest--]=0; arr[dest--]=0; cur--; } } } }; 圖片效果展示 2.3 快樂數(shù) 202. 快樂數(shù) - 力扣（LeetCode） 算法思路 首先可以將題目解答猜成兩部分，第一部分是求取每個位數(shù)上的平方和，第二步就是與1進行比較。 通過快樂數(shù)的定義我們發(fā)現(xiàn)其實當(dāng)它結(jié)果為1時，也會陷入一個1的循環(huán)。所以不管那種過程，累加次都會陷入循環(huán)，最終都會走到一個環(huán)中進行循環(huán)。 情況一：一直在 1 中死循環(huán)，即 1 -> 1 -> 1 -> 1...... 情況二：在歷史的數(shù)據(jù)中死循環(huán)，但始終變不到 1 簡單證明一下： 經(jīng)過一次變化之后的最大值 9^2 * 10 = 810 ( 2^31-1=2147483647 。選一個更大的最 大?9999999999 )，也就是變化的區(qū)間在 [1, 810] 之間； ?根據(jù)「鴿巢原理」，一個數(shù)變化 811 次之后，必然會形成一個循環(huán)； ?因此，變化的過程最終會走到一個圈里面，因此可以用「快慢指針」來解決 將「對于一個正整數(shù)，每一次將該數(shù)替換為它每個位置上的數(shù)字的平方和」這一個 操作記為 x 操作 根據(jù)上述分析，我們可以知道，當(dāng)重復(fù)執(zhí)行?x 的時候，數(shù)據(jù)會陷入到一個「循環(huán)」之中。 而「快慢指針」有一個特性，就是在一個圓圈中，快指針總是會追上慢指針的，也就是說他們總會 相遇在一個位置上。如果相遇位置的值是 1 ，那么這個數(shù)一定是快樂數(shù)；如果相遇位置不是 1的話，那么就不是快樂數(shù)。 代碼展示 class Solution { public: int ret(int n){ int sum=0; while(n){ int a=n%10; sum+=a*a; n=n/10; } return sum; } bool isHappy(int n) { int slow=n; int fast=ret(n); while(slow!=fast){ slow=ret(slow); fast=ret(ret(fast)); } return slow==1; } }; 2.4 盛最多水的容器 11. 盛最多水的容器 - 力扣（LeetCode） 這道題我們首先會想到枚舉，通過暴力的解法將每一種的體積算出來，選出最大的。 lass Solution { public: int maxArea(vector int n=height.size(); int ret=0; for(int i=0;i for(int j=i+1;j ret = max(ret, min(height[i], height[j]) * (j - i)); } } return ret; } }; ?但是這種解法會超時。所以需要換一種思路。我們可以采用對撞指針的思路。 算法思路 設(shè)兩個指針 left ， right 分別指向容器的左右兩個端點，此時容器的容積 : v = (right - left) * min( height[right], height[left]) 容器的左邊界為 height[left] ，右邊界為 height[right] 。 我們假設(shè)「左邊邊界」小于「右邊邊界」。 如果此時我們固定一個邊界，改變另一個邊界，水的容積會有如下變化形式： 容器的寬度一定變小。 由于左邊界較小，決定了水的高度。 如果改變左邊界，新的水面高度度不確定，但是一定不會超過右邊的柱子高度，因此容器的容積可能會增大。 ? 如果改變右邊界，無論右邊界移動到哪里， 新的水面的高度一定不會超過左邊界，也就是不會超過現(xiàn)在的水面高度，但是由于容器的寬度減小，因此容器的容器一定會變小的。 由此可見，左邊界和其余邊界的組合情況都可以舍去。所以我們可以 left++ 跳過這個邊界，繼續(xù)去判斷下一個左右邊界。 代碼展示 class Solution { public: int maxArea(vector int left=0,right=height.size()-1; int max=0; for(int i=0;i if(max<((right-left)*min(height[left],height[right]))) max=(right-left)*min(height[left],height[right]); if(height[left]<=height[right]) left++; else right--; } return max; } }; 結(jié)束語 相信通過本篇博客大家對雙指針?biāo)惴ㄓ辛艘欢ǖ牧私?，下篇博客我們將繼續(xù)講解三道例題加深對雙指針的印象。 最后感謝各位友友的支持，有不同的解法思路歡迎大家在評論區(qū)討論?。?！ 柚子快報激活碼778899分享：c++ 算法魅力-雙指針的實戰(zhàn) 推薦閱讀
本文內(nèi)容根據(jù)網(wǎng)絡(luò)資料整理，出于傳遞更多信息之目的，不代表金鑰匙跨境贊同其觀點和立場。
轉(zhuǎn)載請注明，如有侵權(quán)，聯(lián)系刪除。
Jollychic時尚達人
