哈希入門題目解決(C++) 必看

學(xué)完本文，你需要自己解決：

創(chuàng)新互聯(lián)公司專注于企業(yè)營銷型網(wǎng)站、網(wǎng)站重做改版、莒縣網(wǎng)站定制設(shè)計、自適應(yīng)品牌網(wǎng)站建設(shè)、H5場景定制、成都做商城網(wǎng)站、集團(tuán)公司官網(wǎng)建設(shè)、外貿(mào)網(wǎng)站建設(shè)、高端網(wǎng)站制作、響應(yīng)式網(wǎng)頁設(shè)計等建站業(yè)務(wù)，價格優(yōu)惠性價比高，為莒縣等各大城市提供網(wǎng)站開發(fā)制作服務(wù)。

1. 兩數(shù)之和 - 力扣（LeetCode）

242. 有效的字母異位詞 - 力扣（LeetCode）

349. 兩個數(shù)組的交集 - 力扣（LeetCode）

202. 快樂數(shù) - 力扣（LeetCode）

454. 四數(shù)相加 II - 力扣（LeetCode）

最近剛開始看STL源碼剖析，才知道啥叫一入C++深似海，當(dāng)然扯遠(yuǎn)了，hash類不僅面試常考，而且我認(rèn)為難度是不次于RBTree和AVL等數(shù)據(jù)結(jié)構(gòu)的。 至于hash類的實(shí)現(xiàn)，讀者感興趣的可以看STL源碼剖析，本文是對std::unordered_set和unordered_map的應(yīng)用，只是為了教授讀者如何使用常見的接口。

hash： 查詢和刪除是 o(1)的復(fù)雜度 記住這一點(diǎn)就可以了

常見的接口一定要掌握的，第一重要的就是[]。這個運(yùn)算符對于hash有特殊的意義。官方文檔寫：

Ifkmatches the key of an element in the container, the function returns a reference to its mapped value.

Ifkdoes not match the key of any element in the container, the function inserts a new element with that key and returns a reference to its mapped value. Notice that this always increases the container size by one, even if no mapped value is assigned to the element (the element is constructed using its default constructor).

總結(jié)[]的三大功能就是 ： 1：找(如果存在) 2.插入(key不存在) 3 改

為了避免抽象我用一段簡單代碼解釋下：

unordered_mapmymap;
	mymap["jack"] = 1;
	mymap["lisa"] = 1; //插入
	mymap["james"] = 0;

	int status = mymap["jack"]; //找
	cout<< status<< endl;

	mymap["james"] = 1; //改
	cout<< mymap["james"]<< endl;

另一個常見接口是find，具體內(nèi)容大家看文檔就可以了，用來查找的，有一點(diǎn)我給新手讀者強(qiáng)調(diào)下，find找不到會返回end的迭代器，這點(diǎn)要注意，我們經(jīng)常要利用。

簡單模式

242. 有效的字母異位詞 - 力扣（LeetCode）

這道題其實(shí)很好的反映了哈希思想，其實(shí)哈希的本質(zhì)就是映射，這道題我們沒有必要用stl的hash解決，我就用數(shù)組了，每一個字母我們映射到對應(yīng)的位置，一個加一個減，最后數(shù)組含有非0就是false。

class Solution {
public:
    bool isAnagram(string s, string t) {
    vectorres(26, 0);

    for (auto e: s)
    {
        res[e - 'a']++;
    }

    for (auto e : t)
    {
        res[e- 'a']--;
    }

    for (auto e : res)
    {
        if (e != 0)
            return false;
    }

    return true;
    }
};

349. 兩個數(shù)組的交集 - 力扣（LeetCode）

這道題我們想一下，找交集，可以用兩層for，挨個去比對。我們有沒有更好的辦法？ 其實(shí)就是哈希，我們先用set去重以后，遍歷一個數(shù)組，然后用find接口去找，因?yàn)樵诠Ｖ衒ind是o(1)的對吧，這樣就一層for就解決了，比較簡單，直接上代碼了。

class Solution {
public:
    vectorintersection(vector& nums1, vector& nums2) {
    unordered_setres;
    unordered_setset(nums1.begin(), nums1.end());

    

    for (auto e : nums2)
    {
        if (set.find(e) != set.end())
        {
            res.insert(e);
        }
    }
    return vector(res.begin(), res.end());
    }
};

這里我唯一要說的就是，很多新手很納悶這個find咋等于end去了啊，注意，我再次強(qiáng)調(diào)，文檔一定好好看，find找不到的時候會返回end的迭代器。 所以這句代碼的意思就是我們在set里面找到了e，所以加入到結(jié)果集。

202. 快樂數(shù) - 力扣（LeetCode）

這個題也比較有意思。題目說有可能會無限循環(huán)也到不了1，很多讀者理解不了這啥意思。 我舉個例子啊，比如2， 下一步是4， 16， 37， 58，89，145，42，18，65，61，37. 到這我們發(fā)現(xiàn)了一個重要的問題，凡是這個不是快樂數(shù)的啊，我們算著算著一定會倒回去，不信的你可以自己再舉例試試啊。 所以很簡單，我們直接開一個set，用find找是吧。

bool isHappy(int n) {
    unordered_setres;

    while (1)
    {
        int sum1 = sum(n);
        if (sum1 == 1)
            return true;
        else 
        {
            if (res.find(sum1) != res.end())
            {
                return false;
            }
            else
                res.insert(sum1);
        }

        n = sum1;
    }

這里怎么求每位數(shù)的平方就是sum函數(shù)我就不寫了，讀者應(yīng)該都會。

幾個數(shù)字的和

這里這兩個題比之前的有些難度還是。

1. 兩數(shù)之和 - 力扣（LeetCode）

這個題算倆數(shù)的和，咋算呢，其實(shí)本質(zhì)我還是利用這個find，但是以前咱們都是find這個數(shù)對吧，現(xiàn)在應(yīng)該find啥啊，其實(shí)就是target-我們當(dāng)前這個數(shù)，倆數(shù)是不是就能湊出來了啊。

class Solution {
public:
    vectortwoSum(vector& nums, int target) {
        std::unordered_mapmap; 
        for(int i = 0; i< nums.size(); i++) {
            // 遍歷，并在map中尋找是否有匹配的key
            auto iter = map.find(target - nums[i]); 
            if(iter != map.end()) {
                return {iter->second, i};
            }
            // 如果沒找到，就把訪問過的元素和下標(biāo)加入到map中
            map.insert(pair(nums[i], i)); 
        }
        return {};
    }
};

本題需要我們輸出索引，所以我們用map，pair(數(shù)字，索引)來表示，最后返回的也是iterator的second。還有大家做OJ的時候啊，有的題目要求必須有返回值的，讀者想我們在接口里面肯定就返回了啊不可能到外面來，這個只需要在外面處理一下，寫個空就好了。

454. 四數(shù)相加 II - 力扣（LeetCode）

其實(shí)幾個數(shù)相加的這種問題啊，框架是差不多，但是細(xì)節(jié)實(shí)現(xiàn)起來就個然不同。這道題老實(shí)說一開始我也沒有太好辦法，你直接四個肯定超時。但是看了一下給的數(shù)據(jù)大小，n是小于200的，想了想優(yōu)化下，兩個數(shù)組分成一組，然后去湊。 a+b+c+d == 0， 我ab湊好了以后， 去找 0 -(a+b) 就是(c+d)。還有就是我們找到了應(yīng)該＋幾也是個問題，其實(shí)應(yīng)該加的是key對應(yīng)的value啊，千萬不能加1，因?yàn)槟阆肽鉧+b比如等于5，可能是1和4， 2和3， 很多種情況是不是啊，所以都要加和。

class Solution {
public:
    int fourSumCount(vector& nums1, vector& nums2, vector& nums3, vector& nums4) {
    unordered_mapmap1;


    for(auto e: nums1)
    {
        for(auto x: nums2)
        {
            map1[e + x]++; //我這里說一下范圍for的用法，新手搞不清里面這個e是啥意思，到底是索引還是數(shù)字
        }//范圍for里面的元素全部是迭代器啊，我強(qiáng)調(diào)一下，就是你用范圍for是無法找索引的，因?yàn)樗怯玫鞅闅v的
    }
    int count = 0;
    for (auto e: nums3)
    {
        for(auto x: nums4)
        {
            int target = 0 - (e + x);
            if (map1.find(target) != map1.end())
            {
                count += map1[target]; 
            }
        }
    }
    return count;
    }
};

哈希表的應(yīng)用和玩法還是很多的。等我啃啃書，過段時間再來講解下一些比較難的題。感謝觀看。

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

標(biāo)題名稱：哈希入門題目解決(C++)必看-創(chuàng)新互聯(lián)
URL分享：http://jinyejixie.com/article34/ccchpe.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供動態(tài)網(wǎng)站、建站公司、網(wǎng)站營銷、網(wǎng)站導(dǎo)航、響應(yīng)式網(wǎng)站、虛擬主機(jī)

廣告

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