LeetCode 146. LRU 缓存

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

🔥 146. LRU 缓存

思路分析

Java 通过继承 LinkedHashMap 实现

Golang 通过使用 container/list 和 map 来实现

自定义双向链表+哈希表

参考代码

type LRUCache struct {
	capacity int
	cache    map[int]*Node
	head     *Node
	tail     *Node
}

type Node struct {
	key   int
	value int
	prev  *Node
	next  *Node
}

func Constructor(capacity int) LRUCache {
	head := &Node{}
	tail := &Node{}
	head.next = tail
	tail.prev = head
	return LRUCache{
		capacity: capacity,
		cache:    make(map[int]*Node),
		head:     head,
		tail:     tail,
	}
}

func (this *LRUCache) Get(key int) int {
	if node, ok := this.cache[key]; ok {
		this.moveToHead(node)
		return node.value
	}
	return -1
}

func (this *LRUCache) Put(key int, value int) {
	if node, ok := this.cache[key]; ok {
		node.value = value
		this.moveToHead(node)
	} else {
		if len(this.cache) >= this.capacity {
			this.removeTail()
		}
		newNode := &Node{key: key, value: value}
		this.cache[key] = newNode
		this.addToHead(newNode)
	}
}

func (this *LRUCache) moveToHead(node *Node) {
	this.removeNode(node)
	this.addToHead(node)
}

func (this *LRUCache) removeNode(node *Node) {
	node.prev.next = node.next
	node.next.prev = node.prev
}

func (this *LRUCache) addToHead(node *Node) {
	node.prev = this.head
	node.next = this.head.next
	this.head.next.prev = node
	this.head.next = node
}

func (this *LRUCache) removeTail() {
	lastNode := this.tail.prev
	this.removeNode(lastNode)
	delete(this.cache, lastNode.key)
}

🍏 点击查看 Java 题解(一)

class Node {
    int key, val;
    Node next, prev;

    public Node() {
    }

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

class LRUCache {
    private final int capacity;
    private final Map<Integer, Node> cache;
    private final Node head;
    private final Node tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();
        this.head = new Node();
        this.tail = new Node();
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }

    public int get(int key) {
        if (cache.containsKey(key)) {
            Node node = cache.get(key);
            moveToHead(node);
            return node.val;
        }
        return -1;
    }

    public void put(int key, int val) {
        if (cache.containsKey(key)) {
            Node node = cache.get(key);
            moveToHead(node);
            node.val = val;
        } else {
            if (cache.size() >= capacity) {
                Node lastNode = removeTail();
                cache.remove(lastNode.key);
            }
            Node newNode = new Node(key, val);
            cache.put(key, newNode);
            addToHead(newNode);
        }
    }

    // 将节点移到头部，表示最近使用
    private void moveToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }

    // 移除节点
    private void removeNode(Node node) {
        node.next.prev = node.prev;
        node.prev.next = node.next;
    }

    // 移除尾部节点，返回被移除的节点
    private Node removeTail() {
        Node lastNode = tail.prev;
        removeNode(lastNode);
        return lastNode;
    }

    // 将节点添加到头部，表示最近使用
    private void addToHead(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }
}

🍏 点击查看 Java 题解(二)

class LRUCache extends LinkedHashMap<Integer, Integer> {
    private final int capacity;

    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    public int get(int key) {
        return this.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        super.put(key, value);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return this.size() > capacity;
    }
}

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/17639942