首页 > 编程语言 >【hot100-java】LRU 缓存

【hot100-java】LRU 缓存

时间:2024-10-11 13:49:32浏览次数:11  
标签:Node node java int next hot100 key LRU prev

链表篇

灵神题解

 

 

class LRUCache {
    private static class Node{
        int key,value;
        Node prev,next;

        Node (int k,int v){
            key=k;
            value=v;
        }
    }
    private final int capacity;
    //哨兵节点
    private final Node dummy=new Node(0,0);
    private final Map<Integer,Node> keyToNode =new HashMap<>();

    public LRUCache(int capacity) {
        this.capacity=capacity;
        dummy.prev=dummy;
        dummy.next=dummy;
    }
    
    public int get(int key) {
           Node node=getNode(key);
           return node!=null?node.value:-1;
    }
    
    public void put(int key, int value) {
          Node node=getNode(key);
          //有书则更新
          if(node!=null){
            node.value=value;
            return;
          }
          node=new Node(key,value);
          keyToNode.put(key,node);
          //放在最上面
          pushFront(node);
          //书太多了
          if(keyToNode.size()>capacity){
              Node backNode=dummy.prev;
              keyToNode.remove(backNode.key);
              //去掉最后一本书
              remove(backNode);
          }
    }

    //取节点
    private Node getNode(int key){
        //没有这本书
        if(!keyToNode.containsKey(key)){
            return null;
        }
        //有这本书
        Node node=keyToNode.get(key);
        //抽出来
        remove(node);
        //放在最上面
        pushFront(node);
        return node;
    }

    //删除一个节点(抽出一本书)
    private void remove(Node x){
        x.prev.next=x.next;
        x.next.prev=x.prev;
    }

    //链表头添加节点
    private void pushFront(Node x){
        x.prev=dummy;
        x.next=dummy.next;
        x.prev.next=x;
        x.next.prev=x;
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

 

背题

 

标签:Node,node,java,int,next,hot100,key,LRU,prev
From: https://blog.csdn.net/m0_73629042/article/details/142851855

相关文章

  • 【hot100-java】二叉树的右视图
    二叉树篇tql /***Definitionforabinarytreenode.*publicclassTreeNode{*intval;*TreeNodeleft;*TreeNoderight;*TreeNode(){}*TreeNode(intval){this.val=val;}*TreeNode(intval,TreeNodeleft,Tre......
  • 【hot100-java】合并 K 个升序链表
    链表篇/***Definitionforsingly-linkedlist.*publicclassListNode{*intval;*ListNodenext;*ListNode(){}*ListNode(intval){this.val=val;}*ListNode(intval,ListNodenext){this.val=val;this.next=next;......
  • [Java/Spring] 深入理解 : Spring ApplicationContext
    [Java/Spring]深入理解:SpringApplicationContext1概述:ApplicationContext简介2源码分析ApplicationContextpackageorg.springframework.context;publicinterfaceApplicationContextextendsEnvironmentCapable,ListableBeanFactory,HierarchicalBeanFactor......
  • 一款Java CMS 网站管理系统,基于RuoYi-fast二次开发,网站后台采用SpringBoot + MyBati
    一款JavaCMS网站管理系统基于RuoYi-fast二次开发,网站后台采用SpringBoot+MyBatis文章目录前言一、开源地址二、环境要求三、功能亮点3.1扩展功能3.2内置功能四、安装方法4.1、拉取源码4.2、修改数据库链接配置4.3、创建数据库并导入数据4.4、配置资源上传......
  • 【Java】异常处理指南
     ......
  • 【Java 】包装类详解:从基本概念到实战技巧
     ......
  • Java中的锁
    锁:实现操作的同步或者可以说对操作公共的资源进行一个限制锁的分类:1.排他锁(重点)和共享锁排他锁:获得锁资源之后那么不能对这个资源进行任何的读写操作,这些操作就会进行阻塞共享锁:获得锁资源之后,只能对这个资源进行相关的读操作不能对其进行写操作案例:就是在Mysql......
  • Android Studio添加依赖 新版 和 旧版 的添加方式(Gradle添加依赖)(Java)
    旧版的(在线添加)1找文件在项目的build.gradle文件中添加依赖(在下面的节点中添加库格式’组:名字:版本号‘)dependencies{implementation'com.example:library:1.0.0'}implementation‘组:名字:版本号’添加完成之后上方会出现如下图提示(点击现在同步)(Sy......
  • Java项目: 基于SpringBoot+mybatis+maven+vue健身房管理系统(含源码+数据库+毕业论文)
    一、项目简介本项目是一套基于SpringBoot+mybatis+maven+vue健身房管理系统包含:项目源码、数据库脚本等,该项目附带全部源码可作为毕设使用。项目都经过严格调试,eclipse或者idea确保可以运行!该系统功能完善、界面美观、操作简单、功能齐全、管理便捷,具有很高的实际应用......
  • AI 时代就业指南:Java 程序员如何转行做大模型?
    前言在人工智能(AI)迅速发展的背景下,从传统的编程领域如Java程序员转向大模型开发是一个既充满挑战也充满机遇的过程。对于Java程序员来说,这也是一个实现职业转型、提升薪资待遇的绝佳机遇。一、明确大模型概念简单来说,大模型就是具有大量参数和强大计算能力的人工智能模......