题解 | #设计LRU缓存结构#

这个题目其实没啥好说的。
题目O(1)应该是指最优情况下
unordered_map 可以实现最优情况下O(1)查找。
双向链表可以实现O(1)删除。
就是利用hashmap找到节点删除然后再添加到双向链表的尾部，这里手撸了一下双向链表，😂

class Solution {
public:
    /**
     * lru design
     * @param operators int整型vector<vector<>> the ops
     * @param k int整型 the k
     * @return int整型vector
     */
    struct NodeList
    {
        int key;
        int value;
        NodeList* tail;
        NodeList* next;
    };

    NodeList* head = new NodeList();
    NodeList* hend = head;
    unordered_map<int, NodeList*> KV;
    void insertp (NodeList*& hend, NodeList*& p) {
        hend->next = p;
        p->tail = hend;
        hend = p;
        hend->next = NULL;
    }
    void deletep(NodeList*& p) {
        if (p != hend) {
            p->tail->next = p->next;
            p->next->tail = p->tail;
        }
        else
        {
            hend = p->tail;
            hend->next = p->next;
        } 
    }
    int get(int key) {
        if (KV.count(key)==1) {
            auto p = KV.find(key)->second;
            deletep(p);
            insertp(hend, p);
            return p->value;
        }
        else {
            return -1;
        }
    }
    void set(int key, int value, int& k) {
        int oldValue = get(key);
        if (oldValue == -1) {
            if (!k) {
                NodeList* q = head->next;
                KV.erase(q ->key);
                deletep(q);
                free(q);
                k++;
            }
            NodeList* p = new NodeList();
            p->key = key;
            p->value=value;
            insertp(hend, p);
            KV[key] = p;
            k--;
        }
       else{
           auto p=KV[key];
           p->value=value;
           KV[key]=p;
        }
    }
    vector<int> LRU(vector<vector<int> >& operators, int k) {
        vector<int> res;
        for (auto x : operators) {
            if (x[0] == 1) {
                set(x[1], x[2], k);
            }
            else
            {
                res.push_back(get(x[1]));
            }
        }
        return res;
    }
};
static const auto io_sync_off=[]()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    return nullptr;
}();

ps:牛客的时间确实不太准一会65ms，一会95ms