leetcode算法【146】LRU缓存机制

柔情只为你懂 2023-02-20 07:55 139阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：数组解法
             *   *  复杂度计算
             *  方案：LinkedHashMap
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

*  时隔多日，终于是手痒来写一道，正好在复习操作系统，所以就刷了这个与之相关的，Leetcode真的啥都有~

#### 题目 ####

运用你所掌握的数据结构，设计和实现一个  LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
    
    获取数据 get(key) - 如果关键字 (key) 存在于缓存中，则获取关键字的值（总是正数），否则返回 -1。
    写入数据 put(key, value) - 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字/值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
    
     
    
    进阶:
    
    	你是否可以在 O(1) 时间复杂度内完成这两种操作？
    
     
    
    示例:
    
    		LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
    
    		cache.put(1, 1);
    		cache.put(2, 2);
    		cache.get(1);       // 返回 1
    		cache.put(3, 3);    // 该操作会使得关键字 2 作废
    		cache.get(2);       // 返回 -1 (未找到)
    		cache.put(4, 4);    // 该操作会使得关键字 1 作废
    		cache.get(1);       // 返回 -1 (未找到)
    		cache.get(3);       // 返回 3
    		cache.get(4);       // 返回 4

#### 方案：数组解法 ####

class LRUCache { 
    
            private int[][] cache;
            private int row;
    
            public LRUCache(int capacity) { 
                cache = new int[capacity][3];
                for (int i = 0; i < capacity; i++) { 
                    cache[i][0] = -1;
                }
                row = capacity;
            }
    
            public int get(int key) { 
                int res = -1;
                for (int i = 0; i < this.row; i++) { 
                    if (cache[i][0] == key) { 
                        cache[i][1] = 0;
                        res = cache[i][2];
                    } else if (cache[i][0] == -1) { 
                        break;
                    } else { 
                        cache[i][1]++;
                    }
                }
                return res;
            }
    
            public void put(int key, int value) { 
                int max = -1;
                int index = -1;
                boolean find = false;
                for (int i = 0; i < this.row; i++) { 
                    if (cache[i][0] == key) { 
                        cache[i][1] = 0;
                        cache[i][2] = value;
                        index = -1;
                        find = true;
                    } else if (cache[i][0] == -1&&!find) { 
                        cache[i][0] = key;
                        cache[i][1] = 0;
                        cache[i][2] = value;
                        return;
                    } else { 
                        cache[i][1]++;
                        if (max < cache[i][1]&&!find) { 
                            max = cache[i][1];
                            index = i;
                        }
                    }
                }
                if (index != -1) { 
                    cache[index][0] = key;
                    cache[index][1] = 0;
                    cache[index][2] = value;
                }
            }
        }

##### 复杂度计算 #####

*  时间复杂度：O(n)
 *  空间复杂度：O(n)

#### 方案：LinkedHashMap ####

*  突然发现LinkedHashMap的可以实现LRU，看源码注释：重写下removeEldestEntry，这就直接实现了~，算作弊吧这，哈哈，正常来讲应该是自己写个HashMap之类的搞一搞  
    ![在这里插入图片描述][20200625113252983.png]

class LRUCache extends LinkedHashMap<Integer, Integer> { 
    
            private int capacity;
    
            public LRUCache(int capacity) { 
                super(capacity,0.75F,true);
                this.capacity = capacity;
            }
            public int get(int key) { 
                return super.getOrDefault(key,-1);
            }
    
            public void put(int key, int value) { 
                super.put(key,value);
            }
    
            @Override
            protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) { 
                return size() > capacity;
            }
    
        }

##### 复杂度计算 #####

*  时间复杂度：O(1)
 *  空间复杂度：O(n)

[Git]: https://github.com/ch98road/leetcode
[20200625113252983.png]: https://img-blog.csdnimg.cn/20200625113252983.png