题解 | #链表中的节点每k个一组翻转#
LFU缓存结构设计
http://www.nowcoder.com/practice/93aacb4a887b46d897b00823f30bfea1
#include <unordered_map> #include <vector> using namespace std; // 这题本质上就是链表的插入和删除问题,只不过增加了很多限制,因此我们要分模块编写 // 由于还要考虑访问时间,所以每当我们set或get时,巧妙的利用 ">=" 的频率比较方式实现链表元素的重排,就能模拟达到时间上的访问先后逻辑。 // 同时本题也考虑了heap空间资源的释放,这是C++程序有责任要加入的相关代码!!! class ListNode_ { public: ListNode_(int key, int val): key(key), value(val), freq(1), next(nullptr), prev(nullptr){} void updateState(){ this->freq++; } int key; int value; //size_t serial; size_t freq; ListNode_* next; ListNode_* prev; static size_t curSerial; }; size_t ListNode_::curSerial = 0; class Solution { public: /** * lfu design * @param operators int整型vector<vector<>> ops * @param k int整型 the k * @return int整型vector */ vector<int> LFU(vector<vector<int>> &operators, int k) { // write code here ListNode_::curSerial = 0; this->residualCap = k; map.clear(); head = new ListNode_(0, 0); end = new ListNode_(0, 0); head->next = end; end->prev = head; vector<int> result; for(auto& vec : operators){ if(vec[0] == 1){ set(vec[1], vec[2]); } else if(vec[0] == 2){ result.push_back(get(vec[1])); } } freeResource(head); return result; } private: void freeResource(ListNode_* head){ ListNode_* nextNode = nullptr; while(head != nullptr){ nextNode = head->next; delete head; head = nextNode; } } void set(int key, int val){ if(map.find(key) != map.end()){ ListNode_* node = map[key]; node->value = val; node->updateState(); // 加下来开始调用这一方法 if(isCurNodeNeedMoveForward(node)){ ListNode_* destPos = findNodeToInsert(node->prev, node); eraseNode(node); insertNode(destPos, node); } } else{ ListNode_* node = new ListNode_(key, val); map[key] = node; if(residualCap == 0){ ListNode_* lastNode = end->prev; map.erase(lastNode->key); eraseNode(lastNode); delete lastNode; residualCap++; } ListNode_* destNode = findNodeToInsert(end->prev, node); insertNode(destNode, node); residualCap--; } } int get(int key){ if(map.find(key) == map.end()){ return -1; } ListNode_* node = map[key]; set(key, node->value); return node->value; } ListNode_* findNodeToInsert(ListNode_* curPos, ListNode_* nodeSelf){ while(curPos != head){ if(nodeSelf->freq >= curPos->freq){ // 等于号表示先后状态 curPos = curPos->prev; } else{ break; } } return curPos; } bool isCurNodeNeedMoveForward(ListNode_* node){ if(head->next == node){ return false; } return node->freq >= node->prev->freq ? true : false; } void eraseNode(ListNode_* node){ ListNode_* prevNode = node->prev; prevNode->next = node->next; node->next->prev = prevNode; } void insertNode(ListNode_* destPos, ListNode_* nodeSelf){ nodeSelf->next = destPos->next; nodeSelf->prev = destPos; destPos->next->prev = nodeSelf; destPos->next = nodeSelf; } ListNode_* head; ListNode_* end; size_t residualCap; unordered_map<int, ListNode_*> map; };