题解 | #链表中的节点每k个一组翻转#

#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;
};