📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 1268| 回复: 7
跳转到指定楼层
上一主题 下一主题
收起左侧

[Leetcode] 请问这个LRU代码为什么报空指针错误?

🔗
ygmm | 只看该作者 |倒序浏览
全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
本帖最后由 ygmm 于 2019-9-22 09:01 编辑

请喜欢肉眼debug的朋友帮忙看看。我调试了也没找出来问题。。。

  1. class LRUCache {
  2.   private Node head;
  3.     private Node tail;
  4.     private int capacity;
  5.     private HashMap<Integer, Node> map;
  6.     public class Node{
  7.         int key;
  8.         int val;
  9.         Node prev;
  10.         Node next;
  11.         public Node(int key, int val){
  12.             this.key = key;
  13.             this.val = val;
  14.         }
  15.     }
  16.     public LRUCache(int capacity) {
  17.          this.capacity = capacity;
  18.          map = new HashMap<>();
  19.          head = null;
  20.          tail = null;
  21.     }
  22.    
  23.     public int get(int key) {
  24.         Node node = map.get(key);
  25.         if(node == null){
  26.             return -1;
  27.         }
  28.         refreshNode(node);
  29.         return node.val;
  30.     }
  31.    
  32.     public void put(int key, int value) {
  33.         Node node = map.get(key);
  34.         if(node == null){
  35.             //new
  36.             if(map.size() == capacity){
  37.                 //full
  38.                 int tailkey = remove(tail);
  39.                 map.remove(tailkey);
  40.             }
  41.             node = new Node(key, value);
  42.             add(node);
  43.             map.put(key, node);
  44.         }else{
  45.             //exist
  46.             node.val = value;
  47.             refreshNode(node);
  48.         }
  49.     }
  50.     public void refreshNode(Node node){
  51.         if(node == head){
  52.             return;
  53.         }
  54.         remove(node);
  55.         add(node);
  56.             
  57.             
  58.     }
  59.     private int remove(Node node){
  60.            if(node == tail){
  61.                 tail = tail.prev;
  62.                 tail.next = null;
  63.             }else{
  64.                 node.prev.next = node.next;
  65.                 node.next.prev = node.prev;
  66.             }
  67.         return node.key;
  68.     }
  69.     private void add(Node node){
  70.         if(head == null){
  71.             head = node;
  72.             tail = node;
  73.             return;
  74.         }
  75.             node.next = head;
  76.             head.prev = node;
  77.             head = node;
  78.             head.prev = null;        
  79.     }
  80. }

  81. /**
  82. * Your LRUCache object will be instantiated and called as such:
  83. * LRUCache obj = new LRUCache(capacity);
  84. * int param_1 = obj.get(key);
  85. * obj.put(key,value);
  86. */
复制代码


上一篇:请问R怎么安装lightgbm包呀
下一篇:根据威尔逊区间排序的最受喜欢的题目
推荐
Moai17 2019-9-22 09:21:18 | 只看该作者
全局:
ygmm 发表于 2019-9-21 18:18
初始的时候,head = null, tail = null.
在加入第一个元素后,head 和 tail 都指向这个新的,没看出问题 ...

我没看你后面的代码。。我以为你忘了。。这里应该没问题的。
这个代码的问题是remove出错了,你没有考虑万一只有一个点了,你要把这个remove掉的情况。在remove函数的最前面加上:
        if (node == tail && node == head) {
            tail = null;
            head = null;
            return node.key;
        }
就可以submit了。另外我觉得你这样写有点怪怪的,还是有一个dummy head和dummy tail比较直观一点点。
回复

使用道具 举报

🔗
Moai17 2019-9-22 09:03:24 | 只看该作者
全局:
初始化的时候,把head,tail连一下吧
回复

使用道具 举报

🔗
 楼主| ygmm 2019-9-22 09:05:44 | 只看该作者
全局:
remove 那为什么错呢?

["LRUCache","put","get","put","get","get"]
[[1],[2,1],[2],[3,2],[2],[3]]


java.lang.NullPointerException
  at line 109, LRUCache.remove
  at line 85, LRUCache.put
  at line 63, __Driver__.__helperSelectMethod__
  at line 85, __Driver__.__helper__
  at line 106, __Driver__.main
回复

使用道具 举报

🔗
 楼主| ygmm 2019-9-22 09:18:03 | 只看该作者
全局:
fix1995 发表于 2019-9-22 09:03
初始化的时候,把head,tail连一下吧

初始的时候,head = null, tail = null.
在加入第一个元素后,head 和 tail 都指向这个新的,没看出问题呀。。。我还是太次了
回复

使用道具 举报

🔗
 楼主| ygmm 2019-9-22 09:24:18 | 只看该作者
全局:
本帖最后由 ygmm 于 2019-9-22 09:40 编辑
fix1995 发表于 2019-9-22 09:03
初始化的时候,把head,tail连一下吧

谢谢! 火眼金睛!
回复

使用道具 举报

🔗
 楼主| ygmm 2019-9-22 09:30:04 | 只看该作者
全局:
fix1995 发表于 2019-9-22 09:21
我没看你后面的代码。。我以为你忘了。。这里应该没问题的。
这个代码的问题是remove出错了,你没有考虑 ...

是的,有一个dummy head和dummy tail 能处理这种删最后一个点的情况。 哎,我就是想练练,结果搞了很久也没做出来。  你太厉害了!谢谢
回复

使用道具 举报

🔗
 楼主| ygmm 2019-9-22 10:37:27 | 只看该作者
本楼:
全局:
本帖最后由 ygmm 于 2019-9-22 10:44 编辑

搞定搞定
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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