Concise Java solution by using only two HashMaps. Simple Double linked list structure, easy to understand and beat 95%.


  • 0
    G
    class CacheNode {
      int key, val, count;
      CacheNode pre, next;
    
      public CacheNode(int key, int val) {
        this.key = key;
        this.val = val;
        this.count = 1;
      }
    
    }
    
    
    public class LFUCache {
      /**
       * Store node position in doubly linked list <key, Node>.
       */
      private Map<Integer, CacheNode> positionNodes = new HashMap<>();
    
      /**
       * Store access count and most recently used node among all of the same access count nodes
       * <access_count, most_recently_node>.
       */
      private Map<Integer, CacheNode> countMap = new HashMap<>();
      private int capacity;
      /**
       * Tail pointer, avoid null point checks.
       */
      private CacheNode tail;
    
      public LFUCache(int capacity) {
        this.capacity = capacity;
        tail = new CacheNode(-1, -1);
        tail.count = -1;
      }
    
      public int get(int key) {
        if (this.capacity == 0) {
          return -1;
        }
        CacheNode n = positionNodes.get(key);
        return n == null ? -1 : increaseCount(key);
      }
    
      /**
       * Insert node b behind node a.
       * 
       * @param a
       * @param b
       */
      private void insert(CacheNode a, CacheNode b) {
    
        /**
         * Don't have to update the same node.
         */
        if (a == b) {
          return;
        }
        CacheNode next = a.next;
        a.next = b;
        b.pre = a;
        if (next != null) {
          next.pre = b;
        }
        b.next = next;
      }
    
      public void put(int key, int value) {
        if (this.capacity == 0) {
          return;
        }
        CacheNode n = positionNodes.get(key);
        CacheNode recentlyUsed = countMap.get(1);
    
        if (n == null) {
          /**
           * Always remove tail.
           */
          if (positionNodes.size() >= this.capacity) {
            this.removeNode(tail.next);
          }
          recentlyUsed = countMap.get(1);
          CacheNode newNode = new CacheNode(key, value);
          /**
           * New node will be the most recently used node among of all nodes with access time 1.
           */
          this.insert(((recentlyUsed == null) ? tail : recentlyUsed), newNode);
          countMap.put(1, newNode);
          positionNodes.put(key, newNode);
        } else {
          n.val = value;
          increaseCount(key);
        }
      }
    
      /**
       * Increase access time and adjust position in double linked list.
       * 
       * @param key
       * @return
       */
      private int increaseCount(int key) {
        CacheNode curNode = positionNodes.get(key);
        CacheNode recentlyUsed = countMap.get(curNode.count + 1);
        if (recentlyUsed == null) {
          /**
           * If the count+1 number not in map, which means it can insert right after most recently used
           * node with the same count.
           */
          recentlyUsed = countMap.get(curNode.count);
        }
    
        if (recentlyUsed == null || recentlyUsed == curNode) {
          /**
           * No need to move postion.
           */
          this.updateFrequence(curNode);
          curNode.count++;
          countMap.put(curNode.count, curNode);
        } else {
          int count = curNode.count;
          this.removeNode(curNode);
          CacheNode newNode = new CacheNode(key, curNode.val);
          newNode.count = count + 1;
    
          this.insert(recentlyUsed, newNode);
          countMap.put(count + 1, newNode);
          positionNodes.put(key, newNode);
        }
        return curNode.val;
      }
    
      /**
       * When removing a record from countMap, always try to find if other node with the same count can
       * promoted to most recently used node. Otherwise delete the record only.
       * 
       * @param node
       */
      private void updateFrequence(CacheNode node) {
        if (countMap.get(node.count) == node) {
          if (node.pre.count == node.count) {
            countMap.put(node.count, node.pre);
          } else {
            countMap.remove(node.count);
          }
        }
      }
    
      /**
       * Remove an existing node from the linked list.
       * 
       * @param node to delete.
       */
      private void removeNode(CacheNode node) {
        this.updateFrequence(node);
        CacheNode pre = node.pre;
        CacheNode post = node.next;
        pre.next = post;
        if (post != null)
          post.pre = pre;
        positionNodes.remove(node.key);
    
      }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.