Amazon countMiss code

1. 好想lz以前在哪儿留过什么信息，统一回复missCount这个题，根据lc上LRU cache写的算是优化。大家参考吧。

复制代码

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

码没了 ＝ ＝ 见楼下

1. static class Node {
   
2.         Node prev;
   
3.         Node next;
   
4.         int key;
   
5.         Node(int key){
   
6.                 this.key = key;
   
7.                 this.prev = null;
   
8.                 this.next = null;
   
9.         }
   
10. }
    
11. static int countMiss(int cap, int keys) {
    
12.         if(cap == 0){
    
13.                 return keys.length;
    
14.         }
    
15.         if(keys == null || keys.length == 0){
    
16.                 return 0;
    
17.         }
    
18. 
    
19.         HashMap<Integer, Node> map = new HashMap<Integer, Node>();
    
20.         Node head = new Node(-1);
    
21.         Node tail = new Node(-1);
    
22.         head.next = tail;
    
23.         tail.prev = head;
    
24.         int count = 0;
    
25.         for(Integer k: keys) {
    
26.                 if(map.containsKey(k)){
    
27.                         Node n = map.get(k);
    
28.                         removeNode(n);
    
29.                 }else{
    
30.                         count++;
    
31.                         if(map.size() >= cap) {
    
32.                                 Node n = head.next;
    
33.                                 removeNode(n);
    
34.                                 map.remove(n.key);
    
35.                         }
    
36.                         map.put(k, new Node(k));
    
37.                 }
    
38.                 addNode(map.get(k), tail);
    
39.         }
    
40.         return count;
    
41. }
    
42. private static void addNode(Node node, Node tail) {
    
43.         Node prev = tail.prev;
    
44.         prev.next = node;
    
45.         node.prev = prev;
    
46.         node.next = tail;
    
47.         tail.prev = node;
    
48. }
    
49. private static void removeNode(Node n) {
    
50.         Node prev = n.prev;
    
51.         Node next = n.next;
    
52.         prev.next = next;
    
53.         next.prev = prev;
    
54. }

复制代码