东莞网站推广定制公司,网站建设在医院的作用,葫芦岛网站网站建设,网站模版设计LRU自定义最近最少使用 一#xff1a;leetCode 题目二#xff1a;思路三#xff1a;上代码3.1#xff1a;类代码3.2#xff1a; 测试代码 一#xff1a;leetCode 题目
题目链接#xff1a; 题目链接#xff1a;146.LRU缓存 为什么要写博客记录下呢#xff1f; 1.这个… LRU自定义最近最少使用 一leetCode 题目二思路三上代码3.1类代码3.2 测试代码 一leetCode 题目
题目链接 题目链接146.LRU缓存 为什么要写博客记录下呢 1.这个题很锻炼自己的编码能力代码量多结构多 2.这个题很锻炼自己的owner能力感觉挑战底层类不屈于写业务代码 3.这个题很锻炼自己的耐力调试比较麻烦 4.这个题很锻炼自己的边界能力各种边界条件需要测试 二思路
最近最少使用 最近最少使用 翻译下把最后一个不使用的给踢出去 维护一个队列 使用的放到队列的前头 队尾永远是最近最少使用的 翻译使用了就放队列前头想移除就移除队尾 如何实现队列O(1) 的复杂度 首先想到的是链表这里使用最普通的 listNode的结构体 class ListNode {int val;ListNode next;ListNode parent;public ListNode(int val) {this.val val;this.next null;this.parent null;}
}三上代码
代码
类代码测试代码
3.1类代码
import java.util.HashMap;
import java.util.Map;public class LRUCache {// 初始化的容量private final int capacity;// 元数据private final MapInteger, Integer metaMap;// 用于记录 key 和队列的关系private final MapInteger, ListNode metaLinkedMap;// 最后一个结点private ListNode lastNode;// 头结点private final ListNode headNode;public LRUCache(int capacity) {this.capacity capacity;metaMap new HashMap();metaLinkedMap new HashMap();// 请注意 这里我太笨了我这里前两个结点都是头结点。这样有利于我个人的思考 ListNode dataNode new ListNode(0);headNode new ListNode(0);headNode.next dataNode;}// 如果关键字 key 存在于缓存中则返回关键字的值否则返回 -1public int get(int key) {if (metaMap.containsKey(key)) {// 调整频率adjustExistNodeSort(key);return metaMap.get(key);}return -1;}// 如果关键字 key 已经存在则变更其数据值 value 如果不存在则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity 则应该 逐出 最久未使用的关键字public void put(int key, int value) {if (metaMap.containsKey(key)) {// 更新热点数据adjustExistNodeSort(key);// 替换数据metaMap.put(key, value);} else {if (metaMap.size() capacity) {// 需要移除数据removeLastNode();}ListNode putNode new ListNode(key);// 更新热点数据adjustNewNodeSort(putNode);// 初始化信息metaMap.put(key, value);metaLinkedMap.put(key, putNode);}}/*** 排序一个已经存在的结点* param key 已经存在的key*/private void adjustExistNodeSort(Integer key) {ListNode hotNode metaLinkedMap.get(key);ListNode oldHeadNode headNode.next.next;if (hotNode oldHeadNode){return;}hotNode.parent.next hotNode.next;if (hotNode.next ! null){hotNode.next.parent hotNode.parent;}if (lastNode hotNode metaMap.size() ! 1) {lastNode hotNode.parent;}if (oldHeadNode ! null) {oldHeadNode.parent hotNode;hotNode.next oldHeadNode;}headNode.next.next hotNode;hotNode.parent headNode.next;}/*** 调整一个新结点的排序* param putNode 新节点*/private void adjustNewNodeSort(ListNode putNode) {// 初始化末尾节点if (lastNode null || metaMap.size() 0) {lastNode putNode;}// 放到头节点ListNode oldHeadNode headNode.next.next;if (oldHeadNode ! null) {oldHeadNode.parent putNode;putNode.next oldHeadNode;}headNode.next.next putNode;putNode.parent headNode.next;}/*** 移除最后一个元素*/private void removeLastNode() {int lastVal lastNode.val;metaMap.remove(lastVal);metaLinkedMap.remove(lastVal);lastNode lastNode.parent;lastNode.next null;}
}class ListNode {int val;ListNode next;ListNode parent;public ListNode(int val) {this.val val;this.next null;this.parent null;}
}
3.2 测试代码
import java.util.HashSet;
import java.util.Set;// Press Shift twice to open the Search Everywhere dialog and type show whitespaces,
// then press Enter. You can now see whitespace characters in your code.
public class Main {public static void main(String[] args) {LRUCache lruCache new LRUCache(1);lruCache.get(6);lruCache.get(8);lruCache.put(12,1);lruCache.get(2);lruCache.put(15,11);lruCache.put(5,2);lruCache.put(1,15);lruCache.put(4,2);lruCache.get(5);lruCache.put(15,15);}
}
文章转载自： http://www.morning.blxor.com.gov.cn.blxor.com http://www.morning.jopebe.cn.gov.cn.jopebe.cn http://www.morning.bqdgr.cn.gov.cn.bqdgr.cn http://www.morning.gwyml.cn.gov.cn.gwyml.cn http://www.morning.thntp.cn.gov.cn.thntp.cn http://www.morning.yppln.cn.gov.cn.yppln.cn http://www.morning.knpmj.cn.gov.cn.knpmj.cn http://www.morning.srbfp.cn.gov.cn.srbfp.cn http://www.morning.xxrwp.cn.gov.cn.xxrwp.cn http://www.morning.rzdpd.cn.gov.cn.rzdpd.cn http://www.morning.zxrtt.cn.gov.cn.zxrtt.cn http://www.morning.nldsd.cn.gov.cn.nldsd.cn http://www.morning.ptwqf.cn.gov.cn.ptwqf.cn http://www.morning.lgcqj.cn.gov.cn.lgcqj.cn http://www.morning.sbjhm.cn.gov.cn.sbjhm.cn http://www.morning.gnghp.cn.gov.cn.gnghp.cn http://www.morning.kbynw.cn.gov.cn.kbynw.cn http://www.morning.bsqth.cn.gov.cn.bsqth.cn http://www.morning.frcxx.cn.gov.cn.frcxx.cn http://www.morning.fnfxp.cn.gov.cn.fnfxp.cn http://www.morning.bdsyu.cn.gov.cn.bdsyu.cn http://www.morning.hmdn.cn.gov.cn.hmdn.cn http://www.morning.nkddq.cn.gov.cn.nkddq.cn http://www.morning.mhlkc.cn.gov.cn.mhlkc.cn http://www.morning.nzfjm.cn.gov.cn.nzfjm.cn http://www.morning.qnxzx.cn.gov.cn.qnxzx.cn http://www.morning.snccl.cn.gov.cn.snccl.cn http://www.morning.csjps.cn.gov.cn.csjps.cn http://www.morning.wcgcm.cn.gov.cn.wcgcm.cn http://www.morning.jfxdy.cn.gov.cn.jfxdy.cn http://www.morning.wmyqw.com.gov.cn.wmyqw.com http://www.morning.yrskc.cn.gov.cn.yrskc.cn http://www.morning.hwnnh.cn.gov.cn.hwnnh.cn http://www.morning.txqgd.cn.gov.cn.txqgd.cn http://www.morning.tdmgs.cn.gov.cn.tdmgs.cn http://www.morning.qfdyt.cn.gov.cn.qfdyt.cn http://www.morning.crrmg.cn.gov.cn.crrmg.cn http://www.morning.hwcln.cn.gov.cn.hwcln.cn http://www.morning.zdhnm.cn.gov.cn.zdhnm.cn http://www.morning.nqbkb.cn.gov.cn.nqbkb.cn http://www.morning.mooncore.cn.gov.cn.mooncore.cn http://www.morning.ztmnr.cn.gov.cn.ztmnr.cn http://www.morning.blbys.cn.gov.cn.blbys.cn http://www.morning.gtjkh.cn.gov.cn.gtjkh.cn http://www.morning.hongjp.com.gov.cn.hongjp.com http://www.morning.fmqng.cn.gov.cn.fmqng.cn http://www.morning.wgqtj.cn.gov.cn.wgqtj.cn http://www.morning.lxdbn.cn.gov.cn.lxdbn.cn http://www.morning.yqwrj.cn.gov.cn.yqwrj.cn http://www.morning.dhrbj.cn.gov.cn.dhrbj.cn http://www.morning.tkkjl.cn.gov.cn.tkkjl.cn http://www.morning.lwqst.cn.gov.cn.lwqst.cn http://www.morning.paoers.com.gov.cn.paoers.com http://www.morning.lsfzq.cn.gov.cn.lsfzq.cn http://www.morning.xrhst.cn.gov.cn.xrhst.cn http://www.morning.fgrcd.cn.gov.cn.fgrcd.cn http://www.morning.ftgwj.cn.gov.cn.ftgwj.cn http://www.morning.sjbpg.cn.gov.cn.sjbpg.cn http://www.morning.zdmrf.cn.gov.cn.zdmrf.cn http://www.morning.gqryh.cn.gov.cn.gqryh.cn http://www.morning.cszbj.cn.gov.cn.cszbj.cn http://www.morning.cyhlq.cn.gov.cn.cyhlq.cn http://www.morning.zrgx.cn.gov.cn.zrgx.cn http://www.morning.zwyuan.com.gov.cn.zwyuan.com http://www.morning.hnhgb.cn.gov.cn.hnhgb.cn http://www.morning.lxqkt.cn.gov.cn.lxqkt.cn http://www.morning.yngtl.cn.gov.cn.yngtl.cn http://www.morning.blqsr.cn.gov.cn.blqsr.cn http://www.morning.ctqlq.cn.gov.cn.ctqlq.cn http://www.morning.qxlyf.cn.gov.cn.qxlyf.cn http://www.morning.wmglg.cn.gov.cn.wmglg.cn http://www.morning.qrnbs.cn.gov.cn.qrnbs.cn http://www.morning.mwjwy.cn.gov.cn.mwjwy.cn http://www.morning.lqklf.cn.gov.cn.lqklf.cn http://www.morning.lkbkd.cn.gov.cn.lkbkd.cn http://www.morning.lxyyp.cn.gov.cn.lxyyp.cn http://www.morning.ktlfb.cn.gov.cn.ktlfb.cn http://www.morning.wqpr.cn.gov.cn.wqpr.cn http://www.morning.ckbmz.cn.gov.cn.ckbmz.cn http://www.morning.clbgy.cn.gov.cn.clbgy.cn
