Try 14 times and finally get passed (Java)


  • 0
    J

    Run time: 992 ms

    Data Structure:

    • Use Map to get & set (key, value) pair with O(1) time.
    • Keep the first node & last node of an linkedlist: First-->..-->..-->..-->Last

      Method:
    • Keep a method called moveToEnd(), moving the most recently used key to the end of my LinkedList
      public class LRUCache {
      private class Node {
          int key;
          Node next;
      }
      
      HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
      private Node first, last;
      private int capacity;
      
      public LRUCache(int capacity) {
          this.capacity = capacity;
          last = new Node();
      }
      
      public int get(int key) {
          if (map.containsKey(key)) {
              moveToEnd(key);
              return map.get(key);
          } else {
              return -1;
          }
      }
      
      public void set(int key, int value) {
          // add to queue
          if (!map.containsKey(key)) {
              Node oldLast = last;
              last = new Node();
              last.key = key;
              last.next = null;
              if (first == null) first = last;
              else oldLast.next = last;
          } else {
              moveToEnd(key);
          }
          map.put(key, value);
          
          if (map.size() > capacity) {
              int keyOfFirst = first.key;
              first = first.next;
              if (first == null) last = null;
              map.remove(keyOfFirst);
          }
      }
      
      private void moveToEnd(int key) {
          if (last != null && last.key == key) return;
          if (first == null) return;
          if (first.key == key) {
              first = first.next;
              Node oldLast = last;
              last = new Node();
              last.key = key;
              last.next = null;
              if (first == null) first = last;
              else oldLast.next = last;
              if (first==null) return;
          } else {
              Node copyOfFirst = first;
              while (first.next != null) {
                  if (first.next.key == key) {
                      first.next = first.next.next;
                      
                      Node oldLast = last;
                      last = new Node();
                      last.key = key;
                      last.next = null;
                      if (first == null) first = last;
                      else oldLast.next = last;
                      break;
                  }
                  first = first.next;
              }
              first = copyOfFirst;
          }
      }
      

      }


  • 0
    R

    If you have a @code while loop if your solution. It may not be the O(1) time complexity.


Log in to reply
 

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