LCR030-LCR031哈希表的设计

剑指offer（专项突破版）5.2 哈希表的设计

设计哈希表的前提是待存入的元素需要一个能计算自己哈希值的函数。在Java中所有类型都继承了类型Object，每个Object的实例都可以通过定义函数hashCode来计算哈希值。哈希表根据每个元素的哈希值把它存储到合适的位置。

哈希表最重要的特点就是高效，只需要O（1）的时间就可以把一个元素存入或读出。在常用的基础数据结构中，数组满足这个要求。只要知道数组中的下标，就可以用O（1）的时间存入或读出一个元素。因此，可以考虑基于数组实现哈希表。

设计哈希表有3个要点。为了快速确定一个元素在哈希表中的位置，可以使用一个数组，元素的位置为它的哈希值除以数组长度的余数。由于多个哈希值不同的元素可能会被存入同一位置，数组的每个位置都对应一个链表，因此存入同一位置的多个元素都被添加到同一链表中。为了确保链表不会太长，就需要计算哈希表中元素的数目与数组长度的比值。当这个比值超过某个阈值时，就对数组进行扩容并把哈希表中的所有元素重新分配位置。

LCR030.插入、删除和随机访问都是O（1）的容器

分析

1. 插入

每次添加新数值时，先使用哈希表判断该数值是否存在，存在则直接返回false。不存在则进行插入操作，只要将该数值添加到数组尾部即可，并将该数值和其下标的映射存入哈希表。

2. 删除
   删除同样需使用哈希表判断是否存在，若不存在则返回false。存在则进行删除操作，在哈希表中删除时间复杂度为 O(1)，但是在数值中删除比较麻烦。若只是直接删除，则为了保证数组内存连续性需将删除数值后面的数值均前移一位，时间复杂度为 O(n)。比较好的处理方式是，用数组的最后一个数值去填充需要删除的数值的内存，其他数值在数组中的位置保持不变，并将这个拿来填充的数值的下标更新即可，最后只要删除数组最后一个数值，同样可以保证时间复杂度为 O(1)。

3. 随机返回
   只要随机生成数组下标范围内一个随机下标值，返回该数组下标内的数值即可。

class RandomizedSet {
private:
    unordered_map<int,int> numToLocation;
    vector<int> nums;
public:
    /** Initialize your data structure here. */
    RandomizedSet() {

    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    bool insert(int val) {
        // 已存在，返回false
        if(numToLocation.count(val)){
            return false;
        }
        numToLocation[val] = nums.size();
        nums.push_back(val);
        return true;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    bool remove(int val) {
        // 删除一个不存在的元素，返回false
        if(!numToLocation.count(val)){
            return false;
        }
        // 相当于把最后一个元素放到要删除的位置，然后删除最后一个元素
        int location = numToLocation[val];  // 记录要删除元素的位置
        numToLocation[nums.back()] = location;  // 把最后一个元素的位置标记为要删除元素的位置
        numToLocation.erase(val);   // 删除val
        nums[location] = nums.back();
        nums.pop_back();
        return true;
    }
    
    /** Get a random element from the set. */
    int getRandom() {
        return nums[rand() % nums.size()];
    }
};

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet* obj = new RandomizedSet();
 * bool param_1 = obj->insert(val);
 * bool param_2 = obj->remove(val);
 * int param_3 = obj->getRandom();
 */
CPP

LCR030结果

LCR031.LRU缓存

分析

1. 定义一个双向链表。
2. 定义一个哈希表，键是put进的键，值是链表中的结点。
3. get：不存在返回-1；存在，返回值，然后将结点移到最后（哈希表获取这个值在链表中的结点）。
4. put：不存在，插入，并插到最后；存在判断容量是否已满，满了删除头结点，不满直接插入到最后。

// 定义链表
struct LinkNode{
    int key;
    int value;
    LinkNode* prev;
    LinkNode* next;
    LinkNode():key(0),value(0),prev(NULL),next(NULL){}
    LinkNode(int _key, int _value): key(_key),value(_value),prev(NULL),next(NULL){}
};

class LRUCache {
private:
    LinkNode* head;
    LinkNode* tail;
    unordered_map<int, LinkNode*> cache;
    int cap;

public:
    LRUCache(int capacity) {
        // 使用伪头结点和伪尾结点
        head = new LinkNode();
        tail = new LinkNode();
        head->next = tail;
        tail->prev = head;
        // 初始化容量大小
        cap = capacity;
    }
    
    int get(int key) {
        // 如果不存在，返回-1
        if(!cache.count(key)){
            return -1;
        }
        else{
            // 移到链表末尾
            moveToEnd(cache[key]);
            // 返回值
            return cache[key]->value;
        }
    }
    
    void put(int key, int value) {
        // 如果存在
        if(cache.count(key)){
            // 更新值
            cache[key]->value = value;
            // 移到末尾
            moveToEnd(cache[key]);
        }
        else{
            // 判断是否满，满了就删除头
            if(cache.size() == cap){
                int delKey = deleteHead();
                cache.erase(delKey);
            }
            // 插到末尾
            LinkNode* node = new LinkNode(key,value);
            cache[key] = node;
            moveToEnd(node);
        }

    }

    // 移到表尾
    void moveToEnd(LinkNode* node){
        tail->prev->next = node;
        node->prev = tail->prev;
        node->next = tail;
        tail->prev = node;
    }

    // 删除表头
    int deleteHead(){
        int val = head->next->key;
        head->next = head->next->next;
        head->next->prev = head;
        return val;
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */
CPP

先这样吧，看了好久还是不知道哪里出了问题。以后再看。