• 146.LRU缓存

    题目：

    请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。

    实现 LRUCache 类：

    • LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
    • int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
    • void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

    函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

    示例：

    输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

    LCR 031. LRU 缓存 - 力扣（LeetCode）

    题解：

    思路：

    用一个哈希表和一个双端队列，队列里面存储key，哈希存value。get时把对应的key删除，放在队首。put时有旧的则删掉，size够了把队列的最后一个删掉。然后加入，并且覆盖哈希表里面的值。

    代码：

    1. class LRUCache {
    2.  
    3.     private int capacity;
    4.     private Map cache;
    5.     private Deque queue;
    6.     
    7.     public LRUCache(int capacity) {
    8.         this.capacity=capacity;
    9.         this.cache=new HashMap<>();
    10.         this.queue=new LinkedList<>();
    11.     }
    12.     
    13.     public int get(int key) {
    14.         if(cache.containsKey(key)){
    15.             queue.remove(key);
    16.             queue.offerFirst(key);
    17.             return cache.get(key);
    18.         }
    19.         return -1;
    20.     }
    21.     
    22.     public void put(int y, int value) {
    23.         if(cache.containsKey(y)){
    24.             queue.remove(y);
    25.         }
    26.         if(queue.size()==capacity){
    27.             Integer oldKey=queue.pollLast();
    28.             cache.remove(oldKey);
    29.         }
    30.         cache.put(y,value);
    31.         queue.offerFirst(y);
    32.     }
    33. }

    1. class Node {
    2.     int data;
    3.     Node next;
    4.     Node prev;
    5.     
    6.     Node(int data) {
    7.         this.data = data;
    8.     }
    9. }
    10.  
    11. class MyDeque {
    12.     private Node front;
    13.     private Node rear;
    14.     private int size;
    15.     
    16.     public MyDeque() {
    17.         front = null;
    18.         rear = null;
    19.         size = 0;
    20.     }
    21.     
    22.     // 向队列前端添加元素
    23.     public void offerFirst(int data) {
    24.         Node newNode = new Node(data);
    25.         if (isEmpty()) {
    26.             front = newNode;
    27.             rear = newNode;
    28.         } else {
    29.             newNode.next = front;
    30.             front.prev = newNode;
    31.             front = newNode;
    32.         }
    33.         size++;
    34.     }
    35.     
    36.     // 移除指定元素
    37.     public void remove(int key) {
    38.         Node current = front;
    39.         while (current != null) {
    40.             if (current.data == key) {
    41.                 if (current == front) {
    42.                     pollFirst();
    43.                 } else if (current == rear) {
    44.                     pollLast();
    45.                 } else {
    46.                     current.prev.next = current.next;
    47.                     current.next.prev = current.prev;
    48.                     size--;
    49.                 }
    50.                 return;
    51.             }
    52.             current = current.next;
    53.         }
    54.         return;
    55.     }
    56.     
    57.  // 从队列尾部移除元素
    58.     public int pollLast() {
    59.         if (isEmpty()) {
    60.             return -1;
    61.         }
    62.         int removedData = rear.data;
    63.         if (size == 1) {
    64.             front = null;
    65.             rear = null;
    66.         } else {
    67.             rear = rear.prev;
    68.             rear.next = null;
    69.         }
    70.         size--;
    71.         return removedData;
    72.     }
    73.  // 从队列前端移除元素
    74.     public int pollFirst() {
    75.         if (isEmpty()) {
    76.             return -1;
    77.         }
    78.         int removedData = front.data;
    79.         if (size == 1) {
    80.             front = null;
    81.             rear = null;
    82.         } else {
    83.             front = front.next;
    84.             front.prev = null;
    85.         }
    86.         size--;
    87.         return removedData;
    88.     }
    89.     // 判断队列是否为空
    90.     public boolean isEmpty() {
    91.         return size == 0;
    92.     }
    93.     
    94.     // 获取队列大小
    95.     public int size() {
    96.         return size;
    97.     }
    98.     
    99. }

    完整的双端队列：

    1. class Node {
    2.     int data;
    3.     Node next;
    4.     Node prev;
    5.     
    6.     Node(int data) {
    7.         this.data = data;
    8.     }
    9. }
    10.  
    11. public class MyDeque {
    12.     private Node front;
    13.     private Node rear;
    14.     private int size;
    15.     
    16.     public MyDeque() {
    17.         front = null;
    18.         rear = null;
    19.         size = 0;
    20.     }
    21.     
    22.     // 向队列前端添加元素
    23.     public void addFirst(int data) {
    24.         Node newNode = new Node(data);
    25.         if (isEmpty()) {
    26.             front = newNode;
    27.             rear = newNode;
    28.         } else {
    29.             newNode.next = front;
    30.             front.prev = newNode;
    31.             front = newNode;
    32.         }
    33.         size++;
    34.     }
    35.     
    36.     // 向队列尾部添加元素
    37.     public void addLast(int data) {
    38.         Node newNode = new Node(data);
    39.         if (isEmpty()) {
    40.             front = newNode;
    41.             rear = newNode;
    42.         } else {
    43.             rear.next = newNode;
    44.             newNode.prev = rear;
    45.             rear = newNode;
    46.         }
    47.         size++;
    48.     }
    49.     
    50.     // 从队列前端移除元素
    51.     public int removeFirst() {
    52.         if (isEmpty()) {
    53.             throw new IllegalStateException("队列为空");
    54.         }
    55.         int removedData = front.data;
    56.         if (size == 1) {
    57.             front = null;
    58.             rear = null;
    59.         } else {
    60.             front = front.next;
    61.             front.prev = null;
    62.         }
    63.         size--;
    64.         return removedData;
    65.     }
    66.     
    67.     // 从队列尾部移除元素
    68.     public int removeLast() {
    69.         if (isEmpty()) {
    70.             throw new IllegalStateException("队列为空");
    71.         }
    72.         int removedData = rear.data;
    73.         if (size == 1) {
    74.             front = null;
    75.             rear = null;
    76.         } else {
    77.             rear = rear.prev;
    78.             rear.next = null;
    79.         }
    80.         size--;
    81.         return removedData;
    82.     }
    83.     
    84.     // 移除指定元素
    85.     public void remove(int key) {
    86.         Node current = front;
    87.         while (current != null) {
    88.             if (current.data == key) {
    89.                 if (current == front) {
    90.                     removeFirst();
    91.                 } else if (current == rear) {
    92.                     removeLast();
    93.                 } else {
    94.                     current.prev.next = current.next;
    95.                     current.next.prev = current.prev;
    96.                     size--;
    97.                 }
    98.                 return;
    99.             }
    100.             current = current.next;
    101.         }
    102.         throw new IllegalArgumentException("队列中没有该元素");
    103.     }
    104.     
    105.     // 获取队列前端元素
    106.     public int getFirst() {
    107.         if (isEmpty()) {
    108.             throw new IllegalStateException("队列为空");
    109.         }
    110.         return front.data;
    111.     }
    112.     
    113.     // 获取队列尾部元素
    114.     public int getLast() {
    115.         if (isEmpty()) {
    116.             throw new IllegalStateException("队列为空");
    117.         }
    118.         return rear.data;
    119.     }
    120.     
    121.     // 判断队列是否为空
    122.     public boolean isEmpty() {
    123.         return size == 0;
    124.     }
    125.     
    126.     // 获取队列大小
    127.     public int size() {
    128.         return size;
    129.     }
    130.     
    131. }

  • 相关阅读:
    pat乙级1120(买地攻略) C++
    华为云云耀云服务器L实例评测｜基于L实例安装Prometheus+Grafana插件实现数据可视化监控
    15 -python之文件操作
    Latex伪代码中函数的写法
    RabbitMQ的常见工作模式
    [附源码]计算机毕业设计springboot创意摄影交流平台
    node.js学习之路由、中间件
    webpack 优化方式
    Vue中使用高德地图
    TCP协议详解
  • 原文地址：https://blog.csdn.net/Mar_mxs/article/details/137967110