Created
April 28, 2016 21:32
-
-
Save jianminchen/3dc7da7e0465819e6aa8c10c71901723 to your computer and use it in GitHub Desktop.
LRU - Least Recently Used Cache - C# code implementation with one test case
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * @see <a href="https://leetcode.com/problems/lru-cache/">LRU Cache</a> | |
| * | |
| * Julia, work on C# version | |
| */ | |
| using System.Collections.Generic; | |
| public class LRUCache | |
| { | |
| class ListNode | |
| { | |
| public int key, val; | |
| public ListNode prev, next; | |
| public ListNode(int k, int v) | |
| { | |
| key = k; | |
| val = v; | |
| prev = null; | |
| next = null; | |
| } | |
| } | |
| private int capacity, size; | |
| private ListNode dummyHead, dummyTail; | |
| // private Map<Integer, ListNode> map; Java code | |
| private Dictionary<int, ListNode> map; | |
| public bool argumentOk = true; | |
| public LRUCache(int capacity) | |
| { | |
| if (capacity <= 0) | |
| { | |
| //throw new IllegalArgumentException("Positive capacity required."); | |
| argumentOk = false; | |
| return; | |
| } | |
| this.capacity = capacity; | |
| size = 0; | |
| dummyHead = new ListNode(0, 0); | |
| dummyTail = new ListNode(0, 0); | |
| dummyTail.prev = dummyHead; | |
| dummyHead.next = dummyTail; | |
| map = new Dictionary<int, ListNode>(); | |
| } | |
| public int get(int key) | |
| { | |
| if (!map.ContainsKey(key)) | |
| { | |
| return -1; | |
| } | |
| ListNode target = map[key]; | |
| remove(target); | |
| addToLast(target); | |
| return target.val; | |
| } | |
| public void set(int key, int value) | |
| { | |
| if (map.ContainsKey(key)) | |
| { // update old value of the key | |
| ListNode target = map[key]; | |
| target.val = value; | |
| remove(target); | |
| addToLast(target); | |
| } | |
| else | |
| { // insert new key value pair, need to check current size | |
| if (size == capacity) | |
| { | |
| map.Remove(dummyHead.next.key); | |
| remove(dummyHead.next); | |
| --size; | |
| } | |
| ListNode newNode = new ListNode(key, value); | |
| map.Add(key, newNode); | |
| addToLast(newNode); | |
| ++size; | |
| } | |
| } | |
| private void addToLast(ListNode target) | |
| { | |
| target.next = dummyTail; | |
| target.prev = dummyTail.prev; | |
| dummyTail.prev.next = target; | |
| dummyTail.prev = target; | |
| } | |
| private void remove(ListNode target) | |
| { | |
| target.next.prev = target.prev; | |
| target.prev.next = target.next; | |
| } | |
| public static void Main(string[] args) | |
| { | |
| LRUCache cache = new LRUCache(4); | |
| int[][] keyValuePair = new int[5][]{ | |
| new int[2]{1,1}, | |
| new int[2]{2,1}, | |
| new int[2]{3,1}, | |
| new int[2]{4,1}, | |
| new int[2]{5,1} | |
| }; | |
| for (int i = 0; i < 4; i++ ) | |
| cache.set(keyValuePair[i][0], keyValuePair[i][1]); | |
| int value = cache.get(1); // key 1 is in LRU, so the value is 1; and also 1 is visited, then, remove key 1, and add key 1 to to last one instead. | |
| cache.set(keyValuePair[4][0], keyValuePair[4][1]); // should remove key 1, but 1 is visited recently; 2 is one to remove. | |
| int value2 = cache.get(1); // return 1 | |
| int value3 = cache.get(2); // return -1 | |
| int value4 = cache.get(3); | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment