LRU Cache: AC (Implement By Linked List)

sofkyle · sofkyle · commit 99361e27b89e · 2019-03-03T15:29:19.000+08:00
diff --git a/LeetCodePrj/Java/leetcode/hard/page1/HardPage1.java b/LeetCodePrj/Java/leetcode/hard/page1/HardPage1.java
@@ -0,0 +1,32 @@
+package leetcode.hard.page1;
+
+import org.junit.jupiter.api.Test;
+
+public class HardPage1 {
+    @Test
+    public void testLRUCache() {
+        /*LRUCache lruCache = new LRUCache(3);
+        lruCache.put(1,1);
+        lruCache.put(2,2);
+        lruCache.put(3,3);
+        lruCache.put(4,4);
+        lruCache.get(4);
+        lruCache.get(3);
+        lruCache.get(2);
+        lruCache.get(1);
+        lruCache.put(5,5);
+        lruCache.get(1);
+        lruCache.get(2);
+        lruCache.get(3);
+        lruCache.get(4);
+        lruCache.get(5);*/
+
+        LRUCache lruCache = new LRUCache(2);
+        lruCache.put(2,1);
+        lruCache.put(1,1);
+        lruCache.put(2,3);
+        lruCache.put(4,1);
+        lruCache.get(1);
+        lruCache.get(2);
+    }
+}
diff --git a/LeetCodePrj/Java/leetcode/hard/page1/LRUCache.java b/LeetCodePrj/Java/leetcode/hard/page1/LRUCache.java
@@ -0,0 +1,88 @@
+package leetcode.hard.page1;
+
+import java.util.HashMap;
+import java.util.Map;
+
+public class LRUCache {
+    ListNode cacheListHead;
+    ListNode cacheListTail;
+
+    Map<Integer, Integer> cache = new HashMap<>();
+    int count = 0;
+    int capacity;
+
+    public LRUCache(int capacity) {
+        this.capacity = capacity;
+    }
+
+    public int get(int key) {
+        if (count == 0 || !cache.containsKey(key)) return -1;
+
+        moveToHead(key);
+
+        return cache.get(cacheListHead.val);
+    }
+
+    public void put(int key, int value) {
+        if (!cache.containsKey(key)) {
+            if (count < capacity) {
+                // the max count is equals to capacity
+                count++;
+
+                ListNode node = new ListNode(key);
+                if (cacheListHead == null) {
+                    cacheListHead = node;
+                    cacheListTail = node;
+                } else {
+                    node.next = cacheListHead;
+                    cacheListHead = node;
+                }
+            } else {
+                cache.remove(cacheListTail.val);
+
+                ListNode newNode = new ListNode(key);
+                newNode.next = cacheListHead;
+                cacheListHead = newNode;
+
+                ListNode tmpNode = cacheListHead;
+                while (tmpNode.next != cacheListTail) {
+                    tmpNode = tmpNode.next;
+                }
+
+                tmpNode.next = null;
+                cacheListTail = tmpNode;
+            }
+        } else {
+            moveToHead(key);
+        }
+        cache.put(key, value);
+    }
+
+    private void moveToHead(int key) {
+        if (cacheListHead.val == key) {
+            return;
+        }
+
+        ListNode p = cacheListHead;
+        ListNode q = p.next;
+        while (q.val != key) {
+            p = q;
+            q = p.next;
+        }
+
+        // move q to head
+        p.next = q.next;
+        q.next = cacheListHead;
+        cacheListHead = q;
+        if (p.next == null) cacheListTail = p;
+    }
+
+    public static class ListNode {
+        public int val;
+        public ListNode next;
+        public ListNode(int x) {
+            val = x;
+            next = null;
+        }
+    }
+}
