LeetCode-Algorithms/0146. LRU Cache at main · daniel-tomberg/LeetCode-Algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
https://leetcode.com/problems/lru-cache/description/

Time: O(1)
Space: O(capacity) for Linked List & HashMap

class LRUCache {
    private int capacity;
    private Map<Integer, Node> map = new HashMap<>();
    private Node head;
    private Node tail;

    public LRUCache (int capacity){
        this.capacity = capacity;
    }

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

    public void put(int key, int value) {
        if(map.containsKey(key)){
            Node node = map.get(key);
            node.val = value;
            moveToTail(node);
        } else {
            Node node = new Node(key, value);
            if(map.size() < capacity){
                addToTail(node);
            } else {
                map.remove(head.key);
                removeHead();
                addToTail(node);
            }
        map.put(key, node);
        }
    }

    public void moveToTail (Node node){
        if (node != tail){
            if (node != head){
                node.left.right = node.right;
                node.right.left = node.left;
                tail.right = node;
                node.left = tail;
                tail = node;
                tail.right = null;
            } else {
                Node prevHead = removeHead();
                tail.right = prevHead;
                prevHead.left = tail;
                tail = prevHead;
            }
        }
    }

    public void addToTail (Node node){
        if (head != null){
            tail.right = node;
            node.left = tail;
        } else {
            head = node;
        }
        tail = node;
    }

    public Node removeHead (){
        if (tail == head){
            head = null;
            tail = null;
            return null;
        } else {
            Node prevHead = head;
            head = head.right;
            head.left = null;
            prevHead.right = null;
            return prevHead;
        }
    }


    public static class Node {
        int key;
        int val;
        Node left;
        Node right;
        Node(int key, int val){
            this.key = key;
            this.val = val;
        }
    }
}

//Short Version
//class LRUCache {
//    private final Map<Integer, Integer> cache;
//
//    public LRUCache(int capacity) {
//        this.cache = new LinkedHashMap<Integer, Integer> (capacity, 0.75f, true){
//            @Override
//            protected boolean removeEldestEntry(Map.Entry<Integer, Integer> entry){
//               return size() > capacity;
//            }
//        };
//    }
//
//    public int get(int key) {
//        return cache.getOrDefault(key, -1);
//    }
//
//    public void put(int key, int value) {
//        cache.put(key, value);
//    }
//}