摘要:首先要做到是,能想到的数据结构只有两三种,一个是,一个是,是,还有一个,是。不太可能,因为长度要而且不可变,题目也没说长度固定。可以做到和都是。因为还有函数,要可以,所以还需要一个数据结构来记录顺序,自然想到。
LRU Cache
题目链接:https://leetcode.com/problems...
这个题要求O(1)的复杂度。首先要做到get(key)是O(1),能想到的数据结构只有两三种,一个是HashMap
public class LRUCache { class ListNode { ListNode prev; ListNode next; int val = 0; int key = 0; ListNode() {} ListNode(int key, int val) { this.key = key; this.val = val; } } // new node(most recently) add to the tail part public void append(ListNode node) { node.prev = tail.prev; tail.prev.next = node; node.next = tail; tail.prev = node; } // least recently node need to be remove from head public void remove() { remove(head.next); } // remove the certain node public void remove(ListNode node) { node.prev.next = node.next; node.next.prev = node.prev; } ListNode head, tail; MapLFU Cachemap; int remain; public LRUCache(int capacity) { remain = capacity; // map for get map = new HashMap(); // list for put head = new ListNode(); tail = new ListNode(); head.next = tail; tail.prev = head; } public int get(int key) { if(map.containsKey(key)) { // remove the key node to the tail int value = map.get(key).val; put(key, value); return value; } else return -1; } public void put(int key, int value) { if(map.containsKey(key)) { ListNode node = map.get(key); node.val = value; remove(node); append(node); } else { // not contain, check if count > capacity // remove the least recent node in list & map if(remain == 0) { map.remove(head.next.key); remove(); remain++; } ListNode node = new ListNode(key, value); append(node); map.put(key, node); remain--; } } } /** * 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); */
题目链接:https://leetcode.com/problems...
上一题是只考虑出现的时间,这题加了frequency。那么再加一个map存freq应该是可行的。现在node除了要保存顺序还得保存freq,感觉上像是个二维的,先按freq排序再考虑出现顺序。每次得保存下这个freq出现最早的值,再出现的时候,要从这freq里删了,移到下一个freq的tail上。想了下感觉还是不太好做,看了网上的答案。
参考这个博客:
http://bookshadow.com/weblog/...
first -> point to the freqNode with freq = 1
Map
relation between freqNode:
first(freq 0) <-> freq 1 <-> freq 2 <-> ......
Map
get(key):
case 1: return -1
case 2: exist =>
find keyNode and remove from freqNode, if cur freqNode has no element, remove freqNode
find freqNode through freqMap,
find next freqNode(freq + 1) through freqNode,
add keyNode to the tail of next freqNode
put(key, value)
case 1: not exist in keyMap => add to the tail of freqNode with freq = 1
case 2: exist =>
find keyNode, set value and remove from freqNode, if cur freqNode has no element, remove freqNode
find freqNode through freqMap,
find next freqNode(freq + 1) through freqNode,
add keyNode to the tail of next freqNode
其中,keyNode和keyMap和上一题一样都是可以用LinkedHashMap来实现的。那么这里可以稍微改一下,把keyMap里面直接放
public class LFUCache { class freqNode { int freq = 0; freqNode prev, next; // store keys LinkedHashSetkeyNodes = new LinkedHashSet(); freqNode() {} freqNode(int freq) { this.freq = freq; } public int delete() { // if(keyNodes.isEmpty()) return; int key = keyNodes.iterator().next(); keyNodes.remove(key); return key; } public void delete(int key) { // if(!keyNodes.contains(key)) return; keyNodes.remove(key); } public void append(int key) { keyNodes.add(key); } } int remain; // key, freqNode pair Map freqMap; // key, value pair Map keyMap; freqNode first; freqNode last; public LFUCache(int capacity) { this.remain = capacity; freqMap = new HashMap(); keyMap = new HashMap(); first = new freqNode(); last = new freqNode(); first.next = last; last.next = first; } public int get(int key) { if(!keyMap.containsKey(key)) return -1; else { updateFreq(key); return keyMap.get(key); } } public void put(int key, int value) { if(!keyMap.containsKey(key)) { if(remain == 0) { if(first.next.freq == 0) return; // remove the least frequent int del = first.next.delete(); keyMap.remove(del); freqMap.remove(del); remain++; } // update map and add node keyMap.put(key, value); update(first, key); remain--; } else { updateFreq(key); keyMap.put(key, value); } } private void updateFreq(int key) { freqNode node = freqMap.get(key); update(node, key); // remove current node if has no keyNodes node.delete(key); if(node.keyNodes.size() == 0) { removeNode(node); } } private void update(freqNode node, int key) { // append to the next freq addAfterNode(node); node.next.append(key); // update freqMap key with next freqNode freqMap.put(key, node.next); } private void addAfterNode(freqNode node) { if(node.next.freq != node.freq + 1) { freqNode newNode = new freqNode(node.freq + 1); freqNode temp = node.next; node.next = newNode; newNode.prev = node; temp.prev = newNode; newNode.next = temp; node = null; } } private void removeNode(freqNode node) { node.prev.next = node.next; node.next.prev = node.prev; } } /** * Your LFUCache object will be instantiated and called as such: * LFUCache obj = new LFUCache(capacity); * int param_1 = obj.get(key); * obj.put(key,value); */
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/66567.html
摘要:在静态的频率分布下,性能也落后于因为其不再为不在缓存中的数据维护任何频率数据。可以详见的准入淘汰策略是新增一个新的元素时,判断使用该元素替换一个旧元素,是否可以提升缓存命中率。 1. Introduction LFU的局限: LFU实现需要维护大而复杂的元数据(频次统计数据等) 大多数实际工作负载中,访问频率随着时间的推移而发生根本变化(这是外卖业务不适合朴素LFU的根本原因) 针...
摘要:在静态的频率分布下,性能也落后于因为其不再为不在缓存中的数据维护任何频率数据。可以详见的准入淘汰策略是新增一个新的元素时,判断使用该元素替换一个旧元素,是否可以提升缓存命中率。 1. Introduction LFU的局限: LFU实现需要维护大而复杂的元数据(频次统计数据等) 大多数实际工作负载中,访问频率随着时间的推移而发生根本变化(这是外卖业务不适合朴素LFU的根本原因) 针...
摘要:缓存算法我是,我会统计每一个缓存数据的使用频率,我会把使用最少的缓存替换出缓存区。浏览器就是使用了我作为缓存算法。在缓存系统中找出最少最近的对象是需要较高的时空成本。再来一次机会的缓存算法,是对的优化。直到新的缓存对象被放入。 缓存 什么是缓存? showImg(https://segmentfault.com/img/bVusZg); 存贮数据(使用频繁的数据)的临时地方,因为取原始...
阅读 3217·2023-04-25 22:47
阅读 3722·2021-10-11 10:59
阅读 2272·2021-09-07 10:12
阅读 4213·2021-08-11 11:15
阅读 3403·2019-08-30 13:15
阅读 1713·2019-08-30 13:00
阅读 926·2019-08-29 14:02
阅读 1629·2019-08-26 13:57