algo-aha

都要用个哈希表将查找值=映射到=>存储位置，而存储位置=也要能映射回=>查找值。

O(1)时间插入删除

• https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed/

无重复值：值=>值在数组的idx；有重复值：值=>值在数组的idx集合。在数组末增减元素。

O(1)时间增减频率值

• https://leetcode.com/problems/all-oone-data-structure/

class AllOne {
    // 映射表table按值分行
    struct ValueRow { int value; unordered_set<string> keys; };
    list<ValueRow> table;
    unordered_map<string, list<ValueRow>::iterator> rowPtrs;
private:
    void deleteKey(const string &key, list<ValueRow>::iterator &row) {
        row->keys.erase(key);
        if (row->keys.empty()) table.erase(row);
        rowPtrs.erase(key);
    }

    void insertKey(const string &key, list<ValueRow>::iterator &row) {
        row->keys.insert(key);
        rowPtrs[key] = row;
    }

    void moveKey(const string &key, list<ValueRow>::iterator &from, list<ValueRow>::iterator &to) {
        deleteKey(key, from);
        insertKey(key, to);
    }
public:
    /** Initialize your data structure here. */
    AllOne() {
    }
    
    /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
    void inc(string key) {
        if (!rowPtrs.count(key)) { // 先插入0，待会儿和其他情况一起增1
            rowPtrs[key] = table.insert(table.begin(), {0, { key }}); 
        }
        auto currRow = rowPtrs[key], nextRow = next(currRow); 
        int nextValueNeeded = currRow->value + 1;
        if (nextRow == table.end() || nextRow->value != nextValueNeeded) { // 插入新行
            nextRow = table.insert(nextRow, {nextValueNeeded, { }});
        }
        moveKey(key, currRow, nextRow);
    }
    
    /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
    void dec(string key) {
        if (!rowPtrs.count(key)) return;
        auto currRow = rowPtrs[key];
        if (currRow->value == 1) {
            deleteKey(key, currRow);
            return;
        }
        auto prevRow = prev(currRow);
        int prevValueNeeded = currRow->value - 1;
        if (currRow == table.begin() || prevRow->value != prevValueNeeded) {
            prevRow = table.insert(currRow, {prevValueNeeded, { }});
        }
        moveKey(key, currRow, prevRow);
    }
    
    /** Returns one of the keys with maximal value. */
    string getMaxKey() {
        return table.empty() ? "" : *table.rbegin()->keys.begin();
    }
    
    /** Returns one of the keys with Minimal value. */
    string getMinKey() {
        return table.empty() ? "" : *table.begin()->keys.begin();        
    }
};

LRU cache

• https://leetcode.com/problems/lru-cache/

比按频率分行的情况简单，只需1维链表。

class LRUCache{
    // 把entry{key,value}用链表串起来，
    // 每次访问把entry移到表头，删除lru时删除表尾
    struct Entry { int key; int value; };
    list<Entry> l; // 实际存储
    unordered_map<int, list<Entry>::iterator> entryPtrs; // key=>entry
    int capacity;
private:
    void touch(int key) {
        // toList.splice(toListIterator, fromList, fromListSingleIterator)
        l.splice(l.begin(), l, entryPtrs[key]);
        entryPtrs[key] = l.begin();
    }
public:
    LRUCache(int capacity) {
        this->capacity = capacity;
    }
    
    int get(int key) {
        if (!entryPtrs.count(key)) return -1;
        touch(key);
        return entryPtrs[key]->value;
    }
    
    void put(int key, int value) {
        if (capacity == 0) return;
        if (!entryPtrs.count(key)) {
            if (l.size() == capacity) { // 删除表尾
                entryPtrs.erase(l.back().key);
                l.pop_back();
            }
            l.push_front({key, value});
            entryPtrs[key] = l.begin();
        } else {
            entryPtrs[key]->value = value;
            touch(key);
        }
    }
};

LFU Cache

• https://leetcode.com/problems/lfu-cache/

class LFUCache {
    // 映射表table按频率分行，每行行首放最近使用项
    struct Entry { int key; int value; };
    struct FreqRow { int freq; list<Entry> entries; };
    list<FreqRow> table;
    struct EntryPtr { list<FreqRow>::iterator row; list<Entry>::iterator entry; };
    unordered_map<int, EntryPtr> entryPtrs;
    int capacity;
private:
    void moveKey(int key, list<FreqRow>::iterator &to) {
        auto from = entryPtrs[key].row;
        to->entries.splice(to->entries.begin(), from->entries, entryPtrs[key].entry);
        if (from->entries.empty()) table.erase(from);
        entryPtrs[key] = { to, to->entries.begin() };
    }

    // 将entry从原行删除、插入"freq+1"行
    void incFreq(int key) {
        auto currRow = entryPtrs[key].row, nextRow = next(currRow);
        int nextFreq = currRow->freq + 1;
        if (nextRow == table.end() || nextRow->freq != nextFreq) { // 插入新行
            nextRow = table.insert(nextRow, { nextFreq, { }});
        }
        moveKey(key, nextRow);
    }
    
    // 删除最小频率lfu的行中最少最近使用lru项
    void evict() {
        if (table.empty()) return;
        auto lfu = table.begin();
        entryPtrs.erase(lfu->entries.back().key);
        lfu->entries.pop_back();
        if (lfu->entries.empty()) table.erase(lfu);
    }
public:
    LFUCache(int capacity) {
        this->capacity = capacity;
    }
    
    int get(int key) {
        if (!entryPtrs.count(key)) return -1;
        incFreq(key);
        return entryPtrs[key].entry->value;
    }
    
    void put(int key, int value) {
        if (capacity == 0) return;
        if (!entryPtrs.count(key)) {
            if (entryPtrs.size() == capacity) evict();
            // 先插入freq=0的行，待会儿和其他情况一起增1
            auto row = table.insert(table.begin(), { 0, {{key, value}} });
            entryPtrs[key] = { row, row->entries.begin() };
        } else {
            entryPtrs[key].entry->value = value;
        }
        incFreq(key);
    }
};