剑指offer专项突击版第10天

剑指 Offer II 030. 插入、删除和随机访问都是 O(1) 的容器

变长数组（随机访问）+哈希表（$O(1)$增、删）

class RandomizedSet {
    
private:
    unordered_map<int,int> um;
    vector<int> nums;
public:
    unordered_set<int> us;
    /** Initialize your data structure here. */
    RandomizedSet() {
    
        srand((unsigned)time(nullptr));
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    bool insert(int val) {
    
        if(um.count(val)) return false;
        nums.push_back(val);
        um[val] = nums.size()-1;
        return true;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    bool remove(int val) {
    
        if(!um.count(val)) return false;
        int idx = um[val];
        nums[idx] = nums.back();
        um[nums.back()] = idx;
        nums.pop_back();
        um.erase(val);
        return true;
    }
    
    /** Get a random element from the set. */
    int getRandom() {
    
        return nums[rand()%nums.size()];
    }
};

---

剑指 Offer II 031. 最近最少使用缓存

双向链表+哈希表
有使用（get、put）的结点添加到头结点，如果容量不够只需删除尾部结点即可

class LRUCache {
    
private:
    struct DLinkedNode {
    
        int key,value;
        DLinkedNode *next, *prev;
    }*head, *tail;
    unordered_map<int,DLinkedNode*> um;
    int capacity;    
public:
    LRUCache(int capacity) {
    
        this->capacity = capacity;
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head->next = tail;
        tail->prev = head;
    }
    
    int get(int key) {
    
        if(um.count(key)) {
    
            move_to_head(um[key]);
            return um[key]->value;
        } else {
    
            return -1;
        }
    }
    
    void put(int key, int value) {
    
        if(um.count(key)) {
    
            um[key]->value = value;
            move_to_head(um[key]);
        } else {
    
            DLinkedNode *node = new DLinkedNode();
            node->value = value;
            node->key = key;
            add_to_head(node);
            um[key]= node;
            if(um.size() > capacity) {
    
                um.erase(tail->prev->key);
                delete remove_node(tail->prev); //防止内存溢出
            }
        }
    }

    void add_to_head(DLinkedNode *node) {
    
        node->next = head->next;
        node->prev = head;
        head->next->prev = node;
        head->next = node;
    }

    void move_to_head(DLinkedNode *node) {
    
        remove_node(node);
        add_to_head(node);
    }

    DLinkedNode* remove_node(DLinkedNode *node){
    
        node->prev->next = node->next;
        node->next->prev = node->prev;
        return node;
    }

};