哈希表记录

啥是哈希表？

我自己这么跟自己讲的，把目标物品们放入各自的不同箱子中记录了不同种箱子里的物品数量

第一道题

我写的代码（一开始用的容器储存）

#include <string> using namespace std; class Solution { public: bool isAnagram(string s, string t) { // 边界条件：长度不同直接返回false if (s.length() != t.length()) { return false; } int count[26] = {0}; // 统计字符出现次数 int n = s.length(); // 统计s中字符出现次数 for (int i = 0; i < n; i++) { count[s[i] - 'a']++; } // 抵消t中字符出现次数 for (int i = 0; i < n; i++) { count[t[i] - 'a']--; } // 检查所有计数是否归零 for (int i = 0; i < 26; i++) { if (count[i] != 0) { return false; } } return true; } };

第二道题

学习STL中的map

一、map是什么？

• 本质：基于红黑树的有序键值对容器（自动按Key升序排序）。
• 特点：
  • 键Key唯一，值Value可重复。
  • 插入/删除/查找时间复杂度：O(log n)。
  • 头文件：#include <map>。

二、核心操作

1.声明与初始化

#include <map> using namespace std; map<int, string> m1; // 空map map<string, int> m2 = {{"A", 1}, {"B", 2}}; // 初始化

2.插入元素

m1[101] = "Alice"; // 方法1：下标操作（自动插入） m1.insert({102, "Bob"}); // 方法2：insert（键不存在时插入） m1.emplace(103, "Charlie"); // 方法3：emplace（高效构造）

3.查找元素

// 安全查找（推荐） if (m1.find(102) != m1.end()) { cout << "Found: " << m1[102] << endl; } // 快速检查存在性 if (m1.count(102)) { /* ... */ }

4.删除元素

m1.erase(101); // 按Key删除 auto it = m1.find(102); if (it != m1.end()) m1.erase(it); // 按迭代器删除

5.遍历元素

// 方法1：迭代器 for (auto it = m1.begin(); it != m1.end(); ++it) { cout << it->first << ": " << it->second << endl; } // 方法2：范围循环（C++11） for (const auto& [id, name] : m1) { // 结构化绑定 cout << id << ": " << name << endl; }

自定义排序规则

• 默认按Key升序，可通过自定义比较函数修改：

struct Descending { bool operator()(int a, int b) const { return a > b; } }; map<int, string, Descending> descMap;

然而说到哈希表就不得不提unordered_map（无序）

题解中体现操作

#include <bits/stdc++.h> using namespace std; // 定义一个函数用于对字母异位词进行分组 vector<vector<string>> groupAnagrams(vector<string>& strs) { // 创建一个 unordered_map，键为排序后的字符串，值为包含字母异位词的向量 unordered_map<string, vector<string>> anagramGroups; // 遍历输入的字符串向量 for (const auto& str : strs) { // 复制当前字符串，避免修改原始字符串 string sortedStr = str; // 对复制的字符串进行排序 sort(sortedStr.begin(), sortedStr.end()); // 如果排序后的字符串已经在 unordered_map 中，将原始字符串添加到对应的向量中 // 如果不在，会自动创建一个新的键值对 anagramGroups[sortedStr].push_back(str); } // 创建一个二维向量来存储最终的分组结果 vector<vector<string>> result; // 遍历 unordered_map for (const auto& pair : anagramGroups) { // 将每个键对应的值（即一组字母异位词）添加到结果向量中 result.push_back(pair.second); } return result; } int main() { // 定义一个包含多个字符串的向量 vector<string> strs = {"eat", "tea", "tan", "ate", "nat", "bat"}; // 调用 groupAnagrams 函数进行分组 vector<vector<string>> groupedAnagrams = groupAnagrams(strs); // 输出分组结果 for (const auto& group : groupedAnagrams) { cout << "Group: "; for (const auto& str : group) { cout << str << " "; } cout << std::endl; } return 0; }

上课了