C++第二階段——數(shù)據(jù)結(jié)構(gòu)和算法，之前學(xué)過(guò)一點(diǎn)點(diǎn)數(shù)據(jù)結(jié)構(gòu)，當(dāng)時(shí)是基于Python來(lái)學(xué)習(xí)的，現(xiàn)在基于C++查漏補(bǔ)缺，尤其是樹(shù)的部分。這一部分計(jì)劃一個(gè)月，主要利用代碼隨想錄來(lái)學(xué)習(xí)，刷題使用力扣網(wǎng)站，不定時(shí)更新，歡迎關(guān)注！

一、有效的字母異位詞（力扣242）

給定兩個(gè)字符串 s 和 t ，編寫(xiě)一個(gè)函數(shù)來(lái)判斷 t 是否是 s 的字母異位詞。
注意：若 s 和 t 中每個(gè)字符出現(xiàn)的次數(shù)都相同，則稱(chēng) s 和 t 互為字母異位詞。
示例 1:
輸入: s = “anagram”, t = “nagaram”
輸出: true
示例 2:
輸入: s = “rat”, t = “car”
輸出: false
提示:
1 <= s.length, t.length <= 5 * 104
s 和 t 僅包含小寫(xiě)字母

class Solution {
public:
    bool isAnagram(string s, string t) {
        // 創(chuàng)建哈希數(shù)組
        int hashArray[26] = {0};
        for (int i=0;i<s.length();i++){
            hashArray[s[i]-'a']++;
        }
        for(int i=0;i<t.length();i++){
            hashArray[t[i]-'a']--;
        }
        for(int i=0;i<26;i++){
            if(hashArray[i]!=0){
                return false;
            }
        }
        return true;
    }
};

二、兩個(gè)數(shù)組的交集（力扣349）

給定兩個(gè)數(shù)組 nums1 和 nums2 ，返回 它們的交集 。輸出結(jié)果中的每個(gè)元素一定是 唯一 的。我們可以 不考慮輸出結(jié)果的順序 。
示例 1：
輸入：nums1 = [1,2,2,1], nums2 = [2,2]
輸出：[2]
示例 2：
輸入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
輸出：[9,4]
解釋?zhuān)篬4,9] 也是可通過(guò)的
提示：
1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        // 使用set hash處理
        unordered_set<int> hashSet;
        // 結(jié)果列表
        unordered_set<int> result;
        for(int i=0;i<nums1.size();i++){
            // 將nums添加
            hashSet.insert(nums1[i]);
        }
        for(int i=0;i<nums2.size();i++){
            // 找nums2[i]在不在hashset中
            if(hashSet.find(nums2[i])!=hashSet.end()){
                // 找到了
                result.insert(nums2[i]);
            }
        }
        vector<int> vectorResult(result.begin(),result.end());
        return vectorResult;
    }
};

三、快樂(lè)數(shù)（力扣202）

編寫(xiě)一個(gè)算法來(lái)判斷一個(gè)數(shù) n 是不是快樂(lè)數(shù)。
對(duì)于一個(gè)正整數(shù)，每一次將該數(shù)替換為它每個(gè)位置上的數(shù)字的平方和。
然后重復(fù)這個(gè)過(guò)程直到這個(gè)數(shù)變?yōu)?1，也可能是 無(wú)限循環(huán) 但始終變不到 1。
如果這個(gè)過(guò)程 結(jié)果為 1，那么這個(gè)數(shù)就是快樂(lè)數(shù)。
如果 n 是 快樂(lè)數(shù) 就返回 true ；不是，則返回 false 。
示例 1：
輸入：n = 19
輸出：true
解釋?zhuān)?br> 12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
示例 2：
輸入：n = 2
輸出：false
提示：
1 <= n <= 231 - 1

class Solution {
public:
    bool isHappy(int n) {
        // 使用hashset去判斷這個(gè)數(shù)是否出現(xiàn)
        unordered_set<int> hashset;
        while(true){
            if(n==1){
                return true;
            }
            else{
                n = getHappy(n);
                // 判斷是否存在過(guò)
                if(hashset.find(n)!=hashset.end()){
                    // 存在過(guò)
                    return false;
                }
                // n存入hashset中
                hashset.insert(n);
            }

        }
    }
    int getHappy(int a){
        // 將該數(shù)替換為它每個(gè)位置上的數(shù)字的平方和。
        int sum =0;
        while(a!=0){
            int temp = a%10;
            sum+=temp*temp;
            a = a/10;
        }

        return sum;
    }
};

四、兩數(shù)之和（力扣1）

給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)整數(shù)目標(biāo)值 target，請(qǐng)你在該數(shù)組中找出 和為目標(biāo)值 target 的那 兩個(gè) 整數(shù)，并返回它們的數(shù)組下標(biāo)。
你可以假設(shè)每種輸入只會(huì)對(duì)應(yīng)一個(gè)答案。但是，數(shù)組中同一個(gè)元素在答案里不能重復(fù)出現(xiàn)。
你可以按任意順序返回答案。
示例 1：
輸入：nums = [2,7,11,15], target = 9
輸出：[0,1]
解釋?zhuān)阂驗(yàn)?nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
輸入：nums = [3,2,4], target = 6
輸出：[1,2]
示例 3：
輸入：nums = [3,3], target = 6
輸出：[0,1]
提示：
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只會(huì)存在一個(gè)有效答案
進(jìn)階：你可以想出一個(gè)時(shí)間復(fù)雜度小于 O(n2) 的算法嗎？

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // 使用hashmap解決
        unordered_map<int,int> hashMap;
        for(int i=0;i<nums.size();i++){
            // 計(jì)算需要的值
            int need = target-nums[i];
            if(hashMap.find(need)!=hashMap.end()){
                // 找到了
                return {hashMap[need],i};
            }
            else{
                // 將nums[i]存入hashmap中
                hashMap.insert(make_pair(nums[i],i));
            }
        }
        return {};
    }
};

五、四數(shù)相加 II（力扣454）

給你四個(gè)整數(shù)數(shù)組 nums1、nums2、nums3 和 nums4 ，數(shù)組長(zhǎng)度都是 n ，請(qǐng)你計(jì)算有多少個(gè)元組 (i, j, k, l) 能滿(mǎn)足：
0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
示例 1：
輸入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
輸出：2
解釋?zhuān)?br> 兩個(gè)元組如下：
(0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
(1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0
示例 2：
輸入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
輸出：1
提示：
n == nums1.length
n == nums2.length
n == nums3.length
n == nums4.length
1 <= n <= 200
-228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        // 每?jī)蓚€(gè)相加，通過(guò)hashmap進(jìn)行存儲(chǔ)，key為相加的值，value為出現(xiàn)的次數(shù)
        unordered_map<int,int> hashMapFS; // first and Second
        // 遍歷前兩個(gè)
        for(int i=0;i<nums1.size();i++){
            for(int j=0;j<nums2.size();j++){
                hashMapFS[nums1[i]+nums2[j]]++; // 添加次數(shù)
            }
        }
        // 遍歷后兩個(gè)
        int count =0;
        for(int i=0;i<nums3.size();i++){
            for(int j=0;j<nums4.size();j++){
                int sumTF = nums3[i]+nums4[j];
                int target = -sumTF;
                if(hashMapFS.find(target)!=hashMapFS.end()){
                    // 找到了
                    count += hashMapFS[target]; // 將次數(shù)添加
                }
            }
        }
        return count;
        //
    }
};

六、贖金信（力扣383）

給你兩個(gè)字符串：ransomNote 和 magazine ，判斷 ransomNote 能不能由 magazine 里面的字符構(gòu)成。
如果可以，返回 true ；否則返回 false 。
magazine 中的每個(gè)字符只能在 ransomNote 中使用一次。
示例 1：
輸入：ransomNote = “a”, magazine = “b”
輸出：false
示例 2：
輸入：ransomNote = “aa”, magazine = “ab”
輸出：false
示例 3：
輸入：ransomNote = “aa”, magazine = “aab”
輸出：true
提示：
1 <= ransomNote.length, magazine.length <= 105
ransomNote 和 magazine 由小寫(xiě)英文字母組成

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        // 使用hast數(shù)組解決，判斷最后hashset中有沒(méi)有<0的數(shù)即可
        int hashset[52] ={0};
        for(int i=0;i<magazine.length();i++){
            // 添加到hashset中
            hashset[magazine[i]-'a']++;
        }
        for(int i=0;i<ransomNote.length();i++){
            // 對(duì)應(yīng)位置相減
            hashset[ransomNote[i]-'a']--;
        }
        // 查看有沒(méi)有小于0的
        for(int i=0;i<52;i++){
            if(hashset[i]<0){
                return false;
            }
        }
        return true;
    }
};

七、三數(shù)之和（力扣15）

給你一個(gè)整數(shù)數(shù)組 nums ，判斷是否存在三元組 [nums[i], nums[j], nums[k]] 滿(mǎn)足 i != j、i != k 且 j != k ，同時(shí)還滿(mǎn)足 nums[i] + nums[j] + nums[k] == 0 。請(qǐng)
你返回所有和為 0 且不重復(fù)的三元組。
注意：答案中不可以包含重復(fù)的三元組。
示例 1：
輸入：nums = [-1,0,1,2,-1,-4]
輸出：[[-1,-1,2],[-1,0,1]]
解釋?zhuān)?br> nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元組是 [-1,0,1] 和 [-1,-1,2] 。
注意，輸出的順序和三元組的順序并不重要。
示例 2：
輸入：nums = [0,1,1]
輸出：[]
解釋?zhuān)何ㄒ豢赡艿娜M和不為 0 。
示例 3：
輸入：nums = [0,0,0]
輸出：[[0,0,0]]
解釋?zhuān)何ㄒ豢赡艿娜M和為 0 。
提示：
3 <= nums.length <= 3000
-105 <= nums[i] <= 105

注意去重?。?！

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        // 先對(duì)數(shù)組排序
        sort(nums.begin(),nums.end());
        // 定義結(jié)果數(shù)組
        vector<vector<int>> result;
        // 剪枝操作
        if(nums[0]>0){
            return {}; // 第一個(gè)元素都大于0了，說(shuō)明不可能加起來(lái)等于0，直接返回空
        }
        for(int i=0;i<nums.size();i++){
            // 定義兩個(gè)指針
            int begin = i+1;
            int end = nums.size()-1;
            // 去重操作
            if(i>0&&nums[i]==nums[i-1]){
                // 當(dāng)前的i和i-1的元素是一樣的
                continue; // 跳過(guò)當(dāng)前循環(huán)
            }
            while(begin<end){
                if((nums[i]+nums[begin]+nums[end])==0){
                    result.push_back({nums[i],nums[begin],nums[end]});
                    while(begin<end&&nums[begin]==nums[begin+1]){
                        begin++;
                    }
                    while(begin<end&&nums[end]==nums[end-1]){
                        end--;
                    }
                    begin++;
                    end--;
                }
                else if((nums[i]+nums[begin]+nums[end])>0){
                    end--;
                }
                else{
                    begin++;
                }

            }


        }
        return result;
    }
};

八、四數(shù)之和（力扣18）

給你一個(gè)由 n 個(gè)整數(shù)組成的數(shù)組 nums ，和一個(gè)目標(biāo)值 target 。請(qǐng)你找出并返回滿(mǎn)足下述全部條件且不重復(fù)的四元組 [nums[a], nums[b], nums[c], nums[d]] （若兩個(gè)四元組元素一一對(duì)應(yīng)，則認(rèn)為兩個(gè)四元組重復(fù)）：
0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意順序 返回答案 。
示例 1：
輸入：nums = [1,0,-1,0,-2,2], target = 0
輸出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：
輸入：nums = [2,2,2,2,2], target = 8
輸出：[[2,2,2,2]]
提示：
1 <= nums.length <= 200
-109 <= nums[i] <= 109
-109 <= target <= 109

兩層for循環(huán)，同樣注意去重！

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        // 先排序
        sort(nums.begin(),nums.end());
        // 定義最終返回?cái)?shù)組
        vector<vector<int>> result;
        // 類(lèi)似于三數(shù)之和，多了一層循環(huán)
        for (int i=0;i<nums.size();i++){
            // 剪枝
            if(nums[0]>=0&&nums[0]>target){
                break;
            }
            // 去重
            if(i>0&&nums[i]==nums[i-1]){
                continue;
            }
            for(int j=i+1;j<nums.size();j++){
                // 剪枝
                if(nums[i]+nums[j]>target&&nums[j]>=0){
                    break;
                }
                // 去重
                if(j>i+1&&nums[j]==nums[j-1]){
                    continue;
                }
                // 類(lèi)似于三數(shù)之和
                int begin = j+1;
                int end = nums.size()-1;
                while(begin<end){
                    if((long) nums[i]+nums[j]+nums[begin]+nums[end]==target){
                        // 找到符合要求的數(shù)組，記錄
                        result.push_back({nums[i],nums[j],nums[begin],nums[end]});
                        while(begin<end&&nums[begin]==nums[begin+1]){
                            begin++;
                        }
                        while(begin<end&&nums[end]==nums[end-1]){
                            end--;
                        }
                        begin++;
                        end--;
                    }
                    else if((long)nums[i]+nums[j]+nums[begin]+nums[end]>target){
                        end--;
                    }
                    else{
                        begin++;
                    }
                }
            }
        }
        return result;
    }
};

文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-826232.html

到了這里，關(guān)于C++數(shù)據(jù)結(jié)構(gòu)與算法——哈希表的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！