算法進(jìn)階：雙指針（一）c++leetcode例題-創(chuàng)新互聯(lián)

82. 刪除排序鏈表的重復(fù)元素

力扣傳送：
https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/description/

為雙湖等地區(qū)用戶提供了全套網(wǎng)頁(yè)設(shè)計(jì)制作服務(wù)，及雙湖網(wǎng)站建設(shè)行業(yè)解決方案。主營(yíng)業(yè)務(wù)為網(wǎng)站設(shè)計(jì)制作、做網(wǎng)站、雙湖網(wǎng)站設(shè)計(jì)，以傳統(tǒng)方式定制建設(shè)網(wǎng)站，并提供域名空間備案等一條龍服務(wù)，秉承以專業(yè)、用心的態(tài)度為用戶提供真誠(chéng)的服務(wù)。我們深信只要達(dá)到每一位用戶的要求，就會(huì)得到認(rèn)可，從而選擇與我們長(zhǎng)期合作。這樣，我們也可以走得更遠(yuǎn)！

給一個(gè)排好序的鏈表，刪除把鏈表中出現(xiàn)的所有的重復(fù)的項(xiàng)：
1 2 2 3 3 3 4 5 ----->1 4 5

這道題有很多種解法，我第一眼看到這題的時(shí)候，想到了哈希表。
利用哈希表來(lái)記錄出現(xiàn)的重復(fù)的節(jié)點(diǎn)元素，接著在遍歷鏈表，等到這個(gè)節(jié)點(diǎn)出現(xiàn)在了哈希表中，則while 循環(huán)一直跳過(guò)這個(gè)節(jié)點(diǎn)，直到跳到下一個(gè)不同的元素為止。

在這里插入圖片描述

哈希表的做法:

首先遍歷一邊鏈表，記錄下哈希表的數(shù)據(jù)
然后再遍歷一遍鏈表，當(dāng)哈希表記錄的此節(jié)點(diǎn)處的值出現(xiàn)的次數(shù)大于一次時(shí)，一直while找到直到下一個(gè)等于一次的節(jié)點(diǎn)位置，然后連接前一個(gè)節(jié)點(diǎn)位置，這樣就做到了跳過(guò)了出現(xiàn)次數(shù)大于二的節(jié)點(diǎn)的中間節(jié)點(diǎn)。
雙指針?lè)謩e連接鏈表節(jié)點(diǎn)。

class Solution {public:
    ListNode* deleteDuplicates(ListNode* head) {unordered_mapm;
        ListNode* temp=head;
        while (temp)
        {	//首先初始化哈希表，記錄下每個(gè)節(jié)點(diǎn)的值出現(xiàn)的次數(shù)
            m[temp->val]++;
            temp=temp->next;
        }
        ListNode* pDummy=new ListNode{-101,head};
        ListNode* slow=pDummy;
        ListNode* fast=head;
        while (fast && fast->next)
        {if (m[fast->val]>1)
            {ListNode* pTemp=fast->next;
                while (fast && m[fast->val]>1)
                {fast=fast->next;
                }
                slow->next=fast;
            }
            else
            {slow=slow->next;
                fast=fast->next;
            }
        }
        return pDummy->next;
    }
};

哈希表的缺點(diǎn)：
我們的哈希表的空間隨著鏈表的增大而增大，空間復(fù)雜度達(dá)到了O（N）。

但其實(shí)我們沒(méi)必要使用哈希表。
我們知道用哈希表來(lái)記錄出現(xiàn)次數(shù)大于一次的節(jié)點(diǎn)，那我們能不能直接用雙指針的快指針來(lái)記錄呢？只需要合適的邊界檢測(cè)，就可以記錄下其快指針的當(dāng)前節(jié)點(diǎn)元素和下一個(gè)節(jié)點(diǎn)元素的值，判斷他們是否相等即可。

實(shí)現(xiàn)：

啞節(jié)點(diǎn)方便返回鏈表（pDummy）
慢指針在前，快指針在后，快指針移動(dòng)一步，每次快指針都判斷它當(dāng)前的值和后面的值想不想等，如果相等，則快指針進(jìn)入while循環(huán)，一直跳過(guò)。
等到處理完畢后，慢指針前進(jìn)一步，等于快指針；快指針再前進(jìn)一步，等于next

class Solution {public:
    ListNode* deleteDuplicates(ListNode* head) {ListNode* pDummy=new ListNode{-101,head};
        ListNode* slow=pDummy;
        ListNode* fast=head;
        while (fast && fast->next)
        {int val=fast->val;
            if (val==fast->next->val)
            {while (fast && fast->val==val)
                {fast=fast->next;
                }
                slow->next=fast;
            }
            else
            {slow=fast;
                fast=fast->next;
            }
        }
        return pDummy->next;
    }
};

時(shí)間復(fù)雜度：O（N）只遍歷鏈表一遍，空間復(fù)雜度：O（1）

15. 三數(shù)之和

力扣傳送門：
https://leetcode.cn/problems/3sum/description/?envType=study-plan&id=suan-fa-ji-chu&plan=algorithms&plan_progress=y00ve32

找到數(shù)組中是否包含三個(gè)元素使得 nums[i]+nums[j]+nums[z] =0

這道題目一看看出就可以使用暴力搜索的做法：首先給數(shù)組排序，然后創(chuàng)建一個(gè)三重循環(huán)，每重循環(huán)遍歷每一個(gè)元素；注意，我們的元素可能會(huì)出現(xiàn)重復(fù)項(xiàng)，因此我們要跳過(guò)兩重循環(huán)中可能遍歷到的重復(fù)的項(xiàng)：

class Solution {public:
    vector>threeSum(vector& nums) {vector>res;
        int n=nums.size();
        sort(nums.begin(),nums.end());
        for (int i=0;iif (i==0 || nums[i]!=nums[i-1])
            {for (int j=i+1;jif (j==i+1 || nums[j]!=nums[j-1])
                    {for (int z=j+1;zif (z==j+1 || nums[z]!=nums[z-1])
                            { if (nums[i]+nums[j]+nums[z]==0)
                                {res.push_back({nums[i],nums[j],nums[z]});
                                }
                            }
                        }
                    }
                }
            }
        }
        return res;
    }
};

我們的時(shí)間復(fù)雜度達(dá)到了O（N^3）這對(duì)于最長(zhǎng)數(shù)據(jù)量3000來(lái)說(shuō)是很容易超時(shí)的，因?yàn)?3000 * 3000 * 3000 相乘后達(dá)到了27,000,000,000，即這就是三重循環(huán)的最壞的情況，因此暴力搜索的方法無(wú)法通過(guò)。

我們引入一個(gè)新方法：

利用雙指針降低維數(shù)：利用雙指針把三重循環(huán)降低為二重循環(huán)。

當(dāng)我們確定第一個(gè)數(shù)字之后，如果第二個(gè)數(shù)字增大，則第三個(gè)數(shù)字必定減小。
令第二個(gè)數(shù)字和第三個(gè)數(shù)字同時(shí)尋找。
第二個(gè)數(shù)字起始位于第二重循環(huán)的開頭，第三個(gè)數(shù)字起始位于第二重循環(huán)的末尾。

我們就可以保持第二重循環(huán)不變，而將第三重循環(huán)變成一個(gè)從數(shù)組最右端開始向左移動(dòng)的指針
在這里插入圖片描述

class Solution {public:
    vector>threeSum(vector& nums) {int n=nums.size();
        vector>res;
        sort(nums.begin(),nums.end());
        for (int i=0;i//當(dāng)前項(xiàng)和前一項(xiàng)相同，則當(dāng)前數(shù)字已經(jīng)被剛才用過(guò)了，則直接跳過(guò)這個(gè)數(shù)字
            if (i>0 && nums[i]==nums[i-1])
            {continue;
            }
            //第二重循環(huán)同時(shí)遍歷 j 和 z
            int z=n-1;  //初始化z的位置，z從后往前
            for (int j=i+1;j//同理，跳過(guò)重復(fù)的數(shù)字
                if (j>i+1 && nums[j]==nums[j-1])
                {continue;
                }
                //同時(shí)需要保證j0)
                {//因?yàn)樾蛄袕男〉酱笈判颍?dāng)前的結(jié)果大于0，則減小z,尋找合適的位置
                    --z;
                }
                //如果j 和 z相遇，則表示無(wú)論j再往后，z再往前，他們都不可能再有結(jié)果了（和為0），因?yàn)閖再往后遍歷的數(shù)字一定和z之前的一個(gè)數(shù)字相同; z也是，一定和j之前的一個(gè)數(shù)字相同，我們已經(jīng)遍歷過(guò)了，所以這種情況直接退出 
                if (j==z)
                {break;
                }
                if (nums[i]+nums[j]+nums[z]==0)
                {res.push_back({nums[i],nums[j],nums[z]});
                }
            }
        }
        return res;
    }
};

總結(jié)：

當(dāng)我們需要枚舉數(shù)組中的兩個(gè)元素時(shí)，如果我們發(fā)現(xiàn)隨著第一個(gè)元素的遞增，第二個(gè)元素是遞減的，那么就可以使用雙指針的方法，將枚舉的時(shí)間復(fù)雜度從 O(N^2)減少至 O(N)

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

新聞標(biāo)題：算法進(jìn)階：雙指針（一）c++leetcode例題-創(chuàng)新互聯(lián)
文章源于：http://muchs.cn/article6/pieig.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供Google、網(wǎng)站制作、網(wǎng)站營(yíng)銷、網(wǎng)頁(yè)設(shè)計(jì)公司、云服務(wù)器、品牌網(wǎng)站建設(shè)

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容