首页 > 编程语言 >算法--2023.1.11

算法--2023.1.11

时间:2023-01-12 00:55:05浏览次数:42  
标签:11 node temp map -- Node 2023.1 key public

1.力扣146--LRU缓存

class LRUCache {
    class Node{
        public int key;
        public int value;
        public Node pre,next;
        public Node(){}
        public Node(int key, int value){this.key = key;this.value = value;}
    }
    //双链表+哈希表实现
    //哈希表并不记录插入键值对的顺序,通过双向连链表来保存他们的顺序。
    public HashMap<Integer,Node> map;
    public int capacity;
    public Node tail, head;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        tail = new Node();
        head = new Node();
        head.next = tail;
        tail.pre = head;
    }
    
    public int get(int key) {
        //查询逻辑:如果key不在map中直接返回-1;
        //        如果在map中,找到该节点,在原来链表中删除该节点,然后将该节点放入链表头,返回对应的value  
        Node temp = map.get(key);
        if(temp == null){
            return -1;
        } 
        //System.out.println(temp.value);
        removeToHead(temp);
        return temp.value;

    }
    
    public void put(int key, int value) {
        //写逻辑:如果key不在map中,将该节点放入map中,将该节点放入链表中。
        Node temp = map.get(key);
        if(temp == null){
            temp = new Node(key,value);
            map.put(key,temp);
            addToHead(temp);
            //如果此时哈希表个数超过我们能存放的缓存个数,删除链表最后一个节点(不常用),然后在哈希表中删除对应的节点。
            if(map.size()>capacity){
                //map.remove(tail.pre.key);
                Node node = deletTail();
                map.remove(node.key);
            }
        }else{
            temp.value = value;
            removeToHead(temp);
        }
    }
    private void addToHead(Node node){
        //添加节点操作,先把当前节点连入,在修改前后节点。
        node.pre = head;
        node.next = head.next;
        head.next.pre = node;
        head.next = node;
    }
    private void delet(Node node){
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }
    private void removeToHead(Node node){
        delet(node);
        addToHead(node);
    }
    private Node deletTail(){
        Node node = tail.pre;
        delet(node);
        return node;
    }
}

  

标签:11,node,temp,map,--,Node,2023.1,key,public
From: https://www.cnblogs.com/lyjps/p/17045283.html

相关文章

  • 回家倒数五天,ic人加油
    实习一个月了。感觉学会了不少东西,我要坚持做到总结${\color{Blue} \left|a\right|\leqslantb\Rightarrow-b\leqslanta\leqslant\left|b\right|} $ ......
  • 两台 mac 通过 scp 命令快速传输数据
    这两天由于电脑进水了,所以申请换了一台mac电脑,所以想把老电脑的数据拷贝到新电脑,折腾了半天,最后还是发现scp命令最好用。使用「scp命令方式」之前尝试的其他方法1......
  • 项目经验|今日项目记录
    一、about弹框&表单打开弹框之后,判断弹框里的el-form表单ref='createFormRef':此ref是否存在,存在调用其ref的clearValidate()每每打开弹框时:this.showDrawerCreat......
  • UDP
    UDPUDP是一种全双工通信协议。UDP协议首部中有一个16位的大长度.也就是说一个UDP能传输的报文长度是64K(包含UDP首部)。如果我们需要传输的数据超过64K,就需要在应用层......
  • TCP
    TCP传输控制协议(TCP,TransmissionControlProtocol)是为了在不可靠的互联网络上提供可靠的端到端字节流而专门设计的一个传输协议 一.TCP的客户端和服务端客户端:客户也......
  • Eternal_Battle
    我对你发不了脾气。我只是希望你回答我的问题。不要看到了不回复。我不知道该怎么骂你,你也没有骂过我。小时候一直遭受冷暴力,难道长大之后也一直这样吗?如果嫌我烦我可......
  • CobaltStrike权限提升
    BypassUAC  UAC是微软在WindowsVista以后版本引入的一种安全机制,通过UAC,应用程序和任务可始终在非管理员帐户的安全上下文中运行,除非管理员特别授予管理员级别的系......
  • springMVC文件下载
    通常来说,当我们给浏览器一个文件的路径,当那个文件能够被浏览器直接打开的话,浏览器就直接打开,如果浏览器无法直接打开那么浏览器就会提示用户可以下载这个文件现在我们要做......
  • 学习记录-外观模式
    外观模式外观模式(FacadePattern)隐藏系统的复杂性,并向客户端提供了一个客户端可以访问系统的接口。这种类型的设计模式属于结构型模式,它向现有的系统添加一个接口,来隐藏系......
  • 74. 搜索二维矩阵
    问题链接https://leetcode.cn/problems/search-a-2d-matrix/description/解题思路我们可以确定,数据是有序的。所以我们有2种办法用二分来解决。第一种,我们可以写个下标......