LeetCode刷題總結之雙指針法
- 2019 年 10 月 3 日
- 筆記
Leetcode刷題總結
目前已經刷了50道題，從零開始刷題學到了很多精妙的解法和深刻的思想，因此想按方法對寫過的題做一個總結
雙指針法
雙指針法有時也叫快慢指針，在數組裡是用兩個整型值代表下標，在鏈表裡是兩個指針，一般能實現O（n）的時間解決問題，兩個指針的位置一般在第一個元素和第二個元素或者第一個元素和最後一個元素，快指針在前“探路”，當符合某種條件時慢指針向前挪
- 盛最多水的容器
這道題其實是求最大面積，最大面積取決於較小值。初始時兩指針分別位於第一和最後一個元素處，那麼明確指針應該向什麼方向移動是解題的關鍵。既然最大面積取決於較小值，那麼指針應向較大值方向移動：當指針移動的時候，底在減小，那麼假如向較小值方向移，那麼由於底變小，高小於等於前一次的高，此時面積肯定小於之前的面積，每一次移動更新一次面積值。
時間：O（n）
空間：O（1）
代碼如下：
int maxArea(vector<int>& height) { int i=0,j=height.size()-1; int maxA=0; while(j-i>=1) { maxA=max(maxA,(min(height[i],height[j]))*(j-i)); if(height[i]<=height[j]) i++; else j--; } return maxA; }
View Code
2. 三數之和
此題的子步驟是兩數之和，固定一個數，尋找target=-nums[i]的兩個數，採用二分查找的方法（O（logn）），二分法的基礎是有序，因此需要先對其進行排序操作
時間：O（nlogn）+O（nlogn）
空間：O（1）結果數組不算
代碼如下：
vector<vector<int>> threeSum(vector<int>& nums) { int n=nums.size(); sort(nums.begin(),nums.end()); if(n<3||nums[0]>0||nums[n-1]<0) return {}; vector<vector<int>> res; for(int i=0;i<n-2;i++) { if(nums[i]>0) break; if(i>0&&nums[i]==nums[i-1]) continue; int l=i+1,r=n-1; while(l<r) { if(nums[l]+nums[r]==-nums[i]) { vector<int> t; t.push_back(nums[i]); t.push_back(nums[l]); t.push_back(nums[r]); res.push_back(t); l++; r--; while(l<r&&nums[l]==nums[l-1]) l++; while(l<r&&nums[r]==nums[r+1]) r--; } else if(nums[l]+nums[r]<-nums[i]) l++; else r--; } } return res; }
View Code
3. 四數之和
、
此題的子步驟是三數之和，三數之和的子步驟是兩數之和，因此要定兩個數，尋找剩下的兩個
代碼如下：
vector<vector<int>> fourSum(vector<int>& nums, int target) { vector<vector<int>> res; set<vector<int>> a; int n=nums.size(); sort(nums.begin(),nums.end()); if(n<4) return {}; for(int i=0;i<n-3;i++) { for(int j=i+1;j<n;j++) { int l=j+1,r=n-1; while(l<r) { if(nums[i]+nums[j]+nums[l]+nums[r]==target) { a.insert(vector<int>{nums[i],nums[j],nums[l],nums[r],}); l++; r--; } else if(nums[i]+nums[j]+nums[l]+nums[r]>target) r--; else l++; } } } for(auto c:a) { res.push_back(c); } return res; }
View Code
4. 最接近三數之和
int threeSumClosest(vector<int>& nums, int target) { int n=nums.size(); sort(nums.begin(),nums.end()); int res; int min=INT_MAX; for(int i=0;i<n-2;i++) { int l=i+1,r=n-1; while(l<r) { if(abs(target-nums[i]-nums[l]-nums[r])<min) { min=abs(target-nums[i]-nums[l]-nums[r]); res=nums[i]+nums[l]+nums[r]; } if(nums[i]+nums[l]+nums[r]>target) r--; else l++; } } return res; }
View Code
以上是關於數組的一些典型題目，下面是關於鏈表的一些比較好的例子
5. 刪除鏈表的倒數第N個節點
這道題有姊妹題：獲取數組的倒數第N個元素，獲取鏈表的倒數第N個元素，這些題當然可以先遍歷一遍獲得長度，然後再遍歷一遍，但是此時時間是O（2n），而雙指針法則可以到達O（n）
初始時將慢指針置於head，快指針置於第n+1個元素處，然後快慢指針通過循環同時向後遍歷，直到快指針為NULL，刪除慢指針此時指向的節點
為什麼是第n+1個呢？因為是要刪除倒數第N個元素，需要獲得要刪除的節點的前一個節點才可以實現刪除後仍然連接
時間：O（n）
空間：O（1）
代碼如下：
ListNode* removeNthFromEnd(ListNode* head, int n) { if(n==0) return head; if(head==NULL) return head; ListNode* v=head; ListNode* u=head; for(int i=0;i<n;i++) v=v->next; if(v==NULL) { head=head->next; return head; } while(v->next!=NULL) { u=u->next; v=v->next; } u->next=u->next->next; return head; }
View Code
6. 相交鏈表
這道題方法有多種，第一種暴力法，第二種利用哈希表，先將A的所有節點插入哈希表種，然後遍歷B找到重複的節點，時間是O（m+n），但是空間是O（m）或O（n）
雙指針法做法如下：
- 創建兩個指針 pApA 和 pBpB，分別初始化為鏈表
A和B的頭結點。然後讓它們向後逐結點遍歷。 -
當 pApA 到達鏈表的尾部時，將它重定位到鏈表 B 的頭結點 (你沒看錯，就是鏈表 B); 類似的，當 pBpB 到達鏈表的尾部時，將它重定位到鏈表 A 的頭結點。
- 若在某一時刻 pApA 和 pBpB 相遇，則 pApA/pBpB 為相交結點。
- 如果兩個鏈表相交，那麼尾部必然相同
分析：如上圖，假如兩鏈表交點之前的長度一樣，那麼兩個指針依次向後遍歷，相等時則為交點。上述方法就是讓兩個指針從同一位置出發，經過相同步數之後同時到達交點
時間：O（m+n）
空間：O（1）
代碼如下：
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { if(!headA||!headB) return NULL; int m=0,n=0; ListNode *p=headA; ListNode *q=headB; while(p){ m++; p=p->next; } while(q){ n++; q=q->next; } p=headA; q=headB; if(m>n){ for(int i=0;i<m-n;i++) p=p->next; } if(m<n){ for(int i=0;i<n-m;i++) q=q->next; } while(p&&q&&p!=q){ p=p->next; q=q->next; } if(!p) return NULL; else return p; }
View Code
7. 環形鏈表
此題常規方法是哈希表，時間是O（n），空間也是O（n）
雙指針法如下：快指針相當於環形跑道上領先的人，慢指針則是落後的人，如果存在環，那麼快指針總會追上慢指針而相遇。快指針每次走兩步，慢指針每次走一步，快指針相對於慢指針每次走一步。
代碼如下：
bool hasCycle(ListNode *head) { if(head==NULL||head->next==NULL) return 0; ListNode* s=head; ListNode* f=head->next; while(s!=f) { if(f==NULL||f->next==NULL) return 0; s=s->next; f=f->next->next; } return 1; }
View Code
8. 迴文鏈表
此題思想很簡單：找到中點，將後半部分翻轉，然後與前半部分比較
子步驟是鏈表的翻轉，這個也是leetcode上的一道題（206 翻轉鏈表），快指針每次走兩步，慢指針每次走一步，快相對於慢每次走一步，那麼當快指針到了尾部的時候，慢指針在中點，然後將以慢指針為頭指針的鏈表進行翻轉，再進行比較
時間：O（n）
空間：O（1）
代碼如下：
1 bool isPalindrome(ListNode* head) { 2 if(head==NULL||head->next==NULL) 3 return 1; 4 if(head->next!=NULL&&head->next->next==NULL) 5 { 6 if(head->val==head->next->val) 7 return 1; 8 else 9 return 0; 10 } 11 ListNode* fast=head; 12 ListNode* slow=head; 13 for(;fast&&fast->next;slow=slow->next,fast=fast->next->next) 14 ; 15 ListNode* back=reverseList(slow); 16 for(ListNode* front=head;front&&back;front=front->next,back=back->next) 17 if(front->val!=back->val) 18 return 0; 19 return 1; 20 } 21 ListNode* reverseList(ListNode* head) 22 { 23 if(head==NULL||head->next==NULL) 24 return head; 25 ListNode* pre=NULL; 26 ListNode* cur=head; 27 ListNode* next=head; 28 ListNode* res; 29 while(cur!=NULL) 30 { 31 if(next==NULL) 32 res=cur; 33 else 34 next=next->next; 35 cur->next=pre; 36 pre=cur; 37 cur=next; 38 } 39 return res; 40 }
View Code
