1
class Node {
2
    constructor(key, value) {
3
        this.key = key;
4
        this.value = value;
5
        this.freq = 1;
6
        this.prev = null;
7
        this.next = null;
8
    }
9
}
10

11
class DoublyLinkedList {
12
    constructor() {
13
        this.head = new Node(null, null);
14
        this.tail = new Node(null, null);
15
        this.head.next = this.tail;
16
        this.tail.prev = this.head;
17
        this.size = 0;
18
    }
19

20
    addToHead(node) {
21
        node.next = this.head.next;
22
        node.prev = this.head;
23
        this.head.next.prev = node;
24
        this.head.next = node;
25
        this.size++;
26
    }
27

28
    remove(node) {
29
        node.prev.next = node.next;
30
        node.next.prev = node.prev;
31
        this.size--;
32
    }
33

34
    removeTail() {
35
        if (this.size === 0) return null;
36
        const node = this.tail.prev;
37
        this.remove(node);
38
        return node;
39
    }
40
}
41

42
class LFUCache {
43
    constructor(capacity) {
44
        this.capacity = capacity;
45
        this.minFreq = 0;
46
        this.size = 0;
47
        this.keyMap = new Map();
48
        this.freqMap = new Map();
49
    }
50

51
    get(key) {
52
        if (!this.keyMap.has(key)) return -1;
53
        const node = this.keyMap.get(key);
54
        this.updateNode(node);
55
        return node.value;
56
    }
57

58
    put(key, value) {
59
        if (this.capacity === 0) return;
60

61
        if (this.keyMap.has(key)) {
62
            const node = this.keyMap.get(key);
63
            node.value = value;
64
            this.updateNode(node);
65
            return;
66
        }
67

68
        if (this.size >= this.capacity) {
69
            const minList = this.freqMap.get(this.minFreq);
70
            const deleted = minList.removeTail();
71
            this.keyMap.delete(deleted.key);
72
            this.size--;
73
        }
74

75
        const newNode = new Node(key, value);
76
        this.keyMap.set(key, newNode);
77

78
        if (!this.freqMap.has(1)) {
79
            this.freqMap.set(1, new DoublyLinkedList());
80
        }
81
        this.freqMap.get(1).addToHead(newNode);
82
        this.minFreq = 1;
83
        this.size++;
84
    }
85

86
    updateNode(node) {
87
        const oldFreq = node.freq;
88
        const oldList = this.freqMap.get(oldFreq);
89
        oldList.remove(node);
90

91
        if (oldList.size === 0 && oldFreq === this.minFreq) {
92
            this.minFreq++;
93
        }
94

95
        node.freq++;
96
        const newFreq = node.freq;
97

98
        if (!this.freqMap.has(newFreq)) {
99
            this.freqMap.set(newFreq, new DoublyLinkedList());
100
        }
101
        this.freqMap.get(newFreq).addToHead(node);
102
    }
103
}

1
use std::collections::HashMap;
2
use std::rc::Rc;
3
use std::cell::RefCell;
4

5
struct Node {
6
    key: i32,
7
    value: i32,
8
    freq: i32,
9
    prev: Option<Rc<RefCell<Node>>>,
10
    next: Option<Rc<RefCell<Node>>>,
11
}
12

13
impl Node {
14
    fn new(key: i32, value: i32) -> Self {
15
        Node {
16
            key,
17
            value,
18
            freq: 1,
19
            prev: None,
20
            next: None,
21
        }
22
    }
23
}
24

25
struct DoublyLinkedList {
26
    head: Rc<RefCell<Node>>,
27
    tail: Rc<RefCell<Node>>,
28
    size: usize,
29
}
30

31
impl DoublyLinkedList {
32
    fn new() -> Self {
33
        let head = Rc::new(RefCell::new(Node::new(0, 0)));
34
        let tail = Rc::new(RefCell::new(Node::new(0, 0)));
35
        head.borrow_mut().next = Some(tail.clone());
36
        tail.borrow_mut().prev = Some(head.clone());
37
        DoublyLinkedList { head, tail, size: 0 }
38
    }
39

40
    fn add_to_head(&mut self, node: Rc<RefCell<Node>>) {
41
        let next = self.head.borrow().next.clone();
42
        node.borrow_mut().prev = Some(self.head.clone());
43
        node.borrow_mut().next = next.clone();
44
        self.head.borrow_mut().next = Some(node.clone());
45
        next.unwrap().borrow_mut().prev = Some(node.clone());
46
        self.size += 1;
47
    }
48

49
    fn remove(&mut self, node: Rc<RefCell<Node>>) {
50
        let prev = node.borrow().prev.clone().unwrap();
51
        let next = node.borrow().next.clone().unwrap();
52
        prev.borrow_mut().next = Some(next.clone());
53
        next.borrow_mut().prev = Some(prev);
54
        self.size -= 1;
55
    }
56

57
    fn remove_tail(&mut self) -> Option<Rc<RefCell<Node>>> {
58
        if self.size == 0 {
59
            return None;
60
        }
61
        let node = self.tail.borrow().prev.clone().unwrap();
62
        self.remove(node.clone());
63
        Some(node)
64
    }
65
}
66

67
struct LFUCache {
68
    capacity: usize,
69
    min_freq: i32,
70
    size: usize,
71
    key_map: HashMap<i32, Rc<RefCell<Node>>>,
72
    freq_map: HashMap<i32, DoublyLinkedList>,
73
}
74

75
impl LFUCache {
76
    fn new(capacity: i32) -> Self {
77
        LFUCache {
78
            capacity: capacity as usize,
79
            min_freq: 0,
80
            size: 0,
81
            key_map: HashMap::new(),
82
            freq_map: HashMap::new(),
83
        }
84
    }
85

86
    fn get(&mut self, key: i32) -> i32 {
87
        match self.key_map.get(&key) {
88
            Some(node) => {
89
                let node = node.clone();
90
                self.update_node(node.clone());
91
                node.borrow().value
92
            },
93
            None => -1,
94
        }
95
    }
96

97
    fn put(&mut self, key: i32, value: i32) {
98
        if self.capacity == 0 {
99
            return;
100
        }
101

102
        if let Some(node) = self.key_map.get(&key) {
103
            let node = node.clone();
104
            node.borrow_mut().value = value;
105
            self.update_node(node);
106
            return;
107
        }
108

109
        if self.size >= self.capacity {
110
            if let Some(list) = self.freq_map.get_mut(&self.min_freq) {
111
                if let Some(tail) = list.remove_tail() {
112
                    self.key_map.remove(&tail.borrow().key);
113
                    self.size -= 1;
114
                }
115
            }
116
        }
117

118
        let new_node = Rc::new(RefCell::new(Node::new(key, value)));
119
        self.key_map.insert(key, new_node.clone());
120

121
        self.freq_map.entry(1)
122
            .or_insert_with(DoublyLinkedList::new)
123
            .add_to_head(new_node);
124

125
        self.min_freq = 1;
126
        self.size += 1;
127
    }
128

129
    fn update_node(&mut self, node: Rc<RefCell<Node>>) {
130
        let old_freq = node.borrow().freq;
131
        let new_freq = old_freq + 1;
132

133
        if let Some(list) = self.freq_map.get_mut(&old_freq) {
134
            list.remove(node.clone());
135

136
            if list.size == 0 && old_freq == self.min_freq {
137
                self.min_freq += 1;
138
            }
139
        }
140

141
        node.borrow_mut().freq = new_freq;
142
        self.freq_map.entry(new_freq)
143
            .or_insert_with(DoublyLinkedList::new)
144
            .add_to_head(node);
145
    }
146
}

1
class Node:
2
    __slots__ = ('key', 'value', 'freq', 'prev', 'next')
3
    def __init__(self, key, value):
4
        self.key = key
5
        self.value = value
6
        self.freq = 1
7
        self.prev = None
8
        self.next = None
9

10
class DoublyLinkedList:
11
    def __init__(self):
12
        self.head = Node(0, 0)
13
        self.tail = Node(0, 0)
14
        self.head.next = self.tail
15
        self.tail.prev = self.head
16
        self.size = 0
17

18
    def add_to_head(self, node):
19
        node.next = self.head.next
20
        node.prev = self.head
21
        self.head.next.prev = node
22
        self.head.next = node
23
        self.size += 1
24

25
    def remove(self, node):
26
        node.prev.next = node.next
27
        node.next.prev = node.prev
28
        self.size -= 1
29

30
    def remove_tail(self):
31
        if self.size == 0:
32
            return None
33
        node = self.tail.prev
34
        self.remove(node)
35
        return node
36

37
class LFUCache:
38
    def __init__(self, capacity: int):
39
        self.capacity = capacity
40
        self.min_freq = 0
41
        self.size = 0
42
        self.key_map = {}
43
        self.freq_map = {}
44

45
    def get(self, key: int) -> int:
46
        if key not in self.key_map:
47
            return -1
48
        node = self.key_map[key]
49
        self._update_node(node)
50
        return node.value
51

52
    def put(self, key: int, value: int) -> None:
53
        if self.capacity == 0:
54
            return
55

56
        if key in self.key_map:
57
            node = self.key_map[key]
58
            node.value = value
59
            self._update_node(node)
60
            return
61

62
        if self.size >= self.capacity:
63
            min_list = self.freq_map.get(self.min_freq)
64
            if min_list and min_list.size > 0:
65
                deleted = min_list.remove_tail()
66
                if deleted:
67
                    self.key_map.pop(deleted.key)
68
                    self.size -= 1
69

70
        new_node = Node(key, value)
71
        self.key_map[key] = new_node
72

73
        if 1 not in self.freq_map:
74
            self.freq_map[1] = DoublyLinkedList()
75
        self.freq_map[1].add_to_head(new_node)
76
        self.min_freq = 1
77
        self.size += 1
78

79
    def _update_node(self, node):
80
        old_freq = node.freq
81
        new_freq = old_freq + 1
82

83
        if old_freq in self.freq_map:
84
            old_list = self.freq_map[old_freq]
85
            old_list.remove(node)
86

87
            if old_list.size == 0 and old_freq == self.min_freq:
88
                self.min_freq += 1
89

90
        node.freq = new_freq
91

92
        if new_freq not in self.freq_map:
93
            self.freq_map[new_freq] = DoublyLinkedList()
94
        self.freq_map[new_freq].add_to_head(node)