LeetCode146-LRU缓存机制

发表于 | 分类于 | | 阅读量
字数统计: 559 字 | 阅读时长 ≈ 2 分钟

146.LRU缓存机制

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(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.

The cache is initialized with a positive capacity.

Follow up:
Could you do both operations in O(1) time complexity?

Example:

LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // returns 1
cache.put(3, 3); // evicts key 2
cache.get(2); // returns -1 (not found)
cache.put(4, 4); // evicts key 1
cache.get(1); // returns -1 (not found)
cache.get(3); // returns 3
cache.get(4); // returns 4

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lru-cache

翻译

它应该支持以下操作： 获取数据 get 和 写入数据 put 。

  1. 获取数据 get(key) - 如果关键字 (key) 存在于缓存中，则获取关键字的值（总是正数），否则返回 -1。
  2. 写入数据 put(key, value) - 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字/值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

解答

自己写的比较low的方法，主要运用到了java中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
31
32
33
package xyz.molzhao.cache;

import java.util.LinkedHashMap;

public class LRUCache {
    private LinkedHashMap<Integer, Integer> cacheMap = new LinkedHashMap<>();
    private int size;

    public LRUCache(int capacity) {
        this.size = capacity;
    }

    public int get(int key) {
        if (cacheMap.containsKey(key)) {
            Integer result = cacheMap.get(key);
            cacheMap.remove(key);
            cacheMap.put(key, result);
            return result;
        } else {
            return -1;
        }
    }

    public void put(int key, int value) {
        if (cacheMap.containsKey(key)) {
            cacheMap.remove(key);
        } else if (cacheMap.size() == size) {
            Integer firstKey = cacheMap.keySet().stream().findFirst().get();
            cacheMap.remove(firstKey);
        }
        cacheMap.put(key, value);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import org.junit.Test;
import xyz.molzhao.cache.LRUCache;

public class LRUCacheTest {
    @Test
    public void testLRUCache() {
        LRUCache cache = new LRUCache(2);
        cache.put(1, 1);
        cache.put(2, 2);
        System.out.println(cache.get(1));
        cache.put(3, 3);
        System.out.println(cache.get(2));
        cache.put(4, 4);
        System.out.println(cache.get(1));
        System.out.println(cache.get(3));
        System.out.println(cache.get(4));
    }
}

结果

提交结果 运行时间 内存消耗 语言
通过 26 ms 48 MB JAVA

如果有小伙伴，想要一起交流学习的，欢迎添加博主微信。

weChat