LRU Cache Leetcode Rješenje

Izjava o problemu

Korištenje električnih romobila ističe LRU Cache LeetCode rješenje – “LRU Cache” traži od vas da dizajnirate strukturu podataka koja slijedi Najmanje nedavno korištena (LRU) predmemorija

Moramo implementirati klasu LRUCache koja ima sljedeće funkcije:

• LRUCache(int kapacitet): Inicijalizira LRU predmemoriju s pozitivnom veličinom kapacitet.
• int get(int key): vraća vrijednost ključa ako postoji, u suprotnom vraća -1.
• void put(int key, int value): ažurirajte vrijednost ključa ako postoji, inače umetnite par ključ-vrijednost u predmemoriju. Ako veličina predmemorije premašuje kapacitet predmemorije, uklonite ključ koji je najmanje korišten.

Primjer:

bor

Input:  ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
        [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]

Output: [null, null, null, 1, null, -1, null, -1, 3, 4]

Objašnjenje:

• LRUCache lRUCache = novi LRUCache(2);
• lRUCache.put(1,1); [predmemorija je {1=1} ]
• lRUCache.put(2,2); [cache je {1=1,2=2} ]
• lRUCache.get(1); [povratak 1]
• lRUCache.put(3,3); [LRU ključ je bio 2, uklonite ključ 2, predmemorija je {1=1,3=3} ]
• lRUCache.get(2); [povratak -1]
• lRUCache.put(4,4); [LRU ključ je bio 1, uklonite ključ 1, predmemorija je {4=4,3=3} ]
• lRUCache.get(1); [povratak -1]
• lRUCache.get(3); [povratak 3]
• lRUCache.get(4); [povratak 4]

Pristup

Ideja:

1. Glavna ideja za rješavanje ovog problema je korištenje Hashmapa a dvopovezana lista.
2. Održavajte dvostruko povezan popis i hashmap koji čuva mapiranje ključa na adresu čvora koja je prisutna na dvostruko povezanom popisu.
3. Kada se pozove konstruktor, inicijalizirajte trenutnu veličinu predmemorije kao nulu i kreirajte lažni čvor dvostruko povezane liste. Također, obrišite unose hashtable.
4. updateCache() funkcija se koristi za ažuriranje predmemorije ako je određeni ključ već prisutan u dvostruko povezanom popisu i također ažuriranje dvostruko povezanog popisa.
5. Vratit ćemo -1 kada dobiti() funkcija je pozvana, a ključ nije prisutan u predmemoriji, inače vratite vrijednost i ažurirajte predmemoriju.
6. Kada staviti() metoda je pozvana, a ključ je već prisutan u predmemoriji, ažurirajte par ključ/vrijednost i također ažurirajte predmemoriju i izmijenite dvostruko povezani popis.
7. Kada staviti() Metoda je pozvana, a ključ nije prisutan u predmemoriji, kreirat ćemo novi čvor i umetnuti čvor u dvostruko povezani popis te također umetnuti adresu ključnog čvora u hash. Također, ako je veličina predmemorije premašuje svoj maksimalni kapacitet, moramo ukloniti najmanje nedavno korištenu vrijednost ključa iz predmemorije. To se može učinkovito učiniti uz pomoć povezanog popisa.

Kodirati

LRU Cache Leetcode C++ Rješenje:

class LRUCache {
public:
    struct Node{
        Node* prev;
        Node* next;
        int data,key;
        
        Node(int key,int data){
            this->key = key;
            this->data = data;
            prev = next = nullptr;
        }
    };
    Node *dummy,*curr;
    unordered_map<int,Node*> hash;
    int max_size,curr_size;
    
    void updateCache(int key){
        if(hash[key]==curr){
            return;
        }  
        Node *node1 = hash[key]->prev,*node2 = hash[key]->next;
        node1->next = node2;
        node2->prev = node1;
        curr->next = hash[key];
        hash[key]->prev = curr;
        hash[key]->next = nullptr;
        curr = curr->next;
    }
    LRUCache(int capacity) {
        curr_size = 0;
        max_size = capacity;   
        dummy = new Node(-1,-1);
        curr = dummy;
        hash.clear();
    }
    int get(int key) {
        if(!hash.count(key)){
            return -1;
        }
        updateCache(key);
        return hash[key]->data;
    }
    void put(int key, int data) {
        if(hash.count(key)){
            hash[key]->data = data;
            updateCache(key);
        }
        else{
            if(curr_size==max_size){
                hash.erase(dummy->next->key);           
                Node *node1 = dummy,*node2 = dummy->next->next;
                node1->next = node2;
                if(node2!=nullptr){
                    node2->prev = node1;
                }
                else{
                    curr = node1;
                }
                curr_size--;
            }
            Node* newNode = new Node(key,data);
            curr->next = newNode;
            newNode->prev = curr;
            curr = curr->next;
            hash[key] = newNode;
            curr_size++;
        }
    }
};

LRU Cache Leetcode Java rješenje:

import java.util.Hashtable;
public class LRUCache {
class DLinkedNode {
  int key;
  int value;
  DLinkedNode pre;
  DLinkedNode post;
}
private void addNode(DLinkedNode node) {   
  node.pre = head;
  node.post = head.post;
  head.post.pre = node;
  head.post = node;
}
private void removeNode(DLinkedNode node){
  DLinkedNode pre = node.pre;
  DLinkedNode post = node.post;
  pre.post = post;
  post.pre = pre;
}
private void moveToHead(DLinkedNode node){
  this.removeNode(node);
  this.addNode(node);
} 
private DLinkedNode popTail(){
  DLinkedNode res = tail.pre;
  this.removeNode(res);
  return res;
}
private Hashtable<Integer, DLinkedNode> 
  cache = new Hashtable<Integer, DLinkedNode>();
private int count;
private int capacity;
private DLinkedNode head, tail;

public LRUCache(int capacity) {
  this.count = 0;
  this.capacity = capacity;
  head = new DLinkedNode();
  head.pre = null;
  tail = new DLinkedNode();
  tail.post = null;
  head.post = tail;
  tail.pre = head;
}
public int get(int key) {
  DLinkedNode node = cache.get(key);
  if(node == null){
    return -1;
  }
  this.moveToHead(node);
  return node.value;
}
public void put(int key, int value) {
  DLinkedNode node = cache.get(key);
  if(node == null){
    DLinkedNode newNode = new DLinkedNode();
    newNode.key = key;
    newNode.value = value;
    this.cache.put(key, newNode);
    this.addNode(newNode);
    ++count;
    if(count > capacity){
      DLinkedNode tail = this.popTail();
      this.cache.remove(tail.key);
      --count;
    }
  }else{
    node.value = value;
    this.moveToHead(node);
  }
}
}

Analiza složenosti za LRU Cache Leetcode rješenje

Složenost vremena

Vremenska složenost gornjeg koda je O (1) ako koristimo učinkovitu hash funkciju koja omogućuje umetanje i brisanje u O(1) vremenu. Također, dodavanje i uklanjanje čvorova s ​​dvostruko povezane liste traje O(1) vremena.

Složenost prostora

Složenost prostora gornjeg koda je NA) budući da maksimalna veličina hashmapa može biti O(N).

Referenca: https://en.wikipedia.org/wiki/Cache_replacement_policies

Glavna pitanja za intervju