代码随想录day6 || 哈希表1

更新于2024-12-26|编程训练

|字数总计:2.9k|阅读时长:11分钟|阅读量:

哈希表理论基础

目的：快速判断一个元素是否出现集合里
常见的三种哈希结构
数组、set （集合）、map(映射)
（偷懒直接截图了）

242.有效的字母异位词

题目链接
状态：两遍过
错误原因：为考虑两字符串长度不同可直接返回false
思路：之前在《904. 水果成篮》中学到的unordered_map可直接用

class Solution {
public:
    bool isAnagram(string s, string t) {
        int m = s.size(), n = t.size();
        if (m != n) return false;//第一次未考虑到
        unordered_map<char, int> ans;
        for (int i = 0; i < m; i++) ans[s[i]]++;
        for (int j = 0; j < n; j++)
            if (--ans[t[j]] < 0)
                return false;
        return true;
    }
};

有更高级写法可以学习借鉴

for (char i : s)  // 遍历字符串 s，统计其中每个字符出现的次数，并将其存储在 map1 中
    ans[i]++;
for (char i : t)  // 遍历字符串 t，对于其中的每个字符，减少其在 map1 中的计数器
    ans[i]--;
for (auto it : ans) {  // 遍历 map1 中的所有键值对
    if (it.second != 0) {  // 如果有任何一个键值对的值不为零，则表示两个字符串不互为字谜，返回 false
        return false;

答案还有一种暴力排序做的

class Solution {
public:
    bool isAnagram(string s, string t) {  // 定义 isAnagram 方法，接受两个字符串参数
        if(s.length()!=t.length())  // 如果两个字符串的长度不同，直接返回 false，它们不可能互为字谜
            return false;
        sort(s.begin(),s.end());  // 对字符串 s 进行排序
        sort(t.begin(),t.end());  // 对字符串 t 进行排序
        return s==t;  // 返回字符串 s 和 t 是否完全相同
    }
};

相关题目

383. 赎金信

题目链接
思路一样，甚至无需比较

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        unordered_map<char, int> ans;
        for (char i :magazine) ans[i]++;
        for (char j :ransomNote)
            if (--ans[j] < 0)
                return false;
        return true;

    }
};

49. 字母异位词分组

题目链接
状态：难，没做出来
思路：很复杂，
答案思路参考：

两个字符串互为字母异位词，当且仅当两个字符串包含的字母相同。同一组字母异位词中的字符串具备相同点，可以使用相同点作为一组字母异位词的标志，使用哈希表存储每一组字母异位词，哈希表的键为一组字母异位词的标志，哈希表的值为一组字母异位词列表。

遍历每个字符串，对于每个字符串，得到该字符串所在的一组字母异位词的标志，将当前字符串加入该组字母异位词的列表中。遍历全部字符串之后，哈希表中的每个键值对即为一组字母异位词。

官方题解

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> mp;
        for (string& str: strs) {
        	//string& str 的使用是为了提高效率，避免在每次迭代中复制字符串，从而减少内存和时间开销。
            string key = str;
            sort(key.begin(), key.end());
            mp[key].emplace_back(str);
            //push_back：需要先构造一个临时对象，然后将其拷贝或移动到容器中。对于非平凡构造（例如自定义类的对象），这意味着需要额外的构造和析构开销。
			//emplace_back：直接在容器末尾构造对象，避免了临时对象的创建和销毁，通常比 push_back 更高效。
        }
        vector<vector<string>> ans;
        for (auto it = mp.begin(); it != mp.end(); ++it) {
            ans.emplace_back(it->second);
            //每个元素（键值对）包含两个部分：键（first）和值（second）。
            //it->first：返回当前迭代器 it 指向元素的键.
            //it->second：返回当前迭代器 it 指向元素的值。
        }
        return ans;
    }
};

思路二：使用哈希表
思路：使用长度为 26 的数组记录每个字母出现的次数，这也是我最开始想要使用的思路，奈何水平不够，没整理出来。

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string> &strs) {
        unordered_map<string, vector<string>> m;
        for (auto &s : strs) {
            string sorted_s = s;
            ranges::sort(sorted_s);
            m[sorted_s].push_back(s); // sorted_s 相同的字符串分到同一组
        }
        vector<vector<string>> ans;
        ans.reserve(m.size()); // 预分配空间
        for (auto &[_, value] : m) {
            ans.push_back(value);
        }
        return ans;
    }
};

438. 找到字符串中所有字母异位词

题目链接
状态：超时
思路：暴力直接将p字符串排序后放到map中，在从s字符串中依次取p长度的子字符串，排序后和map中的比较，若相同返回下标索引，反之继续。
初始超时代码：

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int m = s.size(), n = p.size();
        unordered_map<string, int> mp;
        vector<int> res;
        string sub;
        sort(p.begin(),p.end());
        mp[p]++;
        for (int j = 0; j < m - n + 1; j++) {
            sub = s.substr(j, n);
            sort(sub.begin(),sub.end());
            if (mp[sub] != 0)
                res.push_back(j);
        }
        return res;
    }
};

修改版：使用滑动窗口

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int m = s.size(), n = p.size();
        if (m < n)
            return {};
        unordered_map<char, int> mp_s, mp_p;
        vector<int> res;
        for (char i : p)
            mp_p[i]++;
        for (int j = 0; j < n; j++) {
            mp_s[s[j]]++;
        }
        // 滑动窗口
        if (mp_s == mp_p)
            res.push_back(0);
        for (int i = 0, j = n; j < m; i++, j++) {
            mp_s[s[j]]++;           // 增加滑动窗口右边界字符的频率
            if (--mp_s[s[i]] == 0)  // 减少滑动窗口左边界字符的频率
                mp_s.erase(s[i]);   // 如果频率为零，删除该字符
            if (mp_s == mp_p) res.push_back(i + 1);
        }
        return res;
    }
};

忽然发现 unordered_map 好像没什么用，下附一个关于滑动窗口的链接，学完后无敌
滑动窗口

349. 两个数组的交集

题目链接
状态：错一次
错误原因：未考虑返回数组不重复问题
思路：用哈希表先记录一个数组的元素，个数统一为一，再遍历第二个数组，若哈希表里已有则将个数置0，并加入到返回向量中。

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int,int> ans;
        vector<int> res;
        for(int i:nums1) ans[i]=1;
        for(int j:nums2)
            if(ans[j]==1){
                ans[j]=0;
                res.push_back(j);
            }     
        return res;
    }
};

看了标准答案，和他思路一样不过写法我的好像更好一点
下面的答案值得学习

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result_set; // 存放结果，之所以用set是为了给结果集去重
        unordered_set<int> nums_set(nums1.begin(), nums1.end());
        for (int num : nums2) {
            // 发现nums2的元素 在nums_set里又出现过
            if (nums_set.find(num) != nums_set.end()) {
                result_set.insert(num);
            }
        }
        return vector<int>(result_set.begin(), result_set.end());
    }
};
//当使用 end() 函数时，它并不指向任何有效的元素，而是表示迭代器已经遍历完容器内的所有元素。
//在 unordered_set 的上下文中，由于它是无序的，end() 并不指向一个特定的元素，它仅仅是一个用来表示遍历结束的迭代器。
//在代码中，nums_set.find(num) != nums_set.end() 这行检查 find 函数返回的迭代器是否不等于 end()。
//如果 find 函数找到了元素 num，它将返回指向该元素的迭代器；如果没有找到，它将返回 end()。这个检查用于确定元素是否存在于 nums_set 中。

在这个问题中，使用 unordered_set 而不是 unordered_map 主要基于以下原因：

需求: 问题要求找出两个数组的交集，即找到在两个数组中都存在的元素。这不需要存储任何额外的信息，只需要知道某个元素是否存在。
性能: unordered_set 提供平均常数时间复杂度的查找性能，这使得它非常适合快速检查元素是否存在。
简洁性: 使用 unordered_set 可以避免不必要的复杂性。unordered_map 存储键值对，而在这个场景中，我们不需要存储任何值，只需要知道元素是否存在。
内存使用: unordered_set 只存储元素本身，而 unordered_map 需要额外的空间来存储与每个键关联的值（在这个场景中，值是不必要的）。
实现简单性: 使用 unordered_set 可以简化代码实现，因为不需要处理键值对，只需要处理单个元素。
自动去重: unordered_set 会自动去除重复元素，这正是寻找两个数组交集所需要的特性。
直接使用: unordered_set 可以直接使用 insert 或 emplace 方法添加元素，并利用 count 或 find 方法检查元素是否存在。
转换方便: 最终结果需要转换为 vector，而 unordered_set 可以直接转换为 vector，因为集合中的元素已经是排序好的。

使用 unordered_map 在这个场景下可能会引入不必要的复杂性和性能开销，因为 unordered_map 需要额外的内存来存储值，并且在每次查找时都需要处理键值对，这在只需要检查元素存在性的情况下是不必要的。

202. 快乐数

题目链接
状态：错两次
错误原因：1. 未考虑无限循环。2. set.find(num) != set.end()理解出错，应为重复出现而不是未出现
初始代码：

class Solution {
public:
    int func(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) {
            n = func(n);
            if(n==1) break;
            if (set.find(n) != set.end())
                return false;
            else
                set.insert(n);
        }
        return true;
    }
};

改进写法：

bool isHappy(int n) {
        unordered_set<int> set;
        while (true) {
            n = func(n);
            if (n == 1) return true; // 如果 n 变为 1，这是一个快乐数
            auto result = set.insert(n).second; // 尝试插入 n 并获取插入成功与否的状态
            if (!result) return false; // 如果插入失败，说明 n 已经出现过，返回 false
        }
    }

insert 函数的返回值是一个 pair 类型，其中：

pair::first 是一个迭代器，指向集合中的元素，如果插入成功，它指向新插入的元素；如果元素已存在，则指向已存在的元素。
pair::second 是一个布尔值，表示插入操作是否成功。如果 second 为 true，则表示元素被成功插入；如果为 false，则表示元素已存在，没有执行插入操作。

1. 两数之和

题目链接
状态：只想到了暴力方法

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n=nums.size();
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(nums[i]+nums[j]==target)
                    return {i,j};
            }
        }
        return {0};
    }
};

重点：当需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。本题需要一个集合来存放遍历过的元素，然后在遍历数组的时候去询问这个集合，某元素是否遍历过，也就是是否出现在这个集合。

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 {};
    }
};

理解：就遍历一个$nums[i]$，就在哈希表中找他相对应加和为$target$ 的数 $target-nums[i]$ ，若有则返回，否则添加进去。

代码随想录day6 || 哈希表1

http://blog.jxlll.cc/2024/07/08/代码随想录算法训练营第六天 _哈希表1/

作者

JJxXxLL

发布于

2024-07-08

更新于

2024-12-26

许可协议

CC BY-NC-SA 4.0

相关推荐

代码随想录day7 || 哈希表2

数据库加载中