leetCode/leetCode_146.java at master · mehtabgill/leetCode · 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
class LRUCache {

    class Node {
        int key;
        int val;
        Node post;
        Node pre;

        public Node(int key, int value){
            this.key = key;
            this.val = value;
            this.post = null;
            this.pre = null;
        }

    }

    private void moveToHead(Node node){

        removeNode(node);

        addAtHead(node);
    }

    private void addAtHead(Node node){
        Node head_post = head.post;

        node.post = head_post;

        head.post = node;

        node.pre = head;

        head_post.pre = node;
    }

    private void removeNode(Node node){

        Node pre = node.pre;
        Node post = node.post;

        pre.post = post;
        post.pre = pre;

    }
    private Node removeTail(){
       Node res = tail.pre;

        removeNode(res);

        return res;
    }


    HashMap<Integer, Node> map = new HashMap<>();
    // private variables
    private Node head, tail;
    int capacity;


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

        head = new Node(0,0);

        tail = new Node(0,0);

        head.post = tail;
        tail.pre = head;
    }

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

        Node temp = map.get(key);

        moveToHead(temp);

        return temp.val;
    }

    public void put(int key, int value) {
        if(map.containsKey(key)){
            Node node = map.get(key);
            node.val =value;
            moveToHead(node);
        }else{
            Node newNode = new Node(key, value);
            map.put(key, newNode);
            addAtHead(newNode);
            if(map.size() > this.capacity){
                Node toRemove = removeTail();
                map.remove(toRemove.key);
            }
        }
    }
}

/**
 * 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);
 */