代码随想录算法训练营day6（哈希表）

代码随想录算法训练营day6（哈希表）：

学习内容：

哈希表基础内容：
哈希表
定义：哈希表是根据关键码的值而直接进行访问的数据结构
目的：一般哈希表都是用来快速判断一个元素是否出现集合里。

哈希函数
定义：通过hashCode把名字转化为数值，一般hashcode是通过特定编码方式，可以将其他数据格式转化为不同的数值。

哈希碰撞
定义：不同元素被哈希函数索引到同一Index.
解决方式：拉链法（同一索引后接链表）；线性探测法（需要targetsize>datasize）

常见的三种哈希结构：
数组；
set(集合)；
map(映射)。

1. std::vector
   std::vector是动态数组，可以自动扩展大小，适合需要频繁添加和删除元素的场景。

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec = {1, 2, 3};

    // 访问元素
    std::cout << "Element at index 0: " << vec[0] << std::endl;

    // 添加元素
    vec.push_back(4);
    vec.insert(vec.begin() + 1, 5); // 在索引1位置插入元素5

    // 删除元素
    vec.erase(vec.begin() + 2); // 删除索引2处的元素
    vec.pop_back(); // 删除最后一个元素

    // 遍历元素
    for(int i : vec) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    return 0;
}

2. std::set
   std::set是有序集合，内部实现为红黑树，适用于需要快速查找和排序的场景。

#include <iostream>
#include <set>

int main() {
    std::set<int> s = {3, 1, 2};//会自动排序!

    // 添加元素
    s.insert(4);

    // 删除元素
    s.erase(2);

    // 查找元素
    if (s.find(3) != s.end()) {
        std::cout << "Element 3 found" << std::endl;
    }

    // 遍历元素
    for(int i : s) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    return 0;
}

3. std::unordered_set
   std::unordered_set是无序集合，内部实现为哈希表，适用于需要快速查找和唯一性保证的场景。

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> us = {3, 1, 2};

    // 添加元素
    us.insert(4);

    // 删除元素
    us.erase(2);

    // 查找元素
    if (us.find(3) != us.end()) {
        std::cout << "Element 3 found" << std::endl;
    }

    // 遍历元素
    for(int i : us) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    return 0;
}

4. std::map
   std::map是有序映射，内部实现为红黑树，适用于需要按键排序和快速查找键值对的场景。

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> m;

    // 添加键值对
    m[1] = "one";
    m[2] = "two";

    // 更新键值对
    m[1] = "uno";

    // 删除键值对
    m.erase(2);

    // 查找键值对
    if (m.find(1) != m.end()) {
        std::cout << "Key 1 found with value: " << m[1] << std::endl;
    }

    // 遍历键值对
    for(const auto& kv : m) {//const auto& kv
//const：表示kv是一个常量引用，遍历过程中不会修改容器中的元素。
//auto：让编译器自动推导kv的类型。在std::unordered_map<int, std::string>中，kv的实际类型是std::pair<const int, std::string>。
//&：表示kv是一个引用。使用引用可以避免复制每个元素，提高性能。

        std::cout << kv.first << ": " << kv.second << std::endl;
    }

    return 0;
}

5. std::unordered_map
   std::unordered_map是无序映射，内部实现为哈希表，适用于需要快速查找键值对的场景。

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, std::string> um;

    // 添加键值对
    um[1] = "one";
    um[2] = "two";

    // 更新键值对
    um[1] = "uno";

    // 删除键值对
    um.erase(2);

    // 查找键值对
    if (um.find(1) != um.end()) {
        std::cout << "Key 1 found with value: " << um[1] << std::endl;
    }

    // 遍历键值对
    for(const auto& kv : um) {
        std::cout << kv.first << ": " << kv.second << std::endl;
    }

    return 0;
}

总结
std::vector：动态数组，适合需要频繁添加和删除元素的场景。
std::set：有序集合，适合需要排序和快速查找的场景。
std::unordered_set：无序集合，适合需要快速查找和唯一性保证的场景。
std::map：有序映射，适合需要按键排序和快速查找键值对的场景。
std::unordered_map：无序映射，适合需要快速查找键值对的场景。

std::multiset
std::multiset是允许重复元素的有序集合，内部实现通常为红黑树。适用于需要存储有序的、多重的（允许重复）元素的场景。

#include <iostream>
#include <set>

int main() {
    std::multiset<int> ms = {3, 1, 2, 2};

    // 添加元素
    ms.insert(4);
    ms.insert(2); // 允许重复元素，set会从小到大排列

    // 删除元素
    ms.erase(ms.find(2)); // 只删除一个匹配的元素
    ms.erase(3); // 删除所有匹配的元素

    // 查找元素
    auto it = ms.find(2);
    if (it != ms.end()) {
        std::cout << "Element 2 found" << std::endl;
    }

    // 遍历元素
    for(int i : ms) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    return 0;
}

std::multimap
std::multimap是允许重复键的有序映射，内部实现通常为红黑树。适用于需要存储有序的、多重的（允许重复键）键值对的场景。

#include <iostream>
#include <map>

int main() {
    std::multimap<int, std::string> mm;

    // 添加键值对
    mm.insert({1, "one"});
    mm.insert({2, "two"});
    mm.insert({1, "uno"}); // 允许重复键

    // 删除键值对
    mm.erase(mm.find(1)); // 只删除一个匹配的键值对

    // 查找键值对
    auto range = mm.equal_range(1);
    for(auto it = range.first; it != range.second; ++it) {
        std::cout << "Key 1 found with value: " << it->second << std::endl;
    }

    // 遍历键值对
    for(const auto& kv : mm) {
        std::cout << kv.first << ": " << kv.second << std::endl;
    }

    return 0;
}

总结
std::multiset：有序多重集合，允许重复元素，适合需要有序且允许重复的场景。
std::multimap：有序多重映射，允许重复键，适合需要有序且允许重复键值对的场景。
常见操作总结
std::multiset
添加元素：ms.insert(value);
删除元素：ms.erase(value); 或 ms.erase(iterator);
查找元素：auto it = ms.find(value);
遍历元素：for (const auto& value : ms) { /* … / }
std::multimap
添加键值对：mm.insert({key, value});
删除键值对：mm.erase(key); 或 mm.erase(iterator);
查找键值对：auto it = mm.find(key);
范围查找：auto range = mm.equal_range(key);
遍历键值对：for (const auto& kv : mm) { / … */ }

来看看今天的题：

学习产出：

242:
直接把两个字符串转成vector，再排序比较

class Solution {
public:
    bool isAnagram(string s, string t) {
    if (s.size() != t.size()) {
        return false; // 如果两个字符串长度不相等，直接返回false
    }
    
    // 将字符串转换为向量并排序
    std::vector<char> vec_s(s.begin(), s.end());
    std::vector<char> vec_t(t.begin(), t.end());
    
    std::sort(vec_s.begin(), vec_s.end());
    std::sort(vec_t.begin(), vec_t.end());
    
    // 比较排序后的向量
    return vec_s == vec_t;
    }
};

官方给的更标准，把字符映射到数组也就是哈希表的索引下标上，因为字符a到字符z的ASCII是26个连续的数值，所以字符a映射为下标0，相应的字符z映射为下标25。
再遍历 字符串s的时候，只需要将 s[i] - ‘a’ 所在的元素做+1 操作即可，并不需要记住字符a的ASCII，只要求出一个相对数值就可以了。ASCII（American Standard Code for Information Interchange）是一种字符编码标准，每个字符对应一个唯一的整数值。比如，字符’a’的ASCII码是97，字符’b’的ASCII码是98，依此类推，字符’z’的ASCII码是122。这种相对数值表示法可以将字母’a’到’z’映射到0到25之间的整数。同样在遍历字符串t的时候，对t中出现的字符映射哈希表索引上的数值再做-1的操作。那么最后检查一下，record数组如果有的元素不为零0，说明字符串s和t一定是谁多了字符或者谁少了字符，return false。最后如果record数组所有元素都为零0，说明字符串s和t是字母异位词，return true。

class Solution {
public:
    bool isAnagram(string s, string t) {
        int record[26] = {0};
        for (int i = 0; i < s.size(); i++) {
            // 并不需要记住字符a的ASCII，只要求出一个相对数值就可以了
            record[s[i] - 'a']++;
        }
        for (int i = 0; i < t.size(); i++) {
            record[t[i] - 'a']--;
        }
        for (int i = 0; i < 26; i++) {
            if (record[i] != 0) {
                // record数组如果有的元素不为零0，说明字符串s和t 一定是谁多了字符或者谁少了字符。
                return false;
            }
        }
        // record数组所有元素都为零0，说明字符串s和t是字母异位词
        return true;
    }
};

我的方法是创建多个容器，因为需要查找，所以multiset这个容器比较方便查找且允许重复元素（将两个vector转换为multiset）；输出我们暂定一个unordered_set，因为它不允许重复，最后再转换成vector输出。
看不懂的话需要对各种容器的常规操作来复习，比如遍历、查找、增加元素。

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        multiset<int>set_nums1(nums1.begin(),nums1.end());
        multiset<int>set_nums2(nums2.begin(),nums2.end());
        if(set_nums1.size()>set_nums2.size()){
            swap(set_nums1,set_nums2);
        }
        unordered_set<int>output;
        for(int i:set_nums1){
            auto it=set_nums2.find(i);
            if(it!=set_nums2.end()){
                output.insert(i);     
            }

        }
        vector<int>output_final(output.begin(),output.end());
        return output_final;
    }
};

题目中说了会 无限循环，那么也就是说求和的过程中，sum会重复出现，这对解题很重要！所以这道题目使用哈希法，来判断这个sum是否重复出现，如果重复了就是return false， 否则一直找到sum为1为止。判断sum是否重复出现就可以使用unordered_set。
我的方法是把n转成字符，这样可以比较好分开个位、十位、百位…（字符型1234在遍历时会分别读取1、2、3、4），存进一个multiset里。设置一个无重复变量的unordered_set用于记录出现过的数。

class Solution {
public:
    bool isHappy(int n) {
        string n1=to_string(n);//转成字符串
        multiset<char>nums(n1.begin(),n1.end());//字符型multiset
        int sum=0;
        unordered_set<int>record={};
        while(1){
            for(char i:nums){
                int num=i-'0';//0-9的ASCII是连续的，可以由此创建int
                sum+=num*num;
            }
            auto it=record.find(sum);
            if(sum==1){
                return true;
            }else if(it!=record.end()){
                return false;
            }else{
                record.insert(sum);
                nums.clear();//清空nums
                string sum1=to_string(sum);
                nums.insert(sum1.begin(),sum1.end());//更新为新的数
                sum=0;
            }

        }
    }
};

官方解法：

class Solution {
public:
    // 取数值各个位上的单数之和
    int getSum(int n) {
        int sum = 0;
        while (n) {
            sum += (n % 10) * (n % 10);
            n /= 10;
        }
        return sum;
    }
    bool isHappy(int n) {
        unordered_set<int> set;
        while(1) {
            int sum = getSum(n);
            if (sum == 1) {
                return true;
            }
            // 如果这个sum曾经出现过，说明已经陷入了无限循环了，立刻return false
            if (set.find(sum) != set.end()) {
                return false;
            } else {
                set.insert(sum);
            }
            n = sum;
        }
    }
};

我的方法是把向量转换为multiset,逐个排查。如果target减去第一个数的得数可以被查找到就说明找到了这对组成target的对，记得找的时候要从multiset删除正在判定的元素，不然如果该数正好是target一半的话会有判定问题（因为自己和另一个值一样，会肯定被识别到存在，比如【3，2，4】，target=6；本会在识别到3是就退出查找）。找到对子后就回到向量定位即可。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        multiset<int>ms(nums.begin(),nums.end());
        for(int j:ms){
            ms.erase(ms.find(j));
            auto it = ms.find(target-j);
            if(it!=ms.end()){
                vector<int>out;
                for(int i=0;i<nums.size();i++){
                    if(nums[i]==j){
                        out.push_back(i);
                    }else if(nums[i]==target-j){
                        out.push_back(i);
                    }
                    if(out.size()==2){
                        return out;
                    }
                
                }
            }
        }
        return {};
    }
};

官方解答：是用map做的，更简单方便，不用再回到向量找索引了。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        std::unordered_map <int,int> map;
        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};
            }
            // 如果没找到匹配对，就把访问过的元素和下标加入到map中
            map.insert(pair<int, int>(nums[i], i)); 
        }
        return {};
    }
};