首页 > 其他分享 >146.LRUCache

146.LRUCache

时间:2022-11-20 17:37:04浏览次数:71  
标签:146 Node pre map int value key LRUCache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Follow up:
Could you do both operations in O(1) time complexity?

 

class LRUCache {

   int capacity;    Map map = new HashMap();//key是Integer,value是Node    Node head = null;    Node end = null;        public LRUCache(int capacity) {       this.capacity = capacity;    }        public int get(int key) {       if(map.containsKey(key)) {           Node temp = map.get(key);           remove(temp);           setHead(temp);           return temp.value;       }        return -1;    }        public void put(int key, int value) {       if(map.containsKey(key)) {           Node old = map.get(key);           old.value = value;            remove(old);           setHead(old);        } else {           Node created = new Node(key,value);           if(map.size()>=capacity) {              map.remove(end.key);              remove(end);              setHead(created);           } else               setHead(created);          map.put(key,created);       }    }        public void remove(Node n) {       if(n.pre!=null)            n.pre.next = n.next;       else           head = n.next;              if(n.next!=null)            n.next.pre = n.pre;       else            end = n.pre;           }        public void setHead(Node n) {                         n.next = head;         n.pre = null;              if(head!=null)           head.pre=n;        head = n;                if(end == null)           end = head;          } }   class Node {    int key;    int value;    Node pre;    Node next;        Node(int key, int value){        this.key = key;         this.value = value;    } }

标签:146,Node,pre,map,int,value,key,LRUCache
From: https://www.cnblogs.com/MarkLeeBYR/p/16908991.html

相关文章

  • ORA-00932: 数据类型不一致: 应为 -, 但却获得 CLOB/ORA-01460: 转换请求无法实施或不
    最近公司软件中某功能在使用时报错了:ORA-00932:数据类型不一致:应为-,但却获得CLOB看了一下SQL如下:SELECTDISTINCTCLOB字段FROM(SELECTCLOB字段FROM......
  • SP11469 SUBSET - Balanced Cow Subsets Sol
    考虑枚举\(3^n\)种情况,用三进制数表示。对于每一位,\(0\)表示不放,\(1\)表示放入第一个集合,\(2\)表示放入第二个集合。这样显然会TLE。考虑meetinthemiddle。考......
  • MYSQL ERROR 1146 Table doesnt exist 解析
    原创转载请注明出处源码版本5.7.14在MYSQL使用innodb的时候我们有时候会看到如下报错:ERROR1146(42S02):Table'test.test1bak'doesn'texist首先总结下原......
  • 146.LRU 缓存
    请你设计并实现一个满足LRU(最近最少使用)约束的数据结构。实现 LRUCache 类:LRUCache(intcapacity) 以 正整数 作为容量 capacity 初始化LRU缓存intget(int......
  • 一本通 1469:似乎在梦中见过的样子
    对于字符串S,求有多少合法子串(该子串形式为ABA,len(B)>=1,len(A)>=K) lenS=15e3 谁能想到这题是暴力n^2直接n^2枚举l,r,预处理出kmp的next[],逐个判断 ......
  • 一本通 1466 Power Strings
    找字符串的最短循环节 #include<bits/stdc++.h>usingnamespacestd;constintN=1e6+1;chara[N];intn,p[N];voidinit(){inti,j=0;......
  • CF1463F Max Correct Set(取小样法+状压 DP)
    CF1463FMaxCorrectSet要求选出集合\(U=\{1,2,3,\dots,n\}\)的一个子集\(S\),满足:如果\(a\inS\)并且\(b\inS\),那么\(|a-b|\not={x}\)并且\(|a-b|\not=......
  • leetcode-1460-easy
    MakeTwoArraysEqualbyReversingSubarraysYouaregiventwointegerarraysofequallengthtargetandarr.Inonestep,youcanselectanynon-emptysubarra......
  • 洛谷P1462spfa + 二分答案
    第一次接触二分答案的题目最开始是没有思路的看了一个题解,然后强行理解之后开始自己打了一遍,然而结果是只得了30分过了3个点其他全wa,之后是漫长的debug,这里想感慨一句自己d......
  • 洛谷 P1464 Function(dfs+记忆化搜索)
    https://www.luogu.com.cn/problem/P1464单个返回条件的时候,直接return多个返回条件的时候,采用记忆化搜索思想,边存储边继续往下搜索中间穿插记忆化判断,如果之前有过此......