力扣每日一题刷题总结：哈希表篇

剑指 Offer II 033.变位词组 Medium 哈希表 变位词 2023/3/3

给定一个字符串数组 strs ，将 变位词 组合在一起。 可以按任意顺序返回结果列表。
注意：若两个字符串中每个字符出现的次数都相同，则称它们互为变位词。
示例：
示例 1:
输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]

看到 变位词，可以使用int c[26]记录每个字符出现的次数，并归类比较，但算法时间复杂度较高。
利用变位词排序后相同的性质，使用sort方法+哈希表可以快速确定相同排序的字符。

哈希表记录排序好的字符串和当前应该插入的vector的index，非常简洁巧妙。

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {unordered_map<string, int> mp;vector<vector<string>> ans;for (int i = 0; i < strs.size(); i++) {string tmp = strs[i];sort(tmp.begin(), tmp.end());// 找到该排序if (mp.find(tmp) != mp.end()) {ans[mp[tmp]].push_back(strs[i]);}// 没找到else {mp[tmp] = ans.size();ans.push_back({strs[i]});}}return ans;}
};

---

剑指 Offer II 031.最近最少使用缓存 Medium 哈希表 变位词 2023/3/3

运用所掌握的数据结构，设计和实现一个 LRU (Least Recently Used，最近最少使用) 缓存机制 。
实现 LRUCache 类：
LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
示例：
输入
[“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]
解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4

本题需要实现两个方法：在 $O(1)$ 时间复杂度实现查找键值并更新其访问顺序、在 $O(1)$ 时间复杂度实现存键并更新其访问顺序，如使用map + deque，队列每次插入时时放进队尾，但查找键值更新访问顺序时，需要有 $O(n)$ 的时间复杂度找到当前key并pop掉。

如何在 $O(1)$ 时间复杂度实现更新访问顺序呢？使用map + 双向链表。

class LRUCache {int cache_capacity;list<pair<int,int>> mylist; // 双向链表存放键值对unordered_map<int,list<pair<int,int>>::iterator> key2addr; // map存放键和双向链表的迭代器
public:LRUCache(int capacity) {cache_capacity = capacity;}int get(int key) {if (key2addr.count(key) == 0) return -1; // 没有该键list<pair<int,int>>::iterator it = key2addr[key]; // 找到对应链表的迭代器int value = it->second;mylist.erase(it); // 链表删除该元素key2addr[key] = mylist.insert(mylist.begin(),{key,value}); // 链表头插该元素，并将迭代器放进mapreturn value;}void put(int key, int value) {// 存在该键，先删了再说if (key2addr.count(key))mylist.erase(key2addr[key]);// 不存在该键，看其是否超出容量else if (key2addr.size() >= cache_capacity) {key2addr.erase(mylist.back().first); // map删除链表最后一个元素的键mylist.pop_back(); // 链表尾删}key2addr[key] = mylist.insert(mylist.begin(),{key,value}); // 链表头插该元素，并将迭代器放进map}
};

---