Java solution using HashMap and ArrayList (30 lines)


  • 0

    Used an ArrayList to maintain the least visited/set node. If the node was set before, find its index, delete it, and add it again.

    Used a HashMap to maintain the cache table. If there is no space left, find the least used node (which should be the first node in the LinkedList, delete it in both the HashMap and ArrayList, and add the new one in both places.)

    One of the trick thing is that -- if there are no spaces left (when left > 0 is false), removing the least used one and adding the new one, but this operation does not need to increment left anymore (it's just a replacement, and left will be kept at 0)!

    public class LRUCache {
        HashMap<Integer, Integer> map;
        int left;
        ArrayList<Integer> queue = new ArrayList<Integer>();
        public LRUCache(int capacity) {
            left = capacity;
            map = new HashMap<Integer, Integer>();
        }
        
        public int get(int key) {
            if (map.containsKey(key)) {
                queue.remove(queue.indexOf(key));
                queue.add(key);
                return map.get(key);
            } else {
                return -1;
            }
        }
        
        public void set(int key, int value) {
            if (map.containsKey(key) || left > 0) {
                if (!map.containsKey(key)) {
                    left --;
                }
                map.put(key, value);
            } else {
                map.remove(queue.get(0));
                queue.remove(0);
                map.put(key, value);
            }
            if (queue.contains(key)) {  // refresh priority if was set before
                queue.remove(queue.indexOf(key));
            }
            queue.add(key);
        }
    }
    

  • 0
    R

    Does not work for all testcases


Log in to reply
 

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