Home Computer Science Java Algorithm

134 · LRU Cache - LintCode

# Description

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.

Finally, you need to return the data from each get.

Example

Example1

Input:
LRUCache(2)
set(2, 1)
set(1, 1)
get(2)
set(4, 1)
get(1)
get(2)
Output: [1,-1,1]
Explanation：
cache cap is 2，set(2,1)，set(1, 1)，get(2) and return 1，set(4,1) and delete (1,1)，because （1,1）is the least use，get(1) and return -1，get(2) and return 1.

Example 2:

Input：
LRUCache(1)
set(2, 1)
get(2)
set(3, 2)
get(2)
get(3)
Output：[1,-1,2]
Explanation：
cache cap is 1，set(2,1)，get(2) and return 1，set(3,2) and delete (2,1)，get(2) and return -1，get(3) and return 2.

# Solution

public class LRUCache {
    /*
    * @param capacity: An integer
    */
    int cap;
    LinkedHashMap<Integer, Integer> cache;
    public LRUCache(int capacity) {
      this.cap = capacity;
      cache = new LinkedHashMap<>();
    }
    /*
     * @param key: An integer
     * @return: An integer
     */
    public int get(int key) {
        if (!cache.containsKey(key)){
            return -1;
        }
        // 將 key 變成最近使用
        makeRecently(key);
        return cache.get(key);
    }
    /*
     * @param key: An integer
     * @param value: An integer
     * @return: nothing
     */
    public void set(int key, int value) {
        if(cache.containsKey(key)){
            cache.put(key, value);
            makeRecently(key);
        }
        if (cache.size() >= this.cap){
            // 鏈表頭部就是最久未使用的 key
            int oldestKey = cache.keySet().iterator().next();
            cache.remove(oldestKey);
        }
        // 將新的 key 放到鏈表尾部
        cache.put(key, value);
    }
    private void makeRecently(int key) {
       int val = cache.get(key);
       // 刪除 key, 重新插入隊尾
       cache.remove(key);
       cache.put(key, val);
    }
}