leetcode146. LRU缓存机制

146. LRU缓存机制

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果关键字 (key) 存在于缓存中，则获取关键字的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字/值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作？

示例:

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得关键字 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得关键字 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4

JAVA解法：

主要思路是维护一个hashMap和一个双向链表，记得删除node和删除map中的元素

package Lru;

import java.util.HashMap;

public class LRUCache {

    private HashMap<Integer, Node> map;
    private int capcity;
    private Node head;//头指针
    private Node tail;//尾指针

    static class Node {
        int key;
        int val;
        Node pre;
        Node next;

        Node() {
            this.key = -1;
            this.val = -1;
        }

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

        public String toString() {
            return key + "" + val;
        }
    }

    LRUCache(int capacity) {
        this.capcity = capacity;
        map = new HashMap<>(capacity);

        head = new Node();
        tail = new Node();
        head.next = tail;
        head.pre = null;
        tail.pre = head;
        tail.next = null;
    }

    public String toString() {
        return map.toString();
    }

    public void put(int key, int value) {
        Node node = map.get(key);
        if (node == null) {
        	//插入
            if (map.size() >= capcity) {
            //超出容量
                removeLast();
            }
            node = new Node(key, value);
        }
        //更新
        node.val = value;
        moveToHead(node);
    }

    private void removeLast() {
        if (tail.pre == head) {
            return;
        }
        Node last = tail.pre;
        last.pre.next = tail;
        tail.pre = last.pre;
        //记得删除map中的元素
        map.remove(last.key);
    }

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

    private void moveToHead(Node node) {
    	//先删除
        removeNode(node);
        //再挪到head
        Node firstNext = head.next;
        head.next = node;
        node.pre = head;
        node.next = firstNext;
        firstNext.pre = node;
        map.put(node.key, node);
    }

    private void removeNode(Node node) {
        if (map.get(node.key) == null || node == head || node == tail) {
            return;
        }
        Node preNode = node.pre;
        Node nextNode = node.next;

        preNode.next = nextNode;
        nextNode.pre = preNode;
        map.remove(node.key);
    }
}

本文地址：https://blog.csdn.net/m0_37561165/article/details/109273233