35 数据结构设计高频题setAll功能的哈希表测试链接 : https://www.nowcoder.com/practice/7c4559f138e74ceb9ba57d76fd169967思路设计一个时间戳若一个时间点在setAll时间时间之前就是all的值在之后就是自己本身的值伪代码定义全局变量setAllValue setAllTime cnt使用pair数组put方法传入keyval设置这两个的值。setAll方法设置setAllValue setAllTimeget方法找不到返回-1。找到定义value取出key对应的pair。比较时间戳。主函数每次处理新的测试用例前清空状态。代码实现#includebits/stdc.h using namespace std; unordered_mapint, pairint, int umap; int setAllValue 0; int setAllTime -1; int cnt 0; void put(int k, int v) { umap[k].first v; umap[k].second cnt; } void setAll(int v) { setAllValue v; setAllTime cnt; } int get(int k) { if (umap.find(k) umap.end()) { return -1; } pairint, int val umap[k]; if (val.second setAllTime) { return val.first; } else { return setAllValue; } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, op, a, b; cin n; for (int i 0; i n; i) { cin op; if (op 1) { cin a b; put(a, b); } else if (op 2) { cin a; cout get(a) \n; } else if (op 3) { cin a; setAll(a); } } return 0; }LRU缓存测试链接https://leetcode.cn/problems/lru-cache/思路使用双向链表和哈希表用双向链表控制新旧顺序用哈希表控制存取。伪代码定义双向链表结点结构定义双向链表结构头指针和尾指针添加节点到链表尾部addNode将指定结点移动到链表尾部moveNodeToTail,移除并且返回链表的头部结点removeHead。get获取指定key的值不存在就返回-1。put插入或者更新键值对如果键已经存在更新并且移动到尾部。如果键不存在检查容量,容量已满移除链表的头节点和哈希表中的结点添加新结点。移除链表头部结点并且删除哈希表的结点。创建新结点并且添加。代码实现class LRUCache { private: // 双向链表节点结构 struct DoubleNode{ int key; int val; DoubleNode *last; DoubleNode *next; DoubleNode(int k, int v) : key(k), val(v), last(nullptr), next(nullptr) {}; }; // 双向链表结构 class DoubleList { private: DoubleNode* head; DoubleNode* tail; public: DoubleList() : head(nullptr), tail(nullptr) {} // 添加节点到链表尾部 void addNode(DoubleNode *newNode){ if(newNodenullptr){ return ; } if(headnullptr){ headnewNode; tailnewNode; }else{ tail-nextnewNode; newNode-lasttail; tailnewNode;}} // 将指定节点移动到链表尾部 void moveNodeToTail(DoubleNode *newNode){ if(newNodetail){ return; } if(newNodehead){ headhead-next; head-lastnullptr; }else { newNode-last-nextnewNode-next; newNode-next-lastnewNode-last; } newNode-nextnullptr; newNode-lasttail; tail-nextnewNode; tailnewNode; } // 移除并返回链表头部节点 DoubleNode* removeHead(){ if(headnullptr){ return nullptr; } DoubleNode* anshead; if(headtail){ headnullptr; tailnullptr; }else{ headhead-next; head-lastnullptr; ans-nextnullptr; } return ans; } }; unordered_mapint, DoubleNode* keyNodeMap; // 键值到节点的映射 DoubleList nodeList; // 双向链表维护访问顺序 const int capacity; // 缓存容量 public: // 构造函数初始化缓存容量 LRUCache(int cap) : capacity(cap) {} // 析构函数释放所有节点内存避免内存泄漏 //用pair保存哈希表的数据 ~LRUCache(){ for(auto pair:keyNodeMap){ delete pair.second; } keyNodeMap.clear(); } // 获取指定key的值不存在则返回-1 int get(int key){ if(keyNodeMap.find(key)!keyNodeMap.end()){ DoubleNode* anskeyNodeMap[key]; nodeList.moveNodeToTail(ans); return ans-val; } return -1; } // 插入或更新键值对 void put (int k,int v){ if(keyNodeMap.find(k)!keyNodeMap.end()){ // 键已存在更新值并移动到尾部 //哈希表存的就是这个结点的地址在修改这个的值时链表中对应的值也被修改了 DoubleNode* node keyNodeMap[k]; node-val v; nodeList.moveNodeToTail(node); }else{ if(keyNodeMap.size()capacity){ DoubleNode* nodenodeList.removeHead(); keyNodeMap.erase(node-key); delete node; } //创建新结点 DoubleNode *newNodenew DoubleNode(k,v); keyNodeMap[k]newNode; nodeList.addNode(newNode); } } };插入删除和获取随机元素O1时间的结构测试链接 : https://leetcode.cn/problems/insert-delete-getrandom-o1/思路哈希表和数组用数组最后的元素覆盖要删除的元素保证数组的连续性在随机数的时候可以变得更高效。伪代码插入元素如果元素已经存在返回false;不存在将元素添加到数组和哈希表中。删除元素如果元素不存在返回false存在获取要删除元素的索引和最后一个元素的值。将最后一个元素移动到要删除的元素的位置更新最后一个元素的索引。删除哈希表的值和数组中最后一个元素。代码实现class RandomizedSet { private: unordered_mapint,int valToIndex; vectorint arr; public: RandomizedSet() { srand(time(nullptr)); } bool insert(int val) { if(valToIndex.find(val)!valToIndex.end()){//表示元素存在 return false; } valToIndex[val]arr.size(); arr.push_back(val); return true; } bool remove(int val) { if(valToIndex.find(val)valToIndex.end()){//表示元素不存在 return false;} int valIndexvalToIndex[val]; int lastvalarr.back(); arr[valIndex]lastval; valToIndex[lastval]valIndex; valToIndex.erase(val); arr.pop_back(); return true; } int getRandom() { if (arr.empty()) { return -1; } int randomIndex rand() % arr.size(); return arr[randomIndex]; } };插入删除和获取随机元素O1时间且允许有重复数字的结构测试链接 https://leetcode.cn/problems/insert-delete-getrandom-o1-duplicates-allowed/思路用集合来存储一个值对应的一些索引伪代码插入元素将元素插入数组获取该元素对应的索引集合将该元素的索引加入集合。如果是第一次返回true;删除元素元素不存在返回false获取该元素的索引集合取出集合中的一个索引获取数组中最后一个元素的值。如果待删除元素就是数组中最后一个元素的索引直接从索引集合中移除这个索引不是最后一个元素获取最后一份元素的索引集合将最后一个元素的索引集合添加要新的位置去掉老的位置删去当前元素集合中对应的索引数组用最后一个元素覆盖当前元素。删除数组最后一个元素。如果当前元素的索引集为空删去该键。代码实现class RandomizedCollection { private: unordered_mapint,unordered_setint valueToIndexes; vectorint elements; public: RandomizedCollection() { srand(time(nullptr)); } //插入元素 bool insert(int val) { elements.push_back(val); unordered_setint indexesvalueToIndexes[val]; indexes.insert(elements.size()-1); return indexes.size()1; } //移除元素 bool remove(int val) { //未找到该元素 if(valueToIndexes.find(val)valueToIndexes.end()){ return false; } unordered_setint indexesvalueToIndexes[val]; int dex*indexes.begin(); int lastValueelements.back(); //如果是最后一个就直接去除最后一个元素对应的索引 if(lastValueval){ indexes.erase(elements.size()-1); }else{ //先覆盖再映射 unordered_setint lastIndexesvalueToIndexes[lastValue]; elements[dex]lastValue; lastIndexes.insert(dex); lastIndexes.erase(elements.size()-1); indexes.erase(dex); } //删除最后一个元素 elements.pop_back(); //如果索引集为空删除键 if(indexes.empty()){ valueToIndexes.erase(val); } return true; } int getRandom() { if (elements.empty()) { return -1; } // 生成0到elements.size()-1之间的随机索引 int randomIndex rand() % elements.size(); return elements[randomIndex]; } };快速获得数据流的中位数的结构测试链接 : https://leetcode.cn/problems/find-median-from-data-stream/思路较小的一半用大根堆组织较大的一般用小根堆组织伪代码平衡两个堆的大小差值如果两个堆的差值为二哪个堆的元素多就移动到另一个堆如果大根堆为空或者大根堆的堆顶大于等于当前数字存入大根堆否则存入小根堆。找到当前中位数两个堆相等返回两个堆的顶部。不相等返回元素更多的堆的堆顶。代码实现class MedianFinder { private: priority_queueint maxHeap; priority_queueint,vectorint,greaterint minHeap; void balance(){ int gapabs(static_castint(maxHeap.size()) - static_castint(minHeap.size())); if(gap2){ if(maxHeap.size()minHeap.size()){ minHeap.push(maxHeap.top()); maxHeap.pop(); } else{ maxHeap.push(minHeap.top()); minHeap.pop(); } } } public: MedianFinder() { } void addNum(int num) { if(maxHeap.empty()||maxHeap.top()num){ maxHeap.push(num); } else{ minHeap.push(num); } balance(); } double findMedian() { if(maxHeap.size()minHeap.size()){ return (static_castdouble(maxHeap.top()) minHeap.top()) / 2.0; } else{ return maxHeap.size()minHeap.size()?maxHeap.top():minHeap.top(); } } };最大频率栈测试链接 : https://leetcode.cn/problems/maximum-frequency-stack/思路两个哈希表一个哈希表记录出现次数和该次数对应的元素一个哈希表记录元素和元素出现的次数。定义一个最大出现次数。伪代码压入更新该元素的出现次数记录当前的次数。如果当前次数的列表不存在创建空列表。将元素添加到对应次数的表尾更新最大出现次数弹出取出最大次数对应的元素列表取出表的最后一个元素。如果该列表为空删除该键并且减小最大次数。更新该元素的出现的次数代码实现public: FreqStack():topTime(0) { } void push(int val) { valueTimes[val]valueTimes.count(val)?valueTimes[val]1:1; int curTopTimesvalueTimes[val]; if(!cntValue.count(curTopTimes)){ cntValue[curTopTimes]vectorint(0); } cntValue[curTopTimes].push_back(val); topTimemax(curTopTimes,topTime); } int pop() { vectorint topTimeValuescntValue[topTime]; int anstopTimeValues.back(); topTimeValues.pop_back(); if(topTimeValues.empty()){ cntValue.erase(topTime); topTime--; } int curvalueTimes[ans]; if(cur1){ valueTimes.erase(ans); }else{ valueTimes[ans]-1; } return ans; } };全是O(1)的数据结构测试链接https://leetcode.cn/problems/all-oone-data-structure/思路用双向链表和桶伪代码定义桶结点包含词频字符集前后指针插入桶结点移除桶结点断连后释放内存。定义桶的头结点尾结点哈希表。初始化双向链表删除双向链表。插入键不存在加入计数为1的桶在哈希表中记录桶不存在创建新的桶插入链表哈希表记录。键存在取出对应的桶如果计数加1的桶存在存入桶哈希表记录存入桶。不存在创建新桶插入记录。从原桶移除key,如果桶为空去除桶删除键不存在返回。取出字符集如果计数为1删除该键。如果计数减1的桶存在存入桶哈希表记录存入桶。不存在创建新桶插入记录。从原桶移除key,如果桶为空去除桶。代码实现class AllOne { private: struct Bucket{ int cnt; unordered_setstring set; Bucket *last; Bucket *next; Bucket(const string s,int c):cnt(c),last(nullptr),next(nullptr){ set.insert(s); }}; //插入结点 void insert(Bucket*cur,Bucket*pos){ cur-next-lastpos; pos-nextcur-next; cur-nextpos; pos-lastcur; } void remove(Bucket* cur){ cur-last-nextcur-next; cur-next-lastcur-last; delete cur; } Bucket* head; Bucket* tail; unordered_mapstring,Bucket* map; public: AllOne() { head new Bucket(, 0); tail new Bucket(, INT_MAX); head-nexttail; tail-lasthead; } ~AllOne() { Bucket* current head; while (current ! nullptr) { Bucket* next current-next; delete current; current next; } } void inc(string key) { if(map.find(key)map.end()){ if(head-next-cnt1){ map[key]head-next; head-next-set.insert(key); }else{ Bucket* newBucketnew Bucket(key,1); map[key]newBucket; insert(head,newBucket); } } else{ Bucket *bucketmap[key]; if(bucket-next-cntbucket-cnt1){ bucket-next-set.insert(key); map[key]bucket-next; } else{ Bucket *newbucketnew Bucket(key,bucket-cnt1); map[key]newbucket; insert(bucket,newbucket); } bucket-set.erase(key); if(bucket-set.empty()){ remove(bucket); } } } void dec(string key) { if (map.find(key) map.end()) { return; } Bucket* bucket map[key]; if (bucket-cnt 1) { map.erase(key); } else { // 计数1计数-1 if (bucket-last-cnt bucket-cnt - 1) { map[key] bucket-last; bucket-last-set.insert(key); } else { Bucket* newBucket new Bucket(key, bucket-cnt - 1); map[key] newBucket; insert(bucket-last, newBucket); } } // 从原桶中移除key bucket-set.erase(key); if (bucket-set.empty()) { remove(bucket); } } string getMaxKey() { if (tail-last head) { return ; // 空结构返回空字符串 } return *tail-last-set.begin(); } string getMinKey() { if (head-next tail) { return ; // 空结构返回空字符串 } return *head-next-set.begin(); } };