LRU Cache LeetCode Həlli

Sual

a məhdudiyyətlərinə əməl edən məlumat strukturu dizayn edin Ən az istifadə olunan (LRU) önbelleği.

Həyata keçirir LRUCache sinif:

• LRUCache(int capacity) ilə LRU önbelleğini işə salın müsbət boy capacity.
• int get(int key) dəyərini qaytarın key açar varsa, əks halda qaytarın -1.
• void put(int key, int value) dəyərini yeniləyin key Əgər key mövcuddur. Əks halda, əlavə edin key-value keşlə cütləşdirin. Düymələrin sayı çox olarsa capacity bu əməliyyatdan qovmaq ən az istifadə olunan açar.

Funksiyaları get və put hər biri qaçmalıdır O(1) orta vaxt mürəkkəbliyi.

Misal 1:

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]]

Buraxılış

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

Izahat

LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1);    // return -1 (not found)
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4

Məhdudiyyətlər:

• 1 <= capacity <= 3000
• 0 <= key <= 10⁴
• 0 <= value <= 10⁵
• Ən çoxu 2 * 10⁵ -yə zənglər ediləcək get və put.

LRU Cache LeetCode Həlli

The LinkedHashMap üsul LinkedHashMap.removeEldestEntry önbelleğin ölçüsünün müəyyən həddi ilə məhdudlaşdığı keş verilənlər strukturlarında çox istifadə olunan bir üsuldur. Belə hallarda, removeEldestEntry Ölçü həddi keçdikdə ən köhnə girişi avtomatik silmək üçün metod təyin oluna bilər (təriflə müəyyən edilir) MAX_ENTRIES atribut)

public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

Bir misal HashMap onun işinə təsir edən iki parametrə malikdir: ilkin tutum və yük əmsalı. Tutum hash cədvəlindəki vedrələrin sayıdır, ilkin tutum isə sadəcə olaraq hash cədvəlinin yaradıldığı zaman tutumudur. Yük əmsalı, tutumu avtomatik olaraq artırılmadan əvvəl hash cədvəlinin nə qədər dolmasına icazə verildiyinin ölçüsüdür. Haş cədvəlindəki qeydlərin sayı yük əmsalının və cari tutumun məhsulundan çox olduqda, hash cədvəli yenidən qurulur (yəni daxili məlumat strukturları yenidən qurulur), beləliklə hash cədvəlində vedrələrin sayı təxminən iki dəfə çoxdur.

Bir qayda olaraq, defolt yük əmsalı (.75) vaxt və məkan xərcləri arasında yaxşı uyğunlaşma təklif edir. Daha yüksək qiymətlər boşluq yükünü azaldır, lakin axtarış xərclərini artırır (almaq və qoymaq da daxil olmaqla HashMap sinfinin əksər əməliyyatlarında əks olunur). Xəritədəki girişlərin gözlənilən sayı və onun yükləmə əmsalı onun ilkin tutumunu təyin edərkən nəzərə alınmalıdır ki, təkrar əməliyyatların sayını minimuma endirsin. Əgər ilkin tutum yükləmə əmsalına bölünən girişlərin maksimum sayından çox olarsa, heç bir rehash əməliyyatı baş verməyəcək.

LRU Cache LeetCode üçün Java Həlli

class LRUCache extends LinkedHashMap<Integer, Integer>{
  private int capacity;

  public LRUCache(int capacity) {
    super(capacity, 0.75F, true); //calling constructor of LinkedHashMap
    this.capacity = capacity;
  }

  @Override
  protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
    return size() > capacity;
  }

  public void put(int key, int value) {
    super.put(key, value);
  }

  public int get(int key) {
    return super.getOrDefault(key, -1);
  }
}

Your 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]

Expected
[null,null,null,1,null,-1,null,-1,3,4]

References

https://stackoverflow.com/questions/10901752/what-is-the-significance-of-load-factor-in-hashmap#:~:text=Default%20initial%20capacity%20of%20the,as%2016%20*%200.75%20%3D%2012%20.

https://stackoverflow.com/questions/20772869/what-is-the-use-of-linkedhashmap-removeeldestentry/20773619