LeetCode 146. LRU 缓存

146. LRU 缓存

解题思路

参考代码

class LRUCache {

    public class Node {
        int key, val;
        Node pre;
        Node next;

        public Node() {}

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

    public class MyList {
        Node head = new Node(0,0);
        Node tail = new Node(0,0);

        public MyList() {
            head.next = tail;
            tail.pre = head;
        }

        public void headInsert(Node node) {
            node.next = head.next;
            node.pre = head;
            head.next.pre = node;
            head.next = node;
        }

        public void remove(Node node) {
            Node nodePre = node.pre;
            Node nodeNext = node.next;
            nodePre.next = nodeNext;
            nodeNext.pre = nodePre;
        }

        public Node removeLast() {
            Node nodeLast = tail.pre;
            remove(nodeLast);
            return nodeLast;
        }
    }

    public int capacity;
    public Map<Integer, Node> map;
    public MyList myList;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        myList = new MyList();
    }
    
    public int get(int key) {
        if(!map.containsKey(key)) {
            return -1;
        }
        Node node = map.get(key);
        myList.remove(node);
        myList.headInsert(node);
        return node.val;
    }
    
    public void put(int key, int value) {
        // 存在
        if(map.containsKey(key)) {
            Node node = map.get(key);
            node.val = value;
            myList.remove(node);
            myList.headInsert(node);
        } else {
            Node node = new Node(key, value);
            if(map.size() == capacity) {
                Node last = myList.removeLast();
                map.remove(last.key);
            }
            myList.headInsert(node);
            map.put(key, node);
        }

    }
}

ACM 模式

package main.java.mid;

import java.util.*;

public class LRU {

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

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

    class DList {
        Node head;
        Node tail;

        public DList() {
            head = new Node(0,0);
            tail = new Node(0,0);
            head.next = tail;
            tail.pre = head;
        }

        public void headInsert(Node node) {
            node.next = head.next;
            head.next.pre = node;
            head.next = node;
            node.pre = head;
        }

        public void remove(Node node) {
            Node preNode = node.pre;
            Node nxtNode = node.next;
            preNode.next = nxtNode;
            nxtNode.pre = preNode;
        }

        public Node removeLast() {
            Node lastNode = tail.pre;
            remove(lastNode);
            return lastNode;
        }
    }

    public int capacity;
    public Map<Integer, Node> map;
    public DList dList;

    public LRU(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        dList = new DList();
    }

    public int get(int key) {
        if(!map.containsKey(key)) {
            return -1;
        }
        Node node = map.get(key);
        dList.remove(node);
        dList.headInsert(node);
        return node.val;
    }

    public void put(int key, int value) {
        if(!map.containsKey(key)) {
            Node node = new Node(key, value);
            if(map.size() >= capacity) {
                Node lastNode = dList.removeLast();
                map.remove(lastNode.key);
            }
            dList.headInsert(node);
            map.put(key, node);
        } else {
            Node node = map.get(key);
            dList.remove(node);
            node.val = value;
            dList.headInsert(node);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int capacity = sc.nextInt();
        int n = sc.nextInt();
        sc.nextLine();  // 消耗换行符

        LRU cache = new LRU(capacity);
        for(int i = 0; i < n; i ++) {
            String[] parts = sc.nextLine().split(" ");
            if (parts[0].equals("put")) {
                int key = Integer.parseInt(parts[1]);
                int value = Integer.parseInt(parts[2]);
                cache.put(key, value);
            } else if (parts[0].equals("get")) {
                int key = Integer.parseInt(parts[1]);
                System.out.println(cache.get(key));
            }
        }
        sc.close();
    }
}

变体——带 TTL 的 LRU 缓存 ACM 模式

package main.java.mid;

import java.util.*;
import java.util.concurrent.locks.ReentrantLock;

public class LRUWithTTL {

    private final ReentrantLock lock = new ReentrantLock();

    class Node {
        int key, val;
        long expireTime;
        Node pre;
        Node next;

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

    class DList {
        Node head;
        Node tail;

        public DList() {
            head = new Node(0,0,0);
            tail = new Node(0,0,0);
            head.next = tail;
            tail.pre = head;
        }

        public void headInsert(Node node) {
            node.next = head.next;
            head.next.pre = node;
            head.next = node;
            node.pre = head;
        }

        public void remove(Node node) {
            Node preNode = node.pre;
            Node nxtNode = node.next;
            preNode.next = nxtNode;
            nxtNode.pre = preNode;
        }

        public Node removeLast() {
            Node lastNode = tail.pre;
            remove(lastNode);
            return lastNode;
        }
    }

    public int capacity;
    public Map<Integer, Node> map;
    public DList dList;

    public LRUWithTTL(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        dList = new DList();
    }

    public int get(int key) {
        lock.lock();
        try {
            if(!map.containsKey(key)) {
            return -1;
            }

            Node node = map.get(key);
            // 判断是否过期
            if (node.expireTime < System.currentTimeMillis()) {
                dList.remove(node);
                map.remove(key);
                return -1;
            }
            // 更新访问时间
            node.expireTime = System.currentTimeMillis() + 60000; // 1分钟 TTL
            dList.remove(node);
            dList.headInsert(node);
            return node.val;
        } finally {
            lock.unlock();
        }
    }

    public void put(int key, int value) {
        lock.lock();
        try {
            if(!map.containsKey(key)) {
                Node node = new Node(key, value, System.currentTimeMillis() + 60000); // 1分钟 TTL
                if(map.size() >= capacity) {
                    Node lastNode = dList.removeLast();
                    map.remove(lastNode.key);
                }
                dList.headInsert(node);
                map.put(key, node);
            } else {
                Node node = map.get(key);
                dList.remove(node);
                node.val = value;
                node.expireTime = System.currentTimeMillis() + 60000; // 1分钟 TTL
                dList.headInsert(node);
            }
        } finally {
            lock.unlock();
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int capacity = sc.nextInt();
        int n = sc.nextInt();
        sc.nextLine();  // 消耗换行符

        LRUWithTTL cache = new LRUWithTTL(capacity);
        for(int i = 0; i < n; i ++) {
            String[] parts = sc.nextLine().split(" ");
            if (parts[0].equals("put")) {
                int key = Integer.parseInt(parts[1]);
                int value = Integer.parseInt(parts[2]);
                cache.put(key, value);
            } else if (parts[0].equals("get")) {
                int key = Integer.parseInt(parts[1]);
                System.out.println(cache.get(key));
            }
        }

        sc.close();
    }
}