由于面试手撕lru没撕出来，导致心态炸裂，今天特地练习了lru输入输出
手撕版，在每个函数里手动加上输出
public class LC146 {static class LRUCache{class Node{int key, value;Node prev, next;Node(int key, int value){this.key = key;this.value = value;}}private Node dummy = new Node(0,0);private int capacity;private Map<Integer, Node> map = new HashMap<Integer, Node>();public LRUCache(int capacity){this.capacity = capacity;dummy.prev = dummy;dummy.next = dummy;System.out.print("null,");}public int get(int key) {Node node = getNode(key);if(node == null){System.out.print("-1,");return -1;}else{System.out.print(node.value+",");return node.value;}}private Node getNode(int key) {Node node = map.getOrDefault(key, null);if(node == null){return null;}deleteNode(node);pushFront(node);return node;}private void deleteNode(Node node) {node.next.prev = node.prev;node.prev.next = node.next;}private void pushFront(Node node) {node.next = dummy.next;node.prev = dummy;node.prev.next = node;node.next.prev = node;}public void put(int key, int value) {Node node = getNode(key);if(node != null){node.value = value;return ;}node = new Node(key, value);pushFront(node);map.put(key, node);if(map.size() > capacity){map.remove(dummy.prev.key);deleteNode(dummy.prev);}System.out.print("null,");}}public static void main(String[] args) {LRUCache lRUCache = new LRUCache(2);lRUCache.put(1, 1); // 缓存是 {1=1}lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}lRUCache.get(1); // 返回 1lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}lRUCache.get(2); // 返回 -1 (未找到)lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}lRUCache.get(1); // 返回 -1 (未找到)lRUCache.get(3); // 返回 3lRUCache.get(4); // 返回 4}
}leetcode输入输出格式版
public class LC146 {static class LRUCache{class Node{int key, value;Node prev, next;Node(int key, int value){this.key = key;this.value = value;}}private Node dummy = new Node(0,0);private int capacity;private Map<Integer, Node> map = new HashMap<Integer, Node>();public LRUCache(int capacity){this.capacity = capacity;dummy.prev = dummy;dummy.next = dummy;System.out.print("null,");}public int get(int key) {Node node = getNode(key);if(node == null){System.out.print("-1,");return -1;}else{System.out.print(node.value+",");return node.value;}}private Node getNode(int key) {Node node = map.getOrDefault(key, null);if(node == null){return null;}deleteNode(node);pushFront(node);return node;}private void deleteNode(Node node) {node.next.prev = node.prev;node.prev.next = node.next;}private void pushFront(Node node) {node.next = dummy.next;node.prev = dummy;node.prev.next = node;node.next.prev = node;}public void put(int key, int value) {Node node = getNode(key);if(node != null){node.value = value;return ;}node = new Node(key, value);pushFront(node);map.put(key, node);if(map.size() > capacity){map.remove(dummy.prev.key);deleteNode(dummy.prev);}System.out.print("null,");}}public static void main(String[] args) {String[] s = new String[]{"LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"};int[][] inputs = new int[][]{{2}, {1, 1}, {2, 2}, {1}, {3, 3}, {2}, {4, 4}, {1}, {3}, {4}};int n = s.length;LRUCache lruCache = null;for(int i=0; i<n; i++){if(s[i].equals("LRUCache")){lruCache = new LRUCache(inputs[i][0]);System.out.print("null");}else if(s[i].equals("put")){lruCache.put(inputs[i][0], inputs[i][1]);System.out.print("null");}else if(s[i].equals("get")){int ans = lruCache.get(inputs[i][0]);System.out.print(ans);}if(i != n-1){System.out.print(",");}}}
}测试结果
