LeetCode - 146 LRU缓存（Java & JS & Py & C & C ）

题目来源

146. LRU 缓存 - 力扣（LeetCode）

题目描述

请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类：

• LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
• int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
• void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

​

示例

输入

["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]

输出

[null, null, null, 1, null, -1, null, -1, 3, 4]

说明

LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

提示

• 1 <= capacity <= 3000
• 0 <= key <= 10000
• 0 <= value <= 105
• 最多调用 2 * 10^5 次 get 和 put

题目解析

LRU缓存表需要实现如下两个操作：

• get(key)：

1. 如果对应key存在，则返回key对应的val，并更新对应key为最近访问。
2. 如果对应key不存在，则返回-1。

• put(key, val)：

1. 如果对应key存在，则更新key的val，并更新对应key为最近访问。
2. 如果对应key不存在，则需要先检查缓存表是否满了：如果满了，则需要删除最久未使用的key，否则不做删除动作。
3. 之后新增key-val，并更新key为最近访问。

LRU和LFU的区别：

当空间不足时，LRU算法优先删除最久未使用的key。而LFU算法是优先删除最少使用的key，如果有多个最少使用的key，则找出其中最久未使用的key删除。

LRU的实现原理：

LRU缓存结构可以基于哈希表map和双向链表link来实现。

• 哈希表map的键即为本题的key，值则是Node(key, val)，即包装了本题key,val的节点对象。
• 双向链表link的节点元素即为Node。

这里哈希表map的值列 和 双向链表的节点 是共享Node的。如下图所示：

初始时，LRU缓存结构如下

lru.put(1,1)

通过哈希表map的键列，我们可以快速判断key是否已存在于LRU缓存中。

由于map不存在key=1，因此当前put是新增操作，且由于map中记录键数量<capacity，即容量足够，因此无需执行逐出操作。

下面我需要创建节点 Node(key=1, val=1)，并构建如下关系：

• map的键列插入key=1，并key=1的值列和 Node(key=1, val=1) 关联
• 将 Node(key=1, val=1) 头插入到双向链表Link 中（离链表头head越近，即为最近使用，离链表尾tail越近，即为最久未使用）

lru.put(2,2)

由于map不存在key=2的键，因此是put是新增操作，检查容量足够。

因此创建 Node(key=2, val=2) 后，构建如下关系。

lru.get(1)

由于map存在key=1的键，因此可以根据map[key=1]找到对应的节点Node(key=1, val=1)，并获取Node.val返回。

另外，get操作会更新key=1为最近使用，因此我们需要将Node(key=1, val=1)暂时从Link中移除，然后头插到Link。

lru.put(3,3)

由于map不存在key=3的键，因此是put是新增操作，但是此时我们发现map中记录了两个键，分别为key=1,key=2，已经装满了capacity=2的LRU缓存表，因此put新增操作前需要先逐出最久未使用的key。

前面我们说明过，离Link链表头越近的节点，则为最近使用，离Link链表尾越近的节点，则为最久未使用。

因此 Link.tail.prev 节点即为最久未使用的节点，此时我们需要删除它：

• Link中删除该节点
• 根据节点的Node.key，找到map[Node.key]的键，并删除该键

删除最久未使用后，容量足够放下新节点Node(key=3, val=3)

以上即为LRU缓存的实现原理的图示。大家可以对照下面代码实现，继续想想后面的图示。

Java算法源码

import java.util.HashMap;

class LRUCache {
    static class Node {
        int key;
        int val;
        Node prev;
        Node next;

        public Node() {};
        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    static class Link {
        Node head;
        Node tail;

        public Link() {
            this.head = new Node();
            this.tail = new Node();
            this.head.next = this.tail;
            this.tail.prev = this.head;
        }

        public void removeNode(Node node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
            node.prev = null;
            node.next = null;
        }

        public void addFirst(Node node) {
            node.next = this.head.next;
            this.head.next.prev = node;
            this.head.next = node;
            node.prev = this.head;
        }
    }

    int capacity;
    Link link;
    HashMap<Integer, Node> map;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.link = new Link();
        this.map = new HashMap<>();
    }

    public int get(int key) {
        if (this.map.containsKey(key)) {
            Node node = this.map.get(key);

            this.link.removeNode(node);
            this.link.addFirst(node);

            return node.val;
        } else {
            return -1;
        }
    }

    public void put(int key, int value) {
        if (this.map.containsKey(key)) {
            Node node = this.map.get(key);
            this.link.removeNode(node);
            this.link.addFirst(node);
            node.val = value;
        } else {
            if (this.map.size() == this.capacity) {
                Node removed = this.link.tail.prev;
                this.link.removeNode(removed);
                this.map.remove(removed.key);
            }

            Node newNode = new Node(key, value);
            this.link.addFirst(newNode);
            this.map.put(key, newNode);
        }
    }
}

//public class Main {
//    public static void main(String[] args) {
//        LRUCache lRUCache = new LRUCache(2);
//        lRUCache.put(1, 1); // 缓存是 {1=1}
//        lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
//        System.out.println(lRUCache.get(1));    // 返回 1
//        lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
//        System.out.println(lRUCache.get(2));    // 返回 -1 (未找到)
//        lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
//        System.out.println(lRUCache.get(1));    // 返回 -1 (未找到)
//        System.out.println(lRUCache.get(3));    // 返回 3
//        System.out.println(lRUCache.get(4));    // 返回 4
//    }
//}

JS算法源码

class Node {
  constructor(key, val) {
    this.key = key;
    this.val = val;
    this.next = null;
    this.prev = null;
  }
}

class Link {
  constructor() {
    this.head = new Node();
    this.tail = new Node();
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  removeNode(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
    node.prev = null;
    node.next = null;
  }

  addFirst(node) {
    node.next = this.head.next;
    this.head.next.prev = node;
    this.head.next = node;
    node.prev = this.head;
  }
}

/**
 * @param {number} capacity
 */
var LRUCache = function (capacity) {
  this.capacity = capacity;
  this.map = new Map();
  this.link = new Link();
};

/**
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function (key) {
  if (this.map.has(key)) {
    const node = this.map.get(key);
    this.link.removeNode(node);
    this.link.addFirst(node);
    return node.val;
  } else {
    return -1;
  }
};

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function (key, value) {
  if (this.map.has(key)) {
    const node = this.map.get(key);
    this.link.removeNode(node);
    this.link.addFirst(node);
    node.val = value;
  } else {
    if (this.map.size == this.capacity) {
      const removed = this.link.tail.prev;
      this.link.removeNode(removed);
      this.map.delete(removed.key);
    }

    const newNode = new Node(key, value);
    this.link.addFirst(newNode);
    this.map.set(key, newNode);
  }
};

// const lRUCache = new LRUCache(2);
// lRUCache.put(1, 1); // 缓存是 {1=1}
// lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
// console.log(lRUCache.get(1)); // 返回 1
// lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
// console.log(lRUCache.get(2)); // 返回 -1 (未找到)
// lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
// console.log(lRUCache.get(1)); // 返回 -1 (未找到)
// console.log(lRUCache.get(3)); // 返回 3
// console.log(lRUCache.get(4)); // 返回 4

Py算法源码

class Node:
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None


class Link:
    def __init__(self):
        self.head = Node(-1, -1)
        self.tail = Node(-1, -1)
        self.head.next = self.tail
        self.tail.prev = self.head

    def removeNode(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
        node.prev = None
        node.next = None

    def addFirst(self, node):
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node
        node.prev = self.head


class LRUCache(object):

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.capacity = capacity
        self.map = {}
        self.link = Link()

    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        if key in self.map:
            node = self.map[key]
            self.link.removeNode(node)
            self.link.addFirst(node)
            return node.val
        else:
            return -1

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: None
        """
        if key in self.map:
            node = self.map[key]
            self.link.removeNode(node)
            self.link.addFirst(node)
            node.val = value
        else:
            if len(self.map) == self.capacity:
                node = self.link.tail.prev
                self.link.removeNode(node)
                self.map.pop(node.key)

            node = Node(key, value)
            self.link.addFirst(node)
            self.map[key] = node


# if __name__ == '__main__':
#     lRUCache = LRUCache(2)
#     lRUCache.put(1, 1)  # 缓存是 {1=1}
#     lRUCache.put(2, 2)  # 缓存是 {1=1, 2=2}
#     print(lRUCache.get(1))  # 返回1
#     lRUCache.put(3, 3)  # 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
#     print(lRUCache.get(2))  # 返回-1
#     lRUCache.put(4, 4)  # 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
#     print(lRUCache.get(1))  # 返回-1
#     print(lRUCache.get(3))  # 返回3
#     print(lRUCache.get(4))  # 返回4

C算法源码

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 10000

typedef struct NODE {
    int key;
    int val;
    struct NODE *prev;
    struct NODE *next;
} Node;

Node *new_Node(int key, int val) {
    Node *node = (Node *) malloc(sizeof(Node));
    node->key = key;
    node->val = val;
    node->prev = NULL;
    node->next = NULL;
    return node;
}

typedef struct LINK {
    Node *head;
    Node *tail;
} Link;

Link *new_Link() {
    Link *link = (Link *) malloc(sizeof(Link));
    link->head = new_Node(-1, -1);
    link->tail = new_Node(-1, -1);
    link->head->next = link->tail;
    link->tail->prev = link->head;
    return link;
}

void removeNode(Node *node) {
    node->prev->next = node->next;
    node->next->prev = node->prev;
    node->prev = NULL;
    node->next = NULL;
}

void addFirst(Link *link, Node *node) {
    node->next = link->head->next;
    link->head->next->prev = node;
    link->head->next = node;
    node->prev = link->head;
}


typedef struct {
    int capacity;
    Node *map[MAX_SIZE];
    int map_size;
    Link *link;
} LRUCache;


LRUCache *lRUCacheCreate(int capacity) {
    LRUCache *lru = (LRUCache *) malloc(sizeof(LRUCache));
    lru->capacity = capacity;
    lru->link = new_Link();

    lru->map_size = 0;
    for (int i = 0; i < MAX_SIZE; i++) {
        lru->map[i] = NULL;
    }

    return lru;
}

int lRUCacheGet(LRUCache *lru, int key) {
    if (lru->map[key] != NULL) {
        Node *node = lru->map[key];
        removeNode(node);
        addFirst(lru->link, node);
        return node->val;
    } else {
        return -1;
    }
}

void lRUCachePut(LRUCache *lru, int key, int value) {
    if (lru->map[key] != NULL) {
        Node *node = lru->map[key];
        removeNode(node);
        addFirst(lru->link, node);
        node->val = value;
    } else {
        if (lru->map_size == lru->capacity) {
            Node *removed = lru->link->tail->prev;
            removeNode(removed);
            lru->map[removed->key] = NULL;
            lru->map_size--;
        }

        Node *newNode = new_Node(key, value);
        addFirst(lru->link, newNode);
        lru->map[key] = newNode;
        lru->map_size++;
    }
}

void lRUCacheFree(LRUCache *lru) {
    Node *cur = lru->link->head;

    while (cur != NULL) {
        Node *next = cur->next;
        free(cur);
        cur = next;
    }

    free(lru);
}

//int main() {
//    LRUCache *lru = lRUCacheCreate(2);
//    lRUCachePut(lru, 1, 1);
//    lRUCachePut(lru, 2, 2);
//    printf("%d\n", lRUCacheGet(lru, 1));
//    lRUCachePut(lru, 3, 3);
//    printf("%d\n", lRUCacheGet(lru, 2));
//    lRUCachePut(lru, 4, 4);
//    printf("%d\n", lRUCacheGet(lru, 1));
//    printf("%d\n", lRUCacheGet(lru, 3));
//    printf("%d\n", lRUCacheGet(lru, 4));
//
//    lRUCacheFree(lru);
//
//    return 0;
//}

C++算法源码

#include <bits/stdc++.h>
using namespace std;

class Node {
public:
    int key{-1};
    int val{-1};
    Node *prev{};
    Node *next{};

    Node() = default;

    Node(int key, int val) : key(key), val(val) {}
};

class Link {
public:
    Node *head;
    Node *tail;

    Link() {
        this->head = new Node();
        this->tail = new Node();
        this->head->next = this->tail;
        this->tail->prev = this->head;
    }

    static void removeNode(Node *node) {
        node->next->prev = node->prev;
        node->prev->next = node->next;
        node->prev = nullptr;
        node->next = nullptr;
    }

    void addFirst(Node *node) const {
        node->next = this->head->next;
        this->head->next->prev = node;
        this->head->next = node;
        node->prev = this->head;
    }
};

class LRUCache {
public:
    int capacity;
    map<int, Node *> map;
    Link *link;

    explicit LRUCache(int capacity) {
        this->capacity = capacity;
        this->link = new Link();
    }

    int get(int key) {
        if (this->map.count(key) > 0) {
            Node *node = this->map[key];
            Link::removeNode(node);
            this->link->addFirst(node);
            return node->val;
        } else {
            return -1;
        }
    }

    void put(int key, int value) {
        if (this->map.count(key) > 0) {
            Node *node = this->map[key];
            Link::removeNode(node);
            this->link->addFirst(node);
            node->val = value;
        } else {
            if (this->map.size() == this->capacity) {
                Node *removed = this->link->tail->prev;
                Link::removeNode(removed);
                this->map.erase(this->map.find(removed->key));
            }

            Node *newNode = new Node(key, value);
            this->link->addFirst(newNode);
            this->map[key] = newNode;
        }
    }
};


//int main() {
//    LRUCache lru(2);
//    lru.put(1, 1);
//    lru.put(2, 2);
//    cout << lru.get(1) << endl;
//    lru.put(3, 3);
//    cout << lru.get(2) << endl;
//    lru.put(4, 4);
//    cout << lru.get(1) << endl;
//    cout << lru.get(3) << endl;
//    cout << lru.get(4) << endl;
//
//    return 0;
//}