雙指標演算法簡介：指的是在遍歷物件的程序中，不是普通的使用單個指標進行訪問，而是使用兩個相同方向（快慢指標）或者相反方向（左右指標）的指標進行掃描，從而達到相應的目的，換言之，雙指標法充分使用了陣列有序這一特征，從而在某些情況下能夠簡化一些運算，
具體實作案例如下：
第一類：左右指標
leetcode.125-驗證回文串，全ac代碼如下：
class Solution{//功能實作函式
public:
bool isPalindrome(string s){
int start=0;i int end=s.size()-1;
while(start<end){
while(start<end&&!isalum(s[start]))//start位置如果是字母數字字符則向左移動
start++;
while(start<end&&!isalnum(s[end]))//同理滿足條件時end移動
end--;
if(tolower(s[end])!=tolower(s[start]))//小寫字母不同則回傳false
return false;
start++; end--;
}
return false;
}
};
代碼分析：回文是雙指標演算法中比較常見的一種型別，不難發現回文字串是對稱分布的，因此初始化兩個移動速度相同的指標遍歷字串即可，
第二類：快慢指標
（1）leetcode.19-洗掉鏈表的倒數第N個結點（比較明顯的快慢指標）全ac代碼如下：
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* l=new ListNode(0, head);//new一個數值為0的結點作為頭結點
ListNode* fast=head; ListNode* slow=l; ListNode* ans;
for (int i=0;i<n;i++)
fast=fast->next;//先移動快指標
while(fast){
slow=slow->next; fast=fast->next;//快指標不為空時，慢指標，快指標移動一個單位
}
slow->next=slow->next->next;
ans=l->next;
delete l;//洗掉new的頭結點
return ans;
}
};
代碼分析：根據題意，要先找到鏈表的中間節點，再洗掉，因此不難想到雙指標演算法，初始化兩個快慢指標，快指標先移動，然后每次都會比慢指標奪走一步，因此當快指標到結尾時慢指標指向位置正好是中間結點，delete掉然后slow指向slow->next->next即可，下圖可以形象理解移動程序：
（2）leetcode.142-快樂數（不明顯的快慢指標以及環型結構，做的時候一點也不快樂），全ac代碼如下：
class Solution{
public:
bool isHappy(int n){
int fast=next(n);int slow=n;
while(fast!=slow&&fast!=1){
slow=next(slow); fast=next(next(fast));
}
return (fast==1);
}
public:
int next(int n){//寫一個函式計算每一位數平方和
int x;
int sum=0;
while(n>0){
x=n%10;n=n/10;sum+=x*x;
}
return sum;
}
};
代碼分析：剛入手此題時其實想不到會成環，當仔細觀察一個測驗用例后會發現如果一個數每一位數的平方和無論是否會找不到1則會一直回圈下去，因此成環，所以初始化兩個快慢指標，如果存在1的話，快慢指標在一個環型結構中遍歷總會相遇直到找到1或者快慢指標值相同，所以當fast和slow不相等且fast不是1時，因此分兩種情況，一種是會一直走下去直到兩個指標同時走到1，另外一種是由于快指標走得快所以當fast先到1時即可跳出回圈，此時即為快樂數，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/515097.html
標籤：其他