Oliver's Blog
  • 🤩Welcome!
  • Projects
    • RISC Game
    • Mini Amazon
    • HTTP Caching Proxy
    • Course Enrollment App
    • Fitness Tracker App
    • Voice Shopping Assistant
    • Graphics Town
  • Algo
    • Binary Search
      • Classical Binary Search
      • First Position of Target
      • Last Position of Target
      • Guess Number Higher or Lower
      • Search in a Big Sorted Array
      • Total Occurrence of Target
      • First Bad Version
      • Find Minimum in Rotated Sorted Array
      • Maximum Number in Mountain Sequence
      • Search a 2D Matrix
      • Search a 2D Matrix II
      • Search for a Range
      • Smallest Rectangle Enclosing Black Pixels
      • Find Peak Element
      • Search in Rotated Sorted Array
      • Wood Cut
      • Find the Duplicate Number
      • Sqrt(x) II
      • Maximum Average Subarray II
      • Copy Books
      • How Many Problem Can I Accept
    • Linked List
      • Insert Node in Sorted Linked List
      • Merge Two Sorted Lists
      • Merge K Sorted Lists
      • LRU Cache
      • Reverse Linked List II
      • Copy List with Random Pointer
      • Reverse Nodes in k-Group
      • Add Two Numbers
      • Swap Nodes in Pairs
      • Rotate List
      • Linked List Cycle
      • Linked List Cycle II
      • Intersection of Two Linked Lists
      • Remove Linked List Elements
      • Reverse Linked List
      • Delete Node in a Linked List
      • Odd Even Linked List
      • Partition List
    • Recursion Basics
      • Fibonacci
      • Double Factorial
      • Reverse Order Storage
      • Linked List Weighted Sum In Reverse Order
    • Binary Tree
      • 1. Traversal
        • Binary Tree Preorder Traversal
        • Binary Tree Inorder Traversal
        • Binary Tree Postorder Traversal
        • Construct Binary Tree from Inorder and Postorder Traversal
        • Minimum Depth of Binary Tree
        • Find Leaves of Binary Tree
        • Reconstruct Itinerary
      • 2. Classical Questions
        • Maximum Depth of Binary Tree
        • Average of Levels in Binary Tree
        • Binary Tree Leaf Sum
        • Invert Binary Tree
        • Binary Tree Path Sum
        • Binary Tree Path Sum II
        • Binary Tree Path Sum III
        • Clone Binary Tree
        • Sum Root to Leaf Numbers
        • Binary Tree Level Sum
        • Binary Tree Paths
      • 3. Binary Search Tree
        • Insert Node in a Binary Search Tree
        • Remove Node in Binary Search Tree
        • Validate Binary Search Tree
        • Trim a Binary Search Tree
        • Search Range in Binary Search Tree
        • Inorder Successor in BST
        • Binary Search Tree Iterator
        • Recover Binary Search Tree
      • 4. Divide and Conquer
        • Balanced Binary Tree
        • Minimum Subtree
        • Subtree with Maximum Average
        • Maximum Subtree
        • Lowest Common Ancestor of a Binary Tree
        • Lowest Common Ancestor II
        • Lowest Common Ancestor III
        • Binary Tree Maximum Path Sum II
        • Binary Tree Maximum Path Sum
        • Path Sum III
      • Convert Sorted Array to Binary Search Tree
      • Path Sum
      • Lowest Common Ancestor of a Binary Search Tree
      • Sum of Left Leaves
      • Minimum Absolute Difference in BST
      • Minimum Distance Between BST Nodes
      • Convert Sorted List to Binary Search Tree
      • Range Sum of BST
      • Kth Smallest Element in a BST
      • Find Largest Value in Each Tree Row
    • Sorting
      • Sort Integers
      • Merge Two Sorted Arrays
      • Reverse Pair
      • Sort List
      • Partition Array
      • Sort Colors
      • Kth Largest Element
      • Multi-keyword Sort
    • Two Pointers
      • Window Sum
      • Two Sum - Difference equals to target
      • Valid Palindrome
      • Remove Duplicates from Sorted Array
      • Recover Rotated Sorted Array
      • Two Sum II - Input array is sorted
      • Two Sum - Unique pairs
      • Two Sum - Closest to target
    • Queue & Stack
      • Implement Queue by Interface
      • Implement Stack
      • Implement Queue by Two Stacks
      • Implement Stack by Two Queues
      • Binary Tree Level Order Traversal
      • Valid Parentheses
      • Min Stack
      • Largest Rectangle in Histogram
      • Evaluate Reverse Polish Notation
      • Implement Queue by Linked List II
      • Basic Calculator II
      • Moving Average from Data Stream
      • Reveal Cards In Increasing Order
      • Longest Valid Parentheses
    • Hash Table
      • Rehashing
      • Valid Anagram
      • Two Sum
      • Contiguous Array
      • Anagrams
      • Remove Duplicate Numbers in Array
      • Friendship Service
    • Heap & Priority Queue
      • Heapify
      • Top k Largest Numbers II
      • K Closest Points
      • Kth Smallest Number in Sorted Matrix
      • Find Median from Data Stream
      • Sliding Window Median
      • Trapping Rain Water II
      • High Five
    • BFS
      • 1. BFS in Binary Tree
        • Check Full Binary Tree
        • Binary Tree Level Order Traversal II
        • Binary Tree Maximum Path Sum II
        • Convert Binary Tree to Linked Lists by Depth
      • 2. Connected Graph & Topologic Sorting
        • Search Graph Nodes
        • Graph Valid Tree
        • Connected Component in Undirected Graph
        • Topological Sorting
        • Course Schedule
        • Course Schedule II
        • Sequence Reconstruction
        • Clone Graph
        • Alien Dictionary
    • Array
      • Remove Element
      • Search Insert Position
      • Maximum Subarray
      • Plus One
      • Merge Sorted Array
      • Pascal's Triangle
      • Pascal's Triangle II
      • Best Time to Buy and Sell Stock
      • Best Time to Buy and Sell Stock II
      • Majority Element
      • Contains Duplicate
      • Contains Duplicate II
      • Summary Ranges
      • Missing Number
      • Move Zeroes
      • Third Maximum Number
      • Binary Search
      • Pairs of Songs With Total Durations Divisible by 60
      • 3Sum
      • Median of Two Sorted Arrays
      • Running Sum of 1d Array
      • Container With Most Water
    • String
      • Longest Substring Without Repeating Characters
      • Roman to Integer
      • Implement strStr()
      • Reverse Words in a String
      • First Unique Character in a String
      • Count Unique Characters of All Substrings of a Given String
    • Math
      • Pow(x, n)
      • Narcissistic Number
      • A + B Problem
    • Dynamic Programming
      • Fibonacci Number
      • N-th Tribonacci Number
      • Climbing Stairs
      • Min Cost Climbing Stairs
    • LeetCode vs. LintCode Table
  • React Notes
    • Optimizing Performance in React
  • Golang Notes
    • Basics
      • Setup
      • Hello World
      • Structure
      • Data Types
      • Variables
      • Operators
      • Constants
      • Decision Making
      • Loops
      • Special Statements
    • Official Tutorial Notes
      • More Types
        • Functions
        • Pointers
        • Structs
        • Arrays
        • Slices
        • Range
        • Maps
        • More Functions
      • Methods and Interfaces
        • Methods
        • Interfaces
        • Stringers
        • Errors
        • Images
        • Readers
      • Concurrency
        • Goroutines
        • Channels
        • Range and Close
        • Select
        • Mutual Exclusion
  • Miscellaneous
    • Traveling to China During a Global Pandemic
Powered by GitBook
On this page
  • Solution 1 (Java)
  • Notes
  • Solution 2 (Java)
  • Notes

Was this helpful?

  1. Algo
  2. Linked List

LRU Cache

ID: 134; hard; LRU缓存策略

PreviousMerge K Sorted ListsNextReverse Linked List II

Last updated 3 years ago

Was this helpful?

Solution 1 (Java)

public class LRUCache {

    class Node {
        int key, val;
        Node next = null;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
            this.next = null;
        }
    }

    int capacity, size;
    Node dummy, end;
    HashMap<Integer, Node> keyToPrevMap;

    /*
     * @param capacity: An integer
     */
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        this.dummy = new Node(0, 0);
        this.end = this.dummy;
        this.keyToPrevMap = new HashMap<Integer, Node>();
    }

    /*
     * @param key: An integer
     * @return: An integer
     */
    public int get(int key) {
        if (!keyToPrevMap.containsKey(key))
            return -1;

        moveToEnd(key);
        return end.val;
    }

    /*
     * @param key: An integer
     * @param value: An integer
     * @return: nothing
     */
    public void set(int key, int value) {
        // Case I: replace old key and value
        if (get(key) != -1) {
            Node prev = keyToPrevMap.get(key);
            prev.next.val = value;
            return;
        }

        // Case II: add new key and value when in capacility limit
        if (size < capacity) {
            Node newNode = new Node(key, value);
            end.next = newNode;
            keyToPrevMap.put(key, end);
            end = newNode;
            size++;
            return;
        }

        // Case III: invalidate LRU item and add new key and value
        // 1. remove first/LRU node
        Node firstNode = dummy.next;
        keyToPrevMap.remove(firstNode.key);
        // 2. reuse that first node and move it to the end
        firstNode.key = key;
        firstNode.val = value;
        keyToPrevMap.put(key, dummy);
        moveToEnd(key);
    }

    private void moveToEnd(int key) {
        Node prev = keyToPrevMap.get(key);
        Node curr = prev.next;

        if (curr == end) return;
        prev.next = curr.next;
        end.next = curr;

        // update the map for prev and curr
        if (prev.next != null) {
            keyToPrevMap.put(prev.next.key, prev);
        }
        keyToPrevMap.put(curr.key, end);
        end = curr;
    }
}

Notes

We uses a singly linked list and a hash map in this solution. The linked list is basically the cache, where the head is the least recently used (LRU) and the end is the most recently used.The hash map keeps track of key and previous node pairs.

  • We first define a Node class with fields including key, val, and next.

  • Then, the fields of the LRUCache class includes:

    • capacity: the full capacity of the cache as required by user input.

    • size: the current size of the cache

    • dummy: the dummy node pointing to the head of the linked list

    • end: the end of the linked list

    • keyToPrevMap: the hash map of (key, previous node) pairs.

The get method

We first check if a node with the input key is in the map. If not, we return -1 not found. If we do find a node associated with that key, we move that node to the end of the linked list and return its value. (moveToEnd method to be completed later)

The set method

We have three cases for setting key/value pairs.

  1. The key is already contained in the map. All we need to do is find that node and change its value.

  2. Within in the capacity limit, we can directly add a new node to the end of the linked list. Do not forget to update the end, the map, and the size.

  3. When the capacity limit will be exceeded, we remove the first/LRU node from the map. Next, we reuse that first node by putting the new key and value into that node. Then, we move that node to the end of the linked list, meaning that it is the most recently used. Do not forget to update the map as well (for changing the head of the list).

The moveToEnd method

We take in a key and want to move the node associated with that key to the end of the linked list. We first remove it from where it currently is, i.e., pointing its previous node to its next node. Then, we add it at the end of the list. More importantly, do not forget to update the map since two positions in the linked list have changed and do not forget to update end as well.

Solution 2 (Java)

class LRUCache {
    
    class Node {
        int key, val;
        Node prev, next;
        public Node(int key, int val) {
            this.key = key;
            this.val = val;
            this.prev = null;
            this.next = null;
        }
    }
    
    int capacity;
    Node head, tail;
    Map<Integer, Node> map;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head = new Node(-1, -1);
        tail = new Node(-1, -1);
        head.next = tail;
        tail.prev = head;
        this.map = new HashMap<>();
    }
    
    public int get(int key) {
        if (!map.containsKey(key))
            return -1;
        Node curr = map.get(key);
        curr.prev.next = curr.next;
        curr.next.prev = curr.prev;
        moveToTail(curr);
        return curr.val;
    }
    
    public void put(int key, int value) {
        if (get(key) != -1) {
            Node curr = map.get(key);
            curr.val = value;
            return;
        }
        
        if (map.size() == capacity) {
            map.remove(head.next.key);
            head.next = head.next.next;
            head.next.prev = head;
        }
        
        Node newNode = new Node(key, value);
        map.put(key, newNode);
        moveToTail(newNode);
    }
    
    private void moveToTail(Node curr) {
        curr.prev = tail.prev;
        tail.prev = curr;
        curr.prev.next = curr;
        curr.next = tail;
    }
}

// O <-> O <-> O <-> O <-> O

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

Notes

  • Here we used a doubly linked list.

  • Note that head and tail are not actually the head and tail of the doubly linked list. Head is the node before the actual head and tail is the node after the actual tail of the list.

LintCode 炼码
Logo
Loading...LeetCode
Logo