FilesExpand file tree

 master

/

LRUCache.java

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

40 lines (36 loc) · 1.3 KB

 master

/

LRUCache.java

Top

File metadata and controls

• Code
• Blame

40 lines (36 loc) · 1.3 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

/*

Author: Andy, nkuwjg@gmail.com

Date: March 12, 2014

Problem: LRU Cache

Difficulty: Hard

Source: http://oj.leetcode.com/problems/lru-cache/

Notes:

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.

Solution: Hash + list.

*/

import java.util.LinkedHashMap;

import java.util.Map;

public class LRUCache {

private Map<Integer, Integer> map;

private int capacity;

public LRUCache(int capacity) {

this.capacity = capacity;

map = new LinkedHashMap<Integer, Integer>(capacity + 1);

}

public int get(int key) {

Integer val = map.get(key);

if (val == null) return -1;

map.remove(key);

map.put(key, val);

return val;

}

public void set(int key, int value) {

map.remove(key);

map.put(key, value);

if (map.size() > capacity)

map.remove(map.entrySet().iterator().next().getKey());

}

}