1. 使用LinkedList实现
import java.util.LinkedList;public class Main {public static void main(String[] args) throws Exception {cacheLRU cache = new cacheLRU(3);cache.add(1);cache.add(2);cache.add(3);System.out.print(cache.get(1));System.out.print(cache.get(2));System.out.println(cache.get(3));// 123 3->2->1cache.add(4); // 4->3->2System.out.print(cache.get(2));System.out.print(cache.get(3));System.out.print(cache.get(4));// 234 4->3->2}
}class cacheLRU {LinkedList<Integer> linkedList = new LinkedList<>();private int cap;public cacheLRU(int cap) {this.cap = cap;}public boolean add(Integer num) {if (linkedList.size() >= cap) {linkedList.removeLast();}linkedList.addFirst(num);return true;}public int get(Integer num) {if (!linkedList.contains(num)) {return -1;}linkedList.remove(num);add(num);return num;}
}2. 双向链表+哈希表 力扣146
力扣原题点这
class LRUCache {int size;int cap;HashMap<Integer, Node> map;Node head = new Node();Node tail = new Node();class Node {Node pre;Node next;int key;int value;public Node() {}public Node(int key, int value) {this.key = key;this.value = value;this.pre = null;this.next = null;}}public LRUCache(int cap) {this.size = 0;this.cap = cap;this.map = new HashMap<Integer, Node>(cap);this.head.next = tail;this.tail.pre = head;}public void put(int key, int value) {Node node = map.get(key);if (node != null) {node.value = value;moveToHead(node);} else {Node newNode = new Node(key, value);map.put(key, newNode);addToHead(newNode);size++;if (size > cap) {Node tailpre = removeLast();map.remove(tailpre.key);size--;}}}public int get(int key) {Node node = map.get(key);if (node == null) {return -1;}moveToHead(node);return node.value;}private void addToHead(Node node) {node.pre = head;node.next = head.next;head.next.pre = node;head.next = node;}private void removeNode(Node node) {node.pre.next = node.next;node.next.pre = node.pre;}private void moveToHead(Node node) {removeNode(node);addToHead(node);}private Node removeLast() {Node tailpre = tail.pre;removeNode(tailpre);return tailpre;}
}/*** Your LRUCache object will be instantiated and called as such:* LRUCache obj = new LRUCache(capacity);* int param_1 = obj.get(key);* obj.put(key,value);*/