LeetCode刷題總結之雙指針法

陕西十一选五 www.eoxav.com Leetcode刷題總結

目前已經刷了50道題,從零開始刷題學到了很多精妙的解法和深刻的思想,因此想按方法對寫過的題做一個總結

雙指針法

雙指針法有時也叫快慢指針,在數組里是用兩個整型值代表下標,在鏈表里是兩個指針,一般能實現On)的時間解決問題,兩個指針的位置一般在第一個元素和第二個元素或者第一個元素和最后一個元素,快指針在前“探路”,當符合某種條件時慢指針向前挪

  1. 盛最多水的容器

 

這道題其實是求最大面積,最大面積取決于較小值。初始時兩指針分別位于第一和最后一個元素處,那么明確指針應該向什么方向移動是解題的關鍵。既然最大面積取決于較小值,那么指針應向較大值方向移動:當指針移動的時候,底在減小,那么假如向較小值方向移,那么由于底變小,高小于等于前一次的高,此時面積肯定小于之前的面積,每一次移動更新一次面積值。

時間: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

 

posted on 2019-08-11 13:55 Mr..Prudence 閱讀(...) 評論(...) 編輯 收藏