欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

leetcode146. LRU缓存机制

程序员文章站 2022-12-04 23:25:28
LRU缓存机制运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put 。获取数据 get(key) - 如果关键字 (key) 存在于缓存中,则获取关键字的值(总是正数),否则返回 -1。写入数据 put(key, value) - 如果关键字已经存在,则变更其数据值;如果关键字不存在,则插入该组「关键字/值」。当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间。进阶:....

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

相关标签: leetcode java