146. LRU Cache Medium

1/**
2 * [146] LRU Cache
3 *
4 * Design a data structure that follows the constraints of a <a href="https://en.wikipedia.org/wiki/Cache_replacement_policies#LRU" target="_blank">Least Recently Used (LRU) cache</a>.
5 * Implement the LRUCache class:
6 * 
7 * 	LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
8 * 	int get(int key) Return the value of the key if the key exists, otherwise return -1.
9 * 	void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.
10 * 
11 * The functions get and put must each run in O(1) average time complexity.
12 *  
13 * Example 1:
14 * 
15 * Input
16 * ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
17 * [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
18 * Output
19 * [null, null, null, 1, null, -1, null, -1, 3, 4]
20 * Explanation
21 * LRUCache lRUCache = new LRUCache(2);
22 * lRUCache.put(1, 1); // cache is {1=1}
23 * lRUCache.put(2, 2); // cache is {1=1, 2=2}
24 * lRUCache.get(1);    // return 1
25 * lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
26 * lRUCache.get(2);    // returns -1 (not found)
27 * lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
28 * lRUCache.get(1);    // return -1 (not found)
29 * lRUCache.get(3);    // return 3
30 * lRUCache.get(4);    // return 4
31 * 
32 *  
33 * Constraints:
34 * 
35 * 	1 <= capacity <= 3000
36 * 	0 <= key <= 10^4
37 * 	0 <= value <= 10^5
38 * 	At most 2 * 10^5 calls will be made to get and put.
39 * 
40 */
41pub struct Solution {}
42
43// problem: https://leetcode.com/problems/lru-cache/
44// discuss: https://leetcode.com/problems/lru-cache/discuss/?currentPage=1&orderBy=most_votes&query=
45
46// submission codes start here
47
48struct LRUCache {
49        vec![]
50    }
51
52
53/** 
54 * `&self` means the method takes an immutable reference.
55 * If you need a mutable reference, change it to `&mut self` instead.
56 */
57impl LRUCache {
58
59    fn new(capacity: i32) -> Self {
60        
61    }
62    
63    fn get(&self, key: i32) -> i32 {
64        
65    }
66    
67    fn put(&self, key: i32, value: i32) {
68        
69    }
70}
71
72/**
73 * Your LRUCache object will be instantiated and called as such:
74 * let obj = LRUCache::new(capacity);
75 * let ret_1: i32 = obj.get(key);
76 * obj.put(key, value);
77 */
78
79// submission codes end
80
81#[cfg(test)]
82mod tests {
83    use super::*;
84
85    #[test]
86    fn test_146() {
87    }
88}
89