需求说明

如果指定的key存在于缓存中#xff0c;则返回与该键关联的值觉得有难度而且很考验数据结构与算法的功底因此Mark一下。

需求说明

缓存具有固定的容量当达到该容量时score最小的密钥必须失效直到密钥的数量落在缓存容量之内。

weight

缓存的实现需要get(key)的时间复杂度为O(1)。

为了实现高速缓存您可以假设可用一些常见的数据结构如数组、不同类型的列表和哈希表。

在答案的最后给出并解释get(key)和放入put(key)的计算复杂度

首先一说到get和put肯定会想到哈希map并且哈希的get时间复杂度也为O(1),符合要求但比较棘手的需求是如何实现缓存的score机制当缓存满的时候需要让score最低的节点drop掉。

苦思冥想之后我想到了优先队列(priority

queue)平时觉得这个数据结构很冷门但确实有应用场景优先队列是一种根据权重进行出队顺序排列的队列那么我只需要将题目中的score定位为权重就行了。

此时我又想到了用JAVA中的Comparator去定义一个这样的权重策略因为优先队列的权重是可以被Comparator重写的。

所以我总共需要用到两个数据结构。

用hashmap实现get和put的一一对应同时将节点存入优先队列当容量满时让score小的出队就行了。

注意Java中优先队列是权重小的先出队

import

PriorityQueue(timeWeightComparator);}public

int

(!nodeMap.containsKey(key)){return

-1;}Node

nodeMap.get(key);getNode.timeStamp

timeStamp;return

(nodeMap.containsKey(key)){Node

newNode

null;nodeMap.remove(leastNode.key);}Node

newNode

timeStamp);prque.add(newNode);nodeMap.put(key,newNode);}}public

static

Cache(5);cache.put(0,15,3);cache.put(1,28,10);cache.put(2,16,4);cache.put(3,4,6);cache.put(4,75,5);cache.put(4,100,100);System.out.println(cache.get(1));System.out.println(cache.get(2));System.out.println(cache.get(3));System.out.println(cache.get(4));System.out.println(cache.get(0));}

}BigO