【数据结构与算法】LeetCode：哈希表
文章目录
- 哈希表
- 一般查找 (键查找)
- 两数之和 (Hot 100)
- 两个数组的交集
- 快乐数
- 环形链表 （Hot 100）
- 环形链表 II （Hot 100）
- 和为 K 的子数组 (Hot 100)
- 计数查找 (值查找)
- 有效的字母异位词
- 字符串中的第一个唯一字符
- 只出现一次的数字 (Hot 100)
- 多数元素
- 键、值查找
- 两个数组的交集 II
- 其他
- 字母异位词分组
- 最长连续序列
- LRU 缓存 (Hot 100)
- 复制带随机指针的链表
哈希表
一般查找 (键查找)
两数之和 (Hot 100)
两数之和
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> map; // <数值,下标>
for(int i = 0; i < nums.size(); i++){ // 对于每个数字nums[i]
auto it = map.find(target - nums[i]); // 查找target - nums[i]
if(it != map.end()){
return {it->second, i}; // {target - nums[i]的索引，nums[i]的索引}
}
map[nums[i]] = i;
}
return {};
}
};
两个数组的交集
两个数组的交集
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> result;
// num1的元素集合
unordered_set<int> nums1_set(nums1.begin(), nums1.end());
for(auto num:nums2){ // 找出nums2在nums1中出现的元素
if (nums1_set.count(num)){
result.insert(num);
}
}
return vector<int>(result.begin(), result.end());
}
};
快乐数
快乐数
class Solution {
public:
// 计算一个数的各位数字的平方和
int getSquareSum(int n) {
int sum = 0;
while (n > 0) {
int digit = n % 10;
sum += digit * digit;
n /= 10;
}
return sum;
}
// 判断一个数是否为快乐数
bool isHappy(int n) {
std::unordered_set<int> seen; // 使用集合来存储已经出现过的数
while (n != 1 && !seen.count(n)){ // 当 n 不为 1 且 n 没有出现过时
seen.insert(n);
n = getSquareSum(n);
}
return n == 1; // 如果 n 最终为 1，则为快乐数
}
};
环形链表 （Hot 100）
环形链表
class Solution {
public:
bool hasCycle(ListNode *head) {
unordered_set<ListNode*> visited;
ListNode * cur = head;
while (cur != nullptr) {
if (visited.count(cur)) {
return true;
}
visited.insert(cur);
cur = cur->next;
}
return false;
}
};
环形链表 II （Hot 100）
环形链表 II
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
unordered_set<ListNode *> visited;
ListNode* cur = head;
while (cur != nullptr) {// 遍历链表中的每个节点，并将它记录下来
if (visited.count(cur)) { // 一旦遇到了此前遍历过的节点，就可以判定链表中存在环。
return cur;
}
visited.insert(cur);
cur = cur->next;
}
return nullptr;
}
};
和为 K 的子数组 (Hot 100)
和为 K 的子数组
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int ans = 0;
int pre = 0; // 前缀和，子数组[num[j]..num[i]] 和为k 即 pre[i]−pre[j−1]==k
unordered_map<int, int> map_pre_num; // 存储每个前缀和出现的次数。
map_pre_num[0] = 1;
for (auto& num : nums) {
pre += num; // 计算前缀和
// 判断是否已存在pre - k的前缀和，
// 如果存在，说明之前有map_pre_num[pre - k]个位置到当前位置的连续子数组的和为k
if (map_pre_num.find(pre - k) != map_pre_num.end()) {
ans += map_pre_num[pre - k];
}
map_pre_num[pre]++;
}
return ans;
}
};
计数查找 (值查找)
有效的字母异位词
有效的字母异位词（计数对象可数）
class Solution {
public:
bool isAnagram(string s, string t) {
// 使用哈希表来统计两个字符串各个字符出现次数的差值。
// 如果差值都为0，则为字母异位词
// map需要更多的开销，因此优先使用数组
vector<int>vec(26,0);
for(auto c: s) vec[c - 'a']++;
for(auto c: t) vec[c - 'a']--;
// 查找数量不同的字母，有则表示s和t不是字母异位词
for (auto t: vec){
if(t!=0) return false;
}
return true;
}
};
字符串中的第一个唯一字符
字符串中的第一个唯一字符（计数对象可数）：
class Solution {
public:
int firstUniqChar(string s) {
std::unordered_map<char, int> map;
// 统计每个字符的出现次数
for (char c : s) map[c]++;
// 遍历字符串，找到第一个只出现一次的字符
for (int i = 0; i < s.size(); i++) {
if (map[s[i]] == 1) return i;
}
return -1;
}
};
只出现一次的数字 (Hot 100)
只出现一次的数字（计数对象不可数）：
class Solution {
public:
int singleNumber(vector<int>& nums) {
unordered_map<int, int> map;
// 统计每个字符的出现次数
for (int num : nums) {
map[num]++;
}
// 查找只出现一次的元素
for(auto item: map){
if(item.second == 1) return item.first;
}
return NULL;
}
};
多数元素
多数元素
class Solution {
public:
int majorityElement(vector<int>& nums) {
unordered_map<int, int> counts;
int ans = 0, max_count = 0;
for (int num: nums) {
counts[num]++;
if (counts[num] > max_count) { // 查找最多的数
ans = num;
max_count = counts[num];
}
}
return ans;
}
};
键、值查找
两个数组的交集 II
两个数组的交集 II
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int, int> map;
vector<int> result; // 元素可重复
// 记录nums1每个元素出现的次数
for (int num : nums1) map[num]++;
// 遍历 nums2，如果元素在哈希表中且计数大于零，则添加到结果集中并减少计数
// 第一个条件（键）：检查 num 是否存在于哈希表 map 中
// 第二个条件（值）：确保只将在 nums1 中出现过（即计数大于零）的元素添加到结果集中，
for (int num : nums2) {
if (map.find(num) != map.end() && map[num] > 0) {
result.push_back(num);
map[num]--; // 确保各个元素添加的次数不超过它们在 nums1 中出现次数
}
}
return result;
}
};
其他
字母异位词分组
字母异位词分组
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> mp;
// 不同词排序后的字母集是相同的，设为键。字母组成相同的词设为值。
for (string& str: strs) {
string key = str;
sort(key.begin(), key.end()); // 字母集
mp[key].emplace_back(str); // <字母集,词>
}
vector<vector<string>> ans;
for (auto it: mp) {
ans.emplace_back(it.second);
}
return ans;
}
};
最长连续序列
最长连续序列
class Solution{
public:
int longestConsecutive(vector<int>& nums){
unordered_set<int> set;
for(auto num:nums) set.insert(num);
int max_length = 0;
for(auto num: set){
if(!set.count(num - 1)){ // 最长连续序列的开头值（最小值）x
int cur_length = 1;
// 以x为起点，不断尝试匹配 x+1,x+2,⋯ 是否存在
while(set.count(num+1)){
num++;
cur_length++;
}
max_length = max(max_length, cur_length);
}
}
return max_length;
}
};
LRU 缓存 (Hot 100)
LRU 缓存
struct DlinkedNode{
int key, value;
DlinkedNode* prev;
DlinkedNode* next;
DlinkedNode(int _key = 0, int _value = 0 ): key(_key),value(_value), prev(nullptr),next(nullptr){};
};
class LRUCache {
private:
unordered_map<int, DlinkedNode*> cache;
DlinkedNode* head; // 伪头
DlinkedNode* tail; // 伪尾
int size = 0; // 当前缓存的节点数量
int capacity; // 容量
public:
LRUCache(int _capacity):capacity(_capacity) {
// 伪头部和伪尾部节点
head = new DlinkedNode();
tail = new DlinkedNode();
head->next = tail;
tail->prev = head;
}
~LRUCache() {
// 析构函数，清理资源
DlinkedNode* curr = head->next;
while (curr != tail) {
DlinkedNode* temp = curr;
curr = curr->next;
delete temp;
}
delete head;
delete tail;
}
void put(int key, int value) {
// 如果关键字 key 不存在，则向缓存中插入该组 key-value 。
// 如果插入操作导致关键字数量超过 capacity ，则应该逐出最久未使用的关键字。
if(!cache.count(key)){
DlinkedNode* node = new DlinkedNode(key, value);
cache[key] = node;
addToHead(node);
size++;
if(size > capacity) removeTail();
}else{ // 如果关键字 key 已经存在，则变更其数据值 value,并移动到头部
DlinkedNode* node = cache[key];
node->value = value;
addToHead(node, true);
}
}
int get(int key) {
if(!cache.count(key)) return -1; // key不存在
// 如果 key 存在，先通过哈希表定位，再移到头部
DlinkedNode* node = cache[key];
addToHead(node, true);// 尾部是最久未使用
return node->value;
}
void addToHead(DlinkedNode* node, bool exit = false){
if(exit){
node->prev->next = node->next;
node->next->prev = node->prev;
}
node->prev = head;
node->next = head->next;
head->next->prev = node;
head->next = node;
}
void removeTail(){
DlinkedNode* node = tail->prev;
node->prev->next = node->next;
node->next->prev = node->prev;
// 删除哈希表中对应的项
cache.erase(node->key);
delete node;
size--;
}
};
复制带随机指针的链表
复制带随机指针的链表
class Solution {
public:
Node* copyRandomList(Node* head) {
if(head == nullptr) return nullptr;
Node* cur = head;
unordered_map<Node*, Node*> map; // <原节点，复制的新节点>
// 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射
while(cur != nullptr) {
Node* new_node = new Node(cur->val);
map[cur] = new_node; // 原节点 -> 新节点
cur = cur->next;
}
cur = head;
// 构建新链表的 next 和 random 指向
while(cur != nullptr) {
// 值为新节点，键为旧节点
// 当前旧节点对应的新节点的next 指向 当前旧节点的next指向的节点对应的新节点
map[cur]->next = map[cur->next];
// 当前旧节点对应的新节点的random 指向 当前旧节点的random指向的节点对应的新节点
map[cur]->random = map[cur->random];
cur = cur->next;
}
// 返回新链表的头节点
return map[head];
}
};