目录
unordered_map
LeeCode242. Valid Anagram
梦的开始:LeeCode1. Two Sum
unordered_set
LeeCode349. Intersection of Two Arrays
LeeCode202. Happy Number
C++中的unordered_map
和unordered_set
是标准库中提供的两种容器,用于实现哈希表(Hash Table)数据结构。它们提供了高效的查找、插入和删除操作,适用于需要快速访问和操作元素的场景。
-
unordered_map
:
-
unordered_map
是一种关联容器,用于存储键值对(key-value pairs)。
- 它基于哈希表实现,具有快速的查找性能,平均时间复杂度为O(1)。
- 每个键值对称为一个元素,通过键进行唯一标识和访问。
- 键和值可以是任意类型,但键必须是可哈希化的(具有哈希函数)。
-
unordered_map
提供了插入、删除、查找元素的操作,以及迭代器进行遍历操作。
-
unordered_set
:
-
unordered_set
是一种集合容器,用于存储唯一的元素集合。
- 它基于哈希表实现,具有快速的查找性能,平均时间复杂度为O(1)。
- 每个元素在集合中是唯一的,重复的插入将被忽略。
- 元素的类型必须是可哈希化的(具有哈希函数)。
-
unordered_set
提供了插入、删除、查找元素的操作,以及迭代器进行遍历操作。
unordered_map
LeeCode242. Valid Anagram
题目地址:力扣
题目类型:哈希映射
思路:
- 首先用哈希映射存储字符串s中每个char的个数
- 遍历字符串t
- 最后判断s的char是否被全部使用
class Solution {
public:
bool isAnagram(string s, string t) {
unordered_map<char, int> ma;
// 用来存储s中所有char的个数
for (char c : s) {
ma[c]++;
}
// 判断t中是否有s中未出现的char
for (char c : t) {
if (ma[c] == 0) return false;
ma[c]--;
}
// 判断是否所有元素都用完了
for (auto it : ma) {
if (it.second != 0) return false;
}
return true;
}
};
梦的开始:LeeCode1. Two Sum
题目地址:力扣
题目类型:哈希映射
思路:构造哈希map,一次遍历nums,每次都将target - nums[i]放入map中,之后若出现某个nums[j]出现在map中,则说明找到了。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> ma;
for (int i = 0; i < nums.size(); ++i) {
auto it = ma.find(nums[i]);
if (it != ma.end()) return {it->second, i};
ma[target - nums[i]] = i;
}
return {};
}
};
unordered_set
LeeCode349. Intersection of Two Arrays
题目地址:力扣
题目类型:哈希set
思路:
- 将nums1中出现的所有char存入unordered_set中
- 依次遍历nums2,看有哪些char在两个数组中同时出现
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> seen;
vector<int> res;
for (auto it : nums1) {
seen.insert(it);
}
for (auto it : nums2) {
if (seen.count(it)) {
res.emplace_back(it);
seen.erase(it);
}
}
return res;
}
};
LeeCode202. Happy Number
题目地址:力扣
题目类型:哈希set
思路:当n不等与1时,一直遍历下去,并且要将每次的n存入到哈希set中;
停止遍历的条件:n==1 或者 哈希set中出现了已经存入的元素,说名此时形成了死循环
class Solution {
private:
int happy(int n) {
int sum = 0;
while (n) {
sum += (n % 10) * (n % 10);
n /= 10;
}
return sum;
}
public:
bool isHappy(int n) {
unordered_set<int> seen;
while (n != 1) {
// 如果seen中能够找到,则说明陷入循环,直接返回false
if (seen.count(n)) return false;
seen.insert(n);
n = happy(n);
}
return true;
}
};