找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

微信名称:美国米群网

微 信 号:MeetQun

微信QQ:群: 320065698

查看: 152|回复: 2
收起左侧

[刷题记录板] 146. LRU Cache

[复制链接]

23

主题

0

精华

28

积分

新米人

Rank: 1

积分
28
发表于 11-29-2016 05:22 AM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
  1. public class LRUCache {
  2.     public class Node{
  3.         int key;
  4.         int value;
  5.         Node pre,next;
  6.         Node(int key,int value){
  7.             this.key=key;
  8.             this.value=value;
  9.         }
  10.     }
  11.    
  12.     Node head;
  13.     Node tail;
  14.     int capacity;
  15.     Map<Integer,Node> map;
  16.    
  17.     public LRUCache(int capacity) {
  18.         head= new Node(0,0);
  19.         tail= new Node(0,0);
  20.         head.next=tail;
  21.         tail.pre=head;
  22.         this.capacity=capacity;
  23.         map=new HashMap<>();
  24.     }
  25.    
  26.     public int get(int key) {
  27.          if (map.containsKey(key)){
  28.              Node curnode = map.get(key);
  29.              deleteNode(curnode);
  30.              addHead(curnode);
  31.              return curnode.value;
  32.          }
  33.         return -1;
  34.     }
  35.    
  36.     public void set(int key, int value) {
  37.         if (map.containsKey(key)){
  38.             Node curnode = map.get(key);
  39.             curnode.value=value;
  40.             deleteNode(curnode);
  41.             addHead(curnode);            
  42.         }
  43.         else{
  44.             Node newnode = new Node(key,value);
  45.             addHead(newnode);
  46.             map.put(key,newnode);
  47.             if (map.size()>capacity){
  48.                 Node tmp = deleteNode(tail.pre);
  49.                 map.remove(tmp.key);
  50.                
  51.             }
  52.             
  53.         }
  54.         
  55.         
  56.     }
  57.    
  58.    
  59.     public Node deleteNode(Node node){
  60.         node.pre.next=node.next;
  61.         node.next.pre=node.pre;
  62.         return node;
  63.     }
  64.     public void addHead(Node node){
  65.         node.next=head.next;
  66.         head.next.pre=node;
  67.         node.pre=head;
  68.         head.next=node;
  69.     }
  70.    
  71. }
复制代码


713

主题

125

精华

2250

积分

米群网大牛

Rank: 6Rank: 6

积分
2250
发表于 11-29-2016 05:22 AM | 显示全部楼层
感谢taoqi610分享~~~
回复 支持 反对

使用道具 举报

0

主题

0

精华

6

积分

新米人

Rank: 1

积分
6
发表于 12-2-2016 03:21 AM 来自美国米群网手机版 | 显示全部楼层
感谢taoqi610分享~~~
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表