By

文章目录

Problem:
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.

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
public class LRUCache {
    
    private HashMap<Integer,Integer> _cache;
	
	private int _capacity;
	
	private Node _head=null;
	
	private Node _end=null;
	
	public LRUCache(int capacity) {
		
		this._head=new Node();
		this._end=new Node();
		
		this._head.next=this._end;
		this._end.next=null;
		
		this._capacity=capacity;
		this._cache=new HashMap<Integer,Integer>(capacity);
    }
    
    public int get(int key) {
    	int ret=-1;
    	
        if(this._cache.containsKey(key))
        {
        	ret=this._cache.get(key);
        	this.moveToFirst(key);
        }
        	
        	
        return ret;
    }
    
    public void set(int key, int value) {
        if(!this._cache.containsKey(key))
        {
        	if(_cache.size()>=this._capacity)
        	{
        		this._cache.remove(this.popKey());
        	}
        	
        	this.insertToFirst(key);
         }else{
        	this.moveToFirst(key);
         }
        
        this._cache.put(key, value);
    }
    
    private void moveToFirst(Integer key)
    {
    	Node node=this._head;
    	Node node2=null;
    	
    	while(node.next!=null)
    	{
    		
    		if(key.equals(node.key))
    		{
    			break;
    		}
    		node2=node;
    		node=node.next;
    	}
    	
    	node2.next=node.next;
    	node.next=this._head.next;
    	this._head.next=node;
    }
    
    private void insertToFirst(Integer key)
    {
    	Node node=new Node(key);
    	node.next=this._head.next;
    	this._head.next=node;
    	
    }
    
    
    private Integer popKey()
    {
    	int key=-1;
    	Node node=this._head;
    	Node node2=null;
    	
    	while(node.next!=this._end)
    	{
    		node2=node;
    		node=node.next;
    	}
    	
    	key=node.key;
    	node2.next=this._end;
    	
    	return key;
    }
    
    
    
    
    class Node{
    	public Integer key;
    	    	
    	public Node next;
    	
    	public Node()
    	{
    		
    	}
    	
    	public Node(Integer key)
    	{
    		this.key=key;
    	}
    	
    	public Node clone(){
    		Node node=new Node();
    		node.key=this.key;
    		node.next=this.next;
    		
    		return node;
    	}
    }
}

其实在Java中最方便实现LRUCache的方法就是使用LinkedHashMap，天然的集成了该功能，但是LeetCode在这题中并没有引用LinkedHashMap的包，-_-

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
public class LRUCache extends LinkedHashMap<Integer,Integer> {
    private int maxCacheNum=10;
	
	public LRUCache(int capacity)
	{
		super(capacity,0.75f,true);//这里第三个参数一定要为true，这样就表示该LinkedHashMap是使用了访问速度来链表
		this.maxCacheNum=capacity;
	}
	
	public int get(int key) {
        if(super.containsKey(key))
        {
        	return super.get(key);
        }else{
        	return -1;
        }
    }
    
    public void set(int key, int value) {
        super.put(key, value);
    }
	
	/**
	 * 重写删除最少用元素的方法
	 */
	@Override 
	protected boolean removeEldestEntry(Map.Entry<Integer,Integer> eldest) {
        return this.size()>maxCacheNum;
    }
}

本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权kubiCode，并且，不得用于商业用途。如您有任何疑问或者授权方面的协商，请给我留言。

文章目录