146. LRU 缓存 --力扣 --JAVA

简介: ​请你设计并实现一个满足  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

 题目

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

实现 LRUCache 类:

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

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

    解题思路

      1. 由题可知,需要Map来存储数据,List可以通过通过控制添加到的索引位置来将数据提前;
      2. 对Map进行操作时,通过更新List涉及的数据;
      3. 溢出时从List获取末尾节点即最近最少使用的数据进行删除更新。

      代码展示

      class LRUCache {
          Map< Integer, Integer> lru = null;
          List<Integer> sort = null;
          int cap;
          public LRUCache(int capacity) {
              lru = new HashMap<>();
              sort = new ArrayList<>(capacity);
              cap = capacity;
          }
          public int get(int key) {
              Integer val = lru.get(key);
              if(val != null){
                  sort.remove((Integer) key);
                  sort.add(0, key);
                  return val;
              } else {
                  return -1;
              }
          }
          public void put(int key, int value) {
              if(lru.containsKey(key)){
                  lru.put(key,value);
                  sort.remove((Integer) key);
                  sort.add(0, key);
              } else {
                  if (lru.size() == cap) {
                      int last = sort.get(cap - 1);
                      sort.remove(cap - 1);
                      lru.remove(last);
                  }
                  lru.put(key, value);
                  sort.add(0, key);
              }
          }
      }

      image.gif


      目录
      相关文章
      |
      10天前
      |
      缓存 监控 安全
      如何使用LRU缓存来提高程序的性能?
      如何使用LRU缓存来提高程序的性能?
      15 3
      |
      10天前
      |
      存储 缓存 算法
      使用Java实现高效的数据缓存系统
      【2月更文挑战第3天】在大规模的应用程序中,数据缓存是提高应用程序性能的一种重要方法。本文介绍了如何使用Java实现高效的数据缓存系统。我们将讨论缓存的设计原则和缓存算法的选择,同时详细说明如何使用Java内置的缓存库和其他开源工具来构建一个可靠、高效的数据缓存系统。
      |
      12天前
      |
      SQL 缓存 Java
      百度搜索:蓝易云【java mybatis一级缓存二级缓存三级缓存详解】
      综上所述,MyBatis提供了一级缓存和二级缓存,可以通过集成第三方缓存框架来实现三级缓存,以提高查询性能和减轻数据库负担。在使用缓存时,需要根据具体业务场景来选择合适的缓存级别,并合理配置缓存策略,以充分发挥缓存的优势。 买CN2云服务器,免备案服务器,高防服务器,就选蓝易云。百度搜索:蓝易云
      152 3
      |
      13天前
      |
      Java
      LeetCode题解-逆波兰表达式求值-Java
      逆波兰表达式求值-Java
      7 0
      |
      13天前
      |
      Java
      |
      13天前
      |
      Java
      |
      13天前
      |
      Java
      LeetCode题解-二叉搜索树中第K小的元素-Java
      LeetCode题解-二叉搜索树中第K小的元素-Java
      6 0
      |
      13天前
      |
      Java
      |
      13天前
      |
      Java
      LeetCode题解- 两两交换链表中的节点-Java
      两两交换链表中的节点-Java
      7 0
      |
      13天前
      |
      Java
      LeetCode题解-合并K个有序数组-Java
      合并K个有序数组-Java
      5 0

      相关产品

    1. 云迁移中心