146. LRU Cache

Design and implement a data structure forLeast Recently Used (LRU) cache. It should support the following operations:getandput.

get(key)- Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value)- Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Follow up:
Could you do both operations inO(1)time complexity?

Example:

LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

S: list + hashmap

用list存储key-value的关系，list从头到尾代表其节点被使用时间的关系，头结点是最近被使用的节点，尾节点是很久没使用的节点。

因为当list满了时删除操作也要删除hashmap里对应的节点，所以list需要存储key，仅有value是不行的。

用hashmap存储key到list节点(iterator)的关系，以实现O(1)的查找效率

注意每次更新要同步更新hashmap和list

class LRUCache {
public:
    LRUCache(int capacity) {
      cap = capacity;
    }

    int get(int key) {
      if (keyToListNode.find(key) == keyToListNode.end()) {
        return -1;
      }
      updateKey(key);
      return keyValueList.begin()->second;     
    }

    void put(int key, int value) {
        if (keyToListNode.find(key) != keyToListNode.end()) {
          updateKey(key);
          keyValueList.begin()->second = value;
        } else {
          if (keyValueList.size() == cap) {
            keyToListNode.erase(keyValueList.back().first);
            keyValueList.pop_back();
          }
          keyValueList.push_front(make_pair(key, value));
          keyToListNode[key] = keyValueList.begin();
        }
    }

private:
    list<pair<int, int>> keyValueList;
    unordered_map<int, list<pair<int, int>>::iterator> keyToListNode;
    int cap;
    void updateKey(int key) {      
      auto listIt = keyToListNode[key];
      keyValueList.push_front(make_pair(listIt->first, listIt->second));
      keyValueList.erase(listIt);
      keyToListNode[key] = keyValueList.begin();
    }
};

460. LFU Cache

Design and implement a data structure forLeast Frequently Used (LFU)cache. It should support the following operations:getandput.

get(key)- Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value)- Set or insert the value if the key is not already present. When the cache reaches its capacity, it should invalidate the least frequently used item before inserting a new item. For the purpose of this problem, when there is a tie (i.e., two or more keys that have the same frequency), the leastrecentlyused key would be evicted.

Follow up:
Could you do both operations inO(1)time complexity?

Example:

LFUCache cache = new LFUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.get(3);       // returns 3.
cache.put(4, 4);    // evicts key 1.
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

S: hashmap + list

对每个frequency用一个list存储对应的key, 从到后存储，需要删除时删除list.front()

用minFreq记录当前最小的frequency，当删除某一frequency时minFrequency增加，当插入新元素时minFreq重置为1

每次更新要同步更新所有存储结构

class LFUCache {
public:
    LFUCache(int capacity) {
        cap = capacity;
        size = 0;
        minFreq = 1;
    }

    int get(int key) {
        if (keyToValFreq.find(key) == keyToValFreq.end()) return -1;
        int val = keyToValFreq[key].first;
        int freq = keyToValFreq[key].second;
        updateKeyFreq(key, freq);
        return val;
    }

    void put(int key, int value) {
        if (keyToValFreq.find(key) == keyToValFreq.end()) {
            keyToValFreq[key] = make_pair(value, 1);
            addKeyFreq(key, 1);        
            size++;
            if (size > cap) {
                int delKey = *freqToKey[minFreq].begin();
                freqToKey[minFreq].pop_front();
                keyToValFreq.erase(delKey);
                keyToListIt.erase(delKey);      
                size--;
            }
            minFreq = 1;
        } else {
            int oldFreq = keyToValFreq[key].second;        

            keyToValFreq[key].first = value;
            updateKeyFreq(key, oldFreq);
        }

     }
private:
    int cap;
    int size;
    int minFreq;
    unordered_map<int, list<int>> freqToKey;
    unordered_map<int, pair<int, int>> keyToValFreq; //对每个key，存储对应的value和frequency, 方便快速定位到它对应的freqToKey list
    unordered_map<int, list<int>::iterator> keyToListIt; //iterator是key在freqToKey list中的位置，方便删除
    void updateKeyFreq(int key, int freq) {
        freqToKey[freq].erase(keyToListIt[key]);
         if (freqToKey[freq].empty()) {
            freqToKey.erase(freq);
            if (freq == minFreq) minFreq++;
        }
        keyToValFreq[key].second++;
        addKeyFreq(key, freq + 1);
    }

    void addKeyFreq(int key, int freq) {
        if (freqToKey.find(freq) == freqToKey.end()) {
            freqToKey[freq] = list<int>{key};                
        } else {
            freqToKey[freq].push_back(key);
        }
        keyToListIt[key] = --freqToKey[freq].end();
    }
};
·            ······BBBBBBBB