剑指offer专项突击版第10天

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

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

class RandomizedSet {
private:
    unordered_map um;
    vector nums;
public:
    unordered_set us;
    
    RandomizedSet() {
        srand((unsigned)time(nullptr));
    }
    
    
    bool insert(int val) {
        if(um.count(val)) return false;
        nums.push_back(val);
        um[val] = nums.size()-1;
        return true;
    }
    
    
    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;
    }
    
    
    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 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;
    }

};

剑指 Offer II 032. 有效的变位词
简单哈希表（也可以先排序后再判断字符是否相等）

class Solution {
public:
    bool isAnagram(string s, string t) {
        if(s.size() != t.size() || s==t) return false;
        int st[26] = {0};
        for(int i = 0; i < s.size(); i++) {
            st[s[i]-'a']++;
            st[t[i]-'a']--;
        }
        for(int i = 0; i < 26; i++) if(st[i]) return false;
        return true;
    }
};