This article is participating in the nuggets team number online activity, click to see the dachang spring recruiting positions

Topic describes

Using your knowledge of data structures, design and implement an LRU (least recently used) caching mechanism.

Implement the LRUCache class:

  • LRUCache(int capacity) The LRU cache is initialized using a positive integer as capacity
  • Int get(int key) Returns the value of the key if it exists in the cache, otherwise -1 is returned.
  • Void put(int key, int value) If the keyword already exists, change its data value. If the keyword does not exist, the set of keyword – values is inserted. When the cache reaches its maximum capacity, it should delete the oldest unused data values before writing new data to make room for new data values.

Advanced: Can you do both in O(1) time?

Example: Input [" LRUCache ", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2]. [4, 4], [1], [3], [4] Output [NULL, NULL, NULL, 1, NULL, -1, NULL, -1, 3, 4] LRUCache LRUCache = new LRUCache(2); lRUCache.put(1, 1); // Cache is {1=1} lRUCache. Put (2, 2); {1=1, 2=2} lRUCache. Get (1); // Return 1 lRUCache. Put (3, 3); {1=1, 3=3} lRUCache. Get (2); // return -1 (not found) lRUCache. Put (4, 4); {4=4, 3=3} lRUCache. Get (1); // return -1 (not found) lRUCache. Get (3); // return 3 lRUCache. Get (4); // 4 information is displayed: 1 <= Capacity <= 3000 0 <= key <= 3000 0 <= value <= 104 Invoke get and PUT a maximum of 3 times. Difficulty: Medium.Copy the code

Thought analysis

  • A. yes B. no C. no D. noget 和 putThe operation, and requirementsO(1)Complexity, think of hash tables
  • Structures require frequent writes and deletions, which can be achieved using linked lists
  • Combined, the whole idea of solving the problem is to use hash table + double linked list to achieve the whole structure
  • Double-linked lists are used to store caches and need to implement insert logic
  • Hash tables are mainly used to record throughkeyGenerates keys to quickly determine whether caches overlap and locate values
  • The value of the hash table corresponds to the node of the doubly linked list

AC code

#define Nothingness -1
// Create a double-linked list structure
struct node {
    int key;
    int value;
    struct node* prev;
    struct node* next;
};
// Double linked list insert node method
void InsertNode(struct node* head, struct node* cur) {
    if(cur->prev == NULL && cur->next == NULL) {
        // new node, increment
        cur->prev = head;
        cur->next = head->next;
        head->next->prev = cur;
        head->next = cur;
    }else {
        struct node* first = head->next;
        if(first ! = cur) {// Old node, modifycur->prev->next = cur->next; cur->next->prev = cur->prev; cur->prev = head; cur->next = head->next; head->next->prev = cur; head->next = cur; }}}// Create hash structure
struct hash {
    struct node* unused;
    struct hash* next;
};
// find the hash address
struct hash* HashMap(struct hash* table, int key, int capacity) {
    int addr = key % capacity;
    return &table[addr];
}
// Cache structure
typedef struct {
    int size;
    int capacity;
    struct hash* table;
    struct node* head;
    struct node* tail;
} LRUCache;
// Create a new cache structure
LRUCache* lRUCacheCreate(int capacity) {
    LRUCache* obj = (LRUCache*)malloc(sizeof(LRUCache));
    obj->table = (struct hash*)malloc(capacity * sizeof(struct hash));
    memset(obj->table, 0, capacity * sizeof(struct hash));
    obj->head = (struct node*)malloc(sizeof(struct node));
    obj->tail = (struct node*)malloc(sizeof(struct node));

    obj->head->prev = NULL;
    obj->head->next = obj->tail;
    obj->tail->prev = obj->head;
    obj->tail->next = NULL;
    obj->size = 0;
    obj->capacity = capacity;

    return obj;
}
// Get a value in the cache
int lRUCacheGet(LRUCache* obj, int key) {
    struct hash* addr = HashMap(obj->table, key, obj->capacity);
    addr = addr->next;
    if(addr == NULL) return Nothingness;
    while(addr->next ! =NULL&& addr->unused->key ! = key) { addr = addr->next; }if(addr->unused->key == key) {
        // Double linked list goes to the front, returns the value
        InsertNode(obj->head, addr->unused);
        return addr->unused->value;
    }
    return Nothingness;
}
// Store a value in the cache
void lRUCachePut(LRUCache* obj, int key, int value) {
    // Check whether it already exists, and check whether the capacity is sufficient
    // Both hash and linked lists are operated on if they do not exist, only linked lists are operated on if they exist
    struct hash* addr = HashMap(obj->table, key, obj->capacity);
    if(lRUCacheGet(obj, key) == Nothingness) {
        // Does not exist to determine whether the capacity is sufficient
        if(obj->size >= obj->capacity) {
            // Delete unnecessary nodes first
            struct node* last = obj->tail->prev;
            struct hash* remove = HashMap(obj->table, last->key, obj->capacity);
            struct hash* ptr = remove;
            remove = remove->next;
            while(remove->unused->key ! = last->key) { ptr = remove; remove = remove->next; } ptr->next = remove->next; remove->next =NULL;
            remove->unused = NULL;
            free(remove);
            // Make use of last
            last->key = key;
            last->value = value;
            InsertNode(obj->head, last);
            // Update the hash
            struct hash* new_code = (struct hash*)malloc(sizeof(struct hash));
            new_code->next = addr->next;
            addr->next = new_code;
            new_code->unused = last;
        }else {
            // Insert it directly
            struct hash* new_code = (struct hash*)malloc(sizeof(struct hash));
            new_code->unused = (struct node*)malloc(sizeof(struct node));
            new_code->next = addr->next;
            addr->next = new_code;
            new_code->unused->key = key;
            new_code->unused->value = value;
            new_code->unused->prev = NULL;
            new_code->unused->next = NULL; InsertNode(obj->head, new_code->unused); ++(obj->size); }}else {
        // The insert node is already in the front of the linked list due to getobj->head->next->value = value; }}void lRUCacheFree(LRUCache* obj) {
    free(obj->table);
    free(obj->head);
    free(obj->tail);
    free(obj);
}
Copy the code

Complexity analysis

  • Time complexity:O(1)
  • Space complexity:O(n)