哈希表问题-LeetCode 146、290、299、300（哈希表，双向链表，最小上升序列）
哈希表问题-LeetCode 146、290、299、300（哈希表，双向链表，最小上升序列）
作者：TeddyZhang，公众号：算法工程师之路
1
编程题
【LeetCode #146】LRU缓存机制
运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作：获取数据 get 和 写入数据 put 。
获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。 写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。
进阶:
你是否可以在 O(1) 时间复杂度内完成这两种操作？
示例: LRUCache cache = new LRUCache( 2 /* 缓存容量 */ ); cache.put(1, 1); cache.put(2, 2); cache.get(1); // 返回 1 cache.put(3, 3); // 该操作会使得密钥 2 作废 cache.get(2); // 返回 -1 (未找到) cache.put(4, 4); // 该操作会使得密钥 1 作废 cache.get(1); // 返回 -1 (未找到) cache.get(3); // 返回 3 cache.get(4); // 返回 4
解题思路：
LRU算法可以用于缓存机制，也同样适用于页面置换算法！其思路为每次置换最近最久不访问的内存空间到磁盘中，具体措施是维护一个链表，当访问一个页面时， 将该页面移动到链表的头部，而链表的尾部始终为最近最久未访问的空间，当内存不够时，将链表尾部的空间进行置换即可！
而在本题中，引入了缓存机制，由于缓存的数据可能重复，因此使用秘钥key加以区分，由于需要在链表的头部和尾部操作，应该使用双向链表list(STL中forward_list为单向链表)，list的成员应该为pair，不然没有秘钥无法区分！大家都清楚，链表的查询是很慢的，必须从头到尾进行遍历，因此可以使用哈希表进行保存list的迭代器！ 从而使用unordered_map<int, list::iterator>, 这样做的好处就是：假设删除秘钥为key的节点，不用遍历在链表中查询了，可以O(1)的获取将要删除的节点的迭代器！即hashmap[key].,="">,>
(STL库函数版本)
class LRUCache {
public:
LRUCache(int capacity) : capacity_(capacity) {}
int get(int key) {
if(hashmap.count(key) == )
return -1;
else{
int val = hashmap[key]->second;
lis.erase(hashmap[key]);
lis.push_front(make_pair(key, val));
hashmap[key] = lis.begin();
return val;
}
}
void put(int key, int value) {
if(hashmap.count(key) != ){
lis.erase(hashmap[key]);
}else if (lis.size() >= capacity_){
hashmap.erase(lis.back().first);
lis.pop_back(); // 删除最近最久未访问的数据
}
lis.push_front(make_pair(key, value));
hashmap[key] = lis.begin(); // 迭代器存入哈希表
}
private:
int capacity_;
list<pair<int, int>> lis;
unordered_map<int, list<pair<int, int>>::iterator> hashmap;
};
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache* obj = new LRUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/
(手撸双向链表版本)
class LRUCache {
public:
struct ListNode{
ListNode* pre;
ListNode* next;
int key;
int val;
ListNode(int key_, int val_) : key(key_), val(val_), pre(nullptr), next(nullptr) {}
};
LRUCache(int capacity) : capacity_(capacity), cnt(){
head = new ListNode(-1, -1);
tail = new ListNode(-1, -1);
head->next = tail;
tail->pre = head;
}
void update(ListNode *p){ // 更新，将p节点删除，并移至头部
if(p->pre == head) return;
// 删除p节点操作
p->pre->next = p->next;
p->next->pre = p->pre;
// 插入头部操作
p->next = head->next;
p->pre = head;
head->next->pre = p;
head->next = p;
}
int get(int key) {
unordered_map<int, ListNode*>::iterator it = hashmap.find(key);
if(it == hashmap.end()) return -1;
ListNode *p = it->second;
update(p);
return p->val;
}
void put(int key, int value) {
if(capacity_ <= ) return;
unordered_map<int, ListNode*>::iterator it = hashmap.find(key);
if(it == hashmap.end()){ // 没有找到
ListNode *p = new ListNode(key, value);
hashmap[key] = p;
p->next = head->next;
p->pre = head;
head->next->pre = p;
head->next = p;
cnt++; // 节点加一
if(cnt > capacity_){
ListNode* pDel = tail->pre; // 删除双向链表尾部节点
pDel->pre->next = tail;
tail->pre = pDel->pre;
unordered_map<int, ListNode*>::iterator itDel = hashmap.find(pDel->key);
hashmap.erase(itDel);
delete pDel;
cnt--;
}
}else{
ListNode *p = it->second;
p->val = value;
update(p);
}
}
private:
int capacity_;
int cnt; // 标记双向链表节点数
unordered_map<int, ListNode*> hashmap;
ListNode* head, *tail;
};
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache* obj = new LRUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/lru-cache
【LeetCode #290】单词规律
给定一种规律 pattern 和一个字符串 str ，判断 str 是否遵循相同的规律。 这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应规律。
示例1: 输入: pattern = "abba", str = "dog cat cat dog" 输出: true
解题思路：
使用两张哈希表，在CPP中可以使用istringstream进行字符串的分割，将分割后的字符串写入到哈希表stringmap，并不断更新其位置（i+1），而pattern中的字符也对应一个哈希表charmap，其值也为i+1。我们在遍历的同时去判断长度是否一致，以及两个哈希表所代表的的值是否相同即可！
class Solution {
public:
bool wordPattern(string pattern, string str) {
unordered_map<char, int> charmap;
unordered_map<string, int> strmap;
int i = ;
istringstream is(str);
string s = "";
while(is >> s){
if(i == pattern.size()) return false; // 长度不一样，失败
if(strmap[s] != charmap[pattern[i]]) return false;
else
strmap[s] = charmap[pattern[i]] = i+;
i++;
}
return i == pattern.size();
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/word-pattern
【LeetCode #299】猜数字游戏
你正在和你的朋友玩 猜数字（Bulls and Cows）游戏：你写下一个数字让你的朋友猜。每次他猜测后，你给他一个提示，告诉他有多少位数字和确切位置都猜对了（称为“Bulls”, 公牛），有多少位数字猜对了但是位置不对（称为“Cows”, 奶牛）。你的朋友将会根据提示继续猜，直到猜出秘密数字。 请写出一个根据秘密数字和朋友的猜测数返回提示的函数，用 A 表示公牛，用 B 表示奶牛。 请注意秘密数字和朋友的猜测数都可能含有重复数字。
示例 1: 输入: secret = "1807", guess = "7810" 输出: "1A3B" 解释: 1 公牛和 3 奶牛。公牛是 8，奶牛是 0, 1 和 7。
解题思路：
一开始题没有看懂，其实不要管什么牛，只要记住同位置同样数字个数就是A的个数，将这些数字除外以后，剩余数字中不同位置同一数字的个数为B的个数！因此，采用两次遍历的方法，先找出公牛，也就是cnt_A, 然后将其标记为不同字符（不能是数字，避免冲突），然后遍历secret数组，在guess中查找（反过来也可以），如果找到了，cnt_B就自加！
class Solution {
public:
string getHint(string secret, string guess) {
int cnt_A = , cnt_B = ;
for(int i = ; i < secret.length(); i++){
if(secret[i] == guess[i]){
cnt_A++;
secret[i] = '*';
guess[i] = '#'; // 将不同位置相同数字换成不同字符，防止下次查找出错
}
}
for(int i = ; i < secret.length(); i++){
int ss = guess.find(secret[i]);
if(ss != guess.npos){
cnt_B++;
secret[i] = '*';
guess[ss] = '#'; // 将不同位置相同数字换成不同字符，防止下次查找出错
}
}
return to_string(cnt_A)+"A"+to_string(cnt_B)+"B";
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/bulls-and-cows
【LeetCode #300】最长上升子序列
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例: 输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
解题思路：
经典动态规划问题，dp[i] = max(dp[i], dp[j]+1);
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int N = nums.size();
vector<int> dp(N, );
int res = ;
for(int i = ; i < N; i++){
for(int j = ; j < i; j++){
if(nums[j] < nums[i]){
dp[i] = max(dp[i], dp[j]+);
}
}
res = max(dp[i], res);
}
return res;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/longest-increasing-subsequence
腾讯云开发者
