c++ 172ms unordered_map with self-implemented queue O(1)


  • 0
    T
    class LFUCache {
    	struct Node {
    		int key;
    		int value;
    		int frequency;
    		Node *next;
    		Node *pre;
    		Node() : key(-1), value(-1), frequency(-1), next(NULL), pre(NULL) {}
    		Node(int k, int v, int fre) : key(k), value(v), frequency(fre), next(NULL), pre(NULL) {}
    		Node(const Node *node) {
    			key = node->key;
    			value = node->value;
    			frequency = node->frequency;
    			next = node->next;
    			pre = node->pre;
    		}
    	};
    	struct Queue {
    		Node *head, *last;
    		int size;
    		Queue() : size(0) {
    			head = new Node();
    			last = new Node();
    			last->pre = head;
    			head->next = last;
    		}
    		~Queue() {
    			Node *p = head->next;
    			while (p != last) {
    				Node *q = p->next;
    				delete p;
    				p = q;
    			}
    			delete head;
    			delete last;
    		}
    		void erase(Node *node) {
    			node->pre->next = node->next;
    			node->next->pre = node->pre;
    			size--;
    		}
    		void erase_front() {
    			Node *node = head->next;
    			head->next = node->next;
    			node->next->pre = head;
    			delete node;
    			size--;
    		}
    		Node* front() {
    			if (head->next == last) return NULL;
    			return head->next;
    		}
    		void insert(Node *node) {
    			last->pre->next = node;
    			node->pre = last->pre;
    			node->next = last;
    			last->pre = node;
    			size++;
    		}
    		int get_size() {
    			return size;
    		}
    	};
    	public:
    		LFUCache(int capacity) : cache_size(capacity) {
    			cache_space.push_back(new Queue());
    			cache_space_capacity = 1;
    			min_fre = 100000;
    		}
    		~LFUCache() {
    			for (int i = 0; i < cache_space_capacity; ++i) {
    				Queue *queue = cache_space[i];
    				delete queue;
    			}
    			cache_space.clear();
    		}
    		void set(int key, int value) {
    			if (cache_size == 0) return;
    			if (cache_map.count(key) == 0) {
    				if (cache_size == cache_map.size()) {
    					Queue *q = cache_space[min_fre];
    					Node *erased_node = q->front();
    					cache_map.erase(erased_node->key);
    					q->erase_front();
    					Node *node = new Node(key, value, 0);
    					cache_map[key] = node;
    					cache_space[0]->insert(node);
    					if (min_fre > 0) min_fre = 0;
    				} else {
    					Node *node = new Node(key, value, 0);
    					cache_map[key] = node;
    					cache_space[0]->insert(node);
    					if (min_fre > 0) min_fre = 0;
    				}
    			} else {
    				Node *node = cache_map[key];
    				node->value = value;
    				get(key);
    			}
    		}
    		int get(int key) {
    			if (cache_map.count(key) == 0) return -1;
    			int res_val = cache_map[key]->value;
    			Node *node = cache_map[key];
    			int cur_fre = node->frequency;
    			Queue *q = cache_space[cur_fre];
    			q->erase(node);
    
    			if (cur_fre == min_fre) {
    				if (q->get_size() == 0) min_fre++;
    			}
    
    			cur_fre++;
    			node->frequency++;
    			if (cur_fre >= cache_space_capacity) {
    				cache_space.push_back(new Queue());
    				cache_space_capacity++;
    			}
    			cache_space[cur_fre]->insert(node);
    			return res_val;
    		}
    	private:
    		std::unordered_map<int, Node*> cache_map;
    		std::vector<Queue*> cache_space;
    		int cache_size;
    		int min_fre;
    		int cache_space_capacity;
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.