Leetcode: LRU Cache

这是我最近做到的一道比较有意思的题目,在这里写一点儿自己的想法。

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set. get(key) – Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. set(key, value) – Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

这是一道系统设计题,实现起来并不复杂,想法是通过HashTable实现get方法(因为hash table的get操作可以做到O(1)),通过list实现set方法(基于和get方法一样的考虑,使得set操作的时间复杂度降到O(1))。现在要把hash和list结合起来,于是想到我们可以直接把hash的value值设置成一个存有next node、previous node和integer value的node数据结构。注意:这里如果使用java的ArrayList的remove和add方法的话会出现Time Limit Exceeded的问题,原因是ArrayList内建remove方法和add方法的时间复杂度是O(n)。

关于java中HashTable和HashMap的区别,我找到了一个简单的答案

  1. HashMap是非线程安全的,HashTable是线程安全的。
  2. HashMap的键和值都允许有null值存在,而HashTable则不行。
  3. 因为线程安全的问题,HashMap效率比HashTable的要高。

具体的原因就要深入到它们实现了,这个之后有时间要去研究一下。

下面是我AC的代码,写得好难看,汗==

Be First to Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注