数据结构设计
设计有setAll功能的哈希表
#include <vector>
#include <iostream>
#include <algorithm>
#include <unordered_map>using namespace std;// <key, <val, time>>
unordered_map<int, pair<int, int>> map;
int setAllVal;
int setAllTime = -1;
// 时间戳
int timeStamp = 0;void put(int k, int v) {if (map.find(k) == map.end()) {// 不存在就加上时间戳map.emplace(k, make_pair(v, timeStamp++));} else {// 已经存在就修改时间戳map[k].first = v;map[k].second = timeStamp++;}
}void get(int k) {// 不存在if (map.find(k) == map.end()) {cout << -1 << endl;return;}// 返回最新的值if (map[k].second > setAllTime)cout << map[k].first << endl;elsecout << setAllVal << endl;
}void setAll(int v) {setAllVal = v;setAllTime = timeStamp++;
}int main() {int n;scanf("%d", &n);for (int i = 0, opt, k, v; i < n; ++i) {cin >> opt;switch (opt) {case 1:scanf("%d%d", &k, &v);put(k, v);break;case 2:scanf("%d", &k);get(k);break;case 3:scanf("%d", &v);setAll(v);break;}}
}
146. LRU 缓存
#include <vector>
#include <iostream>
#include <algorithm>
#include <unordered_map>using namespace std;class LRUCache {
public:// 双向链表struct ListNode {int key;int value;ListNode *prev;ListNode *next;ListNode() {prev = nullptr;next = nullptr;}ListNode(int k, int v) {key = k;value = v;prev = nullptr;next = nullptr;}};// 用于定位 key 所对应的节点在链表中的位置unordered_map<int, ListNode *> map;// 虚拟头尾节点ListNode *dummyHead;ListNode *dummyTail;int capacity;int size;LRUCache(int capacity) {LRUCache::capacity = capacity;size = 0;dummyHead = new ListNode();dummyTail = new ListNode();dummyHead->next = dummyTail;dummyTail->prev = dummyHead;}// 插入到最后void addToTail(ListNode *node) {node->next = dummyTail;node->prev = dummyTail->prev;dummyTail->prev->next = node;dummyTail->prev = node;}// 将最近操作过的节点放到双向链表的表尾// 表头是最近最久未使用的节点void moveToTail(ListNode *node) {// 断开node->prev->next = node->next;node->next->prev = node->prev;addToTail(node);}// 删除首个节点void removeHead() {ListNode *node = dummyHead->next;dummyHead->next->next->prev = dummyHead;dummyHead->next = dummyHead->next->next;delete node;node = nullptr;}int get(int key) {// 不存在if (map.find(key) == map.end()) return -1;// 存在，就挪到末尾然后返回moveToTail(map[key]);return map[key]->value;}void put(int key, int value) {if (map.find(key) == map.end()) {// 超出容量就删除最近最久未使用的if (++size > capacity) {map.erase(dummyHead->next->key);removeHead();}// 不存在就新建ListNode *node = new ListNode(key, value);addToTail(node);map.emplace(key, node);} else {// 已经存在就修改map[key]->value = value;moveToTail(map[key]);}}
};
380. O(1) 时间插入、删除和获取随机元素
- 用 map 定位元素在动态数组中的位置，删除时，转化成删除末尾元素，不让动态数组中有空位
#include <vector>
#include <iostream>
#include <algorithm>
#include <unordered_map>using namespace std;class RandomizedSet {
public:vector<int> arr;// <val, index>unordered_map<int, int> map;RandomizedSet() {}bool insert(int val) {if (map.find(val) != map.end()) return false;arr.emplace_back(val);// 记录 val 在动态数组中的位置map.emplace(val, arr.size() - 1);return true;}bool remove(int val) {if (map.find(val) == map.end()) return false;// 更新原来末尾元素的新位置map[arr[arr.size() - 1]] = map[val];// 与最后一个元素互换位置，然后删掉动态数组的末尾swap(arr[arr.size() - 1], arr[map[val]]);arr.pop_back();map.erase(val);return true;}int getRandom() {return arr[rand() % arr.size()];}
};
381. O(1) 时间插入、删除和获取随机元素 - 允许重复
#include <vector>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>using namespace std;class RandomizedCollection {
public:vector<int> arr;// <val, 在动态数组中下标的集合>unordered_map<int, unordered_set<int>> map;RandomizedCollection() {}bool insert(int val) {arr.emplace_back(val);// 记录 val 在动态数组中的位置map[val].emplace(arr.size() - 1);return map[val].size() == 1;}bool remove(int val) {if (map.find(val) == map.end()) return false;if (val == arr[arr.size() - 1]) {map[val].erase(arr.size() - 1);arr.pop_back();} else {// 从所有值为 val 的元素中选一个作为被删除元素int valIndex = *map[val].begin();// 数组末尾元素，用于放到被删除的位置int lastIndex = arr.size() - 1;int last = arr[lastIndex];// 1. 交换这两个元素在 map 中的定位信息// 先更新被删除元素的位置：：val 由 valIndex 移动到 arr.size() - 1map[val].erase(valIndex);map[val].emplace(lastIndex);// 后更新 last 元素的位置：last 由 arr.size() - 1 移动到 valIndexmap[last].erase(lastIndex);map[last].emplace(valIndex);// 2. 交换在数组中的位置，然后删掉末尾swap(arr[valIndex], arr[lastIndex]);map[val].erase(lastIndex);arr.pop_back();}// 移除空的集合if (map[val].size() == 0) map.erase(val);return true;}int getRandom() {return arr[rand() % arr.size()];}
};
295. 数据流的中位数
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>using namespace std;class MedianFinder {
public:// 左侧的大根堆，如果总个数为奇数个，就把中位数放到大根堆里priority_queue<int, vector<int>, less<int>> maxHeap;// 右侧的小根堆priority_queue<int, vector<int>, greater<int>> minHeap;MedianFinder() {}void addNum(int num) {if (maxHeap.size() == 0) {maxHeap.emplace(num);return;}if ((maxHeap.size() + minHeap.size()) & 1) {// 总个数为奇数个if (num <= maxHeap.top()) {// 放入左侧的大根堆maxHeap.emplace(num);// 把大根堆堆顶移到小根堆里，使两个堆的元素一样多minHeap.emplace(maxHeap.top());maxHeap.pop();} else {// 直接放入小根堆minHeap.emplace(num);}} else {// 总个数为偶数个if (num <= maxHeap.top()) {// 直接放入左侧的大根堆maxHeap.emplace(num);} else {// 放入小根堆minHeap.emplace(num);// 把小根堆堆顶移到大根堆里，使两个堆的元素一样多maxHeap.emplace(minHeap.top());minHeap.pop();}}}double findMedian() {if ((maxHeap.size() + minHeap.size()) & 1) {// 总个数为奇数个return maxHeap.top();} else {// 总个数为偶数个return (maxHeap.top() + minHeap.top()) / 2.0;}}
};
895. 最大频率栈
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <unordered_map>using namespace std;class FreqStack {
public:// <i, i 出现的次数>unordered_map<int, int> freq;// <出现的次数，包含出现这种次数的所有数的列表>unordered_map<int, vector<int>> countValues;// 最大次数int _max;FreqStack() {}void push(int val) {freq[val]++;// 如果没有对应次数的列表，就新建if (countValues.find(freq[val]) == countValues.end())countValues.emplace(freq[val], vector<int>());// 往这种次数对应的列表末尾加入当前数countValues[freq[val]].emplace_back(val);// 更新最大出现次数_max = max(_max, freq[val]);}int pop() {// 获取出现次数最大的列表的最后一个数，也就是最靠近栈顶的int res = countValues[_max].back();countValues[_max].pop_back();// 如果这个列表空了，就移除，并且出现的最大次数减一if (countValues[_max].empty())countValues.erase(_max--);// 出栈，并减少这个数字出现的次数if (freq[res] == 1)freq.erase(res);elsefreq[res]--;return res;}
};
432. 全 O(1) 的数据结构
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>using namespace std;class AllOne {
public:// 双向链表struct ListNode {int times;unordered_set<string> bucket;ListNode *prev;ListNode *next;ListNode() {prev = nullptr;next = nullptr;}ListNode(int times, string key) : ListNode() {this->times = times;bucket.emplace(key);}};// <val, address> 记录值 val 所在链表节点的地址unordered_map<string, ListNode *> map;ListNode *dummyHead;ListNode *dummyTail;// 在 cur 后面插入void insertNode(ListNode *pos, ListNode *node) {node->prev = pos;node->next = pos->next;pos->next->prev = node;pos->next = node;}void removeNode(ListNode *node) {node->next->prev = node->prev;node->prev->next = node->next;delete node;node = nullptr;}AllOne() {dummyHead = new ListNode();dummyTail = new ListNode();dummyHead->next = dummyTail;dummyTail->prev = dummyHead;dummyHead->times = 0;dummyTail->times = INT_MAX;}void inc(string key) {if (map.find(key) == map.end()) {// key 首次加入if (dummyHead->next->times == 1) {// 如果有记录词频为 1 的桶，就放入dummyHead->next->bucket.emplace(key);map[key] = dummyHead->next;} else {// 否则就新建桶并放入ListNode *node = new ListNode(1, key);map[key] = node;insertNode(dummyHead, node);}} else {// 不是首次加入，就移动到下个词频（当前词频加一）的桶中ListNode *cur = map[key];if (cur->next->times == cur->times + 1) {// 如果存在下个一个词频的桶，就移进去cur->next->bucket.emplace(key);map[key] = cur->next;} else {// 否则就新建桶并放入ListNode *node = new ListNode(cur->times + 1, key);map[key] = node;insertNode(cur, node);}// 从原来的桶里移除cur->bucket.erase(key);if (cur->bucket.empty()) removeNode(cur);}}void dec(string key) {ListNode *cur = map[key];if (cur->times == 1) {map.erase(key);} else {if (cur->prev->times == cur->times - 1) {// 移动到上个词频（当前词频减一）的桶中cur->prev->bucket.emplace(key);map[key] = cur->prev;} else {// 否则就新建桶并放入ListNode *node = new ListNode(cur->times - 1, key);map[key] = node;insertNode(cur->prev, node);}}// 从桶里移除cur->bucket.erase(key);if (cur->bucket.empty()) removeNode(cur);}string getMaxKey() {if (dummyTail->prev == dummyHead) return "";return *(dummyTail->prev->bucket.begin());}string getMinKey() {if (dummyHead->next == dummyTail) return "";return *(dummyHead->next->bucket.begin());}
};
