LeetCode - Algorithms - 146. LRU Cache

这题是 Top Interview Questions 及 Top 100 Liked Questions之一，前后又花了一个星期。

先是了解了下 Cache replacement policies，其中提及 General implementations of Least recently used (LRU) require keeping “age bits” for cache-lines and track the “Least Recently Used” cache-line based on age-bits.

题目里提示 Could you do both operations in O(1) time complexity? ，又了解了下Time complexity。又在kindle上翻了下《算法图解》，了解了下散列表、链表等数据结构，也算加强了下对哈希表的认识。

在平均情况下， 散列表执行各种操作的时间都为O(1)。 O(1)被称为常量时间。你以前没有见过 常量时间，它并不意味着马上，而是说不管散列表多大，所需的时间都相同。

实际上，你以前见过常量时间——从数组中获取一个元素所需的时间就是固定的：不管数组多大，从中获取一个元素所需的时间都是相同的。

填装因子(load factor)度量的是散列表中有多少位置是空的。填装因子越低，发生冲突的可能性越小，散列表的性能越高。一个不错的经验规则是：一旦填装因子大于0.7，就调整散列表的长度。

自己琢磨也是徒劳，不如上网找点提示信息，在quora上找到几条信息

Typically LRU cache is implemented using a doubly linked list and a hash map.

An LRU Cache should support fast lookup. Apparently, in order to achieve fast lookup, we need to use Hashtable or HashMap.Also, an LRU Cache requires that insert and delete operations should be in O(1) time. The obvious choice for this requirement is Linked List. Linked List support insert/delete operations in O(1) time if we have the reference of element. While building an LRU cache requires that you think in terms of these two data structures. The reality is that these two data structures actually work coherently to achieve the design.So, we are finalizing on these data structures: HashMap and Doubly Linked List. HashMap holds the keys and values as reference of the nodes (entries) of Doubly Linked List.Doubly Linked List is used to store list of nodes (entries) with most recently used node at the head of the list. So, as more nodes are added to the list, least recently used nodes are moved to the end of the list with node at tail being the least recently used in the list.

自己对java集合类库还是不够熟悉，看到Is there any doubly linked list implementation in Java?才明白原来java.util.LinkedList本来就可以当双向链表使用，

Doubly-linked list implementation of the List and Deque interfaces. Implements all optional list operations, and permits all elements (including null).All of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.

在leetcode上提交了两次，终于运行通过，如果自己来实现双向链表是不是更能提高性能? 做了这些题，感觉leetcode的算法题不是那种难得要死的题，不会做说明你的数据结构和算法知识还比较欠缺。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class LRUCache {
	private LinkedList<DualLinkNode> list;
	private Map<Integer,DualLinkNode> map;
	private final int cacheSize;

    public LRUCache(int capacity) {
    	list = new LinkedList<DualLinkNode>();
    	map = new HashMap<Integer,DualLinkNode>();
    	this.cacheSize = capacity;
    }

    public int get(int key) {
    	if (map.containsKey(key)) {
    		DualLinkNode node = map.get(key);
    		list.remove(node);
    		list.addFirst(node);
    		return node.val;
    	}
    	else {
    		return -1;
    	}
    }

    public void put(int key, int value) {
    	if (map.containsKey(key)) {
    		DualLinkNode node = map.get(key);
    		list.remove(node);
    		node.val=value;
    		list.addFirst(node);
    	}
    	else {
			if (list.size()==cacheSize) {
				DualLinkNode node = list.pollLast();
				map.remove(node.key);
			}
			DualLinkNode node = new DualLinkNode(key,value);
			list.addFirst(node);
			map.put(key, node);
    	}
    }

	private class DualLinkNode {
		public int key;
		public int val;

		public DualLinkNode(int key, int val) {
			super();
			this.key = key;
			this.val = val;
		}
	}
}

Submission Detail

  • 18 / 18 test cases passed.
  • Your runtime beats 7.69 % of java submissions.