设计哈希映射 + 删除并获得点数

706. 设计哈希映射

没有想到resize可以这样用，要不然就做不出来了~
链地址法还没有熟练掌握。

方法一 自己瞎写的用vector

这里因为题目说0 <= key, value <= 10^6，才能用key当index这样做，但凡有小于0的key这个方法就不适用了。

class MyHashMap {
public:
    /** Initialize your data structure here. */
    vector<int> fakeH;
    MyHashMap() {

    }
    
  
  /** value will always be non-negative. */
    void put(int key, int value) {
        if(fakeH.size() <= key){
            fakeH.resize(key+1,-1);
        }
        fakeH[key] = value;
    }
    
    /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
    int get(int key) {
        if(key < fakeH.size() && fakeH[key]!=-1) return fakeH[key];
        else return -1;
    }
    
    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    void remove(int key) {
        if(key < fakeH.size())
        fakeH[key] = -1;
    }
};

/**
 * Your MyHashMap object will be instantiated and called as such:
 * MyHashMap* obj = new MyHashMap();
 * obj->put(key,value);
 * int param_2 = obj->get(key);
 * obj->remove(key);
 */

方法二 链地址法

⭐ C++ list的用法

本题考查我们对于实现哈希表，有哪些方法，分别有什么利弊？
实现哈希表的原理，其实我们会遇到一个抉择，那就是时间和空间的取舍。
实现方式有两种：
超大数组：不考虑空间复杂度，创建超大数组，每个数都能单独存入，且不会位置冲突。
链地址法：空间/时间的最佳实践，基于数组实现，并且通过一个 hashhash 函数生成一个对应的索引，当多个数索引一致的时候，再处理冲突问题，一般我们使用链地址法解决冲突。

class MyHashMap {
private:
    vector<list<pair<int, int>>> data;
    static const int base = 769;
    static int hash(int key) {
        return key % base;
    }
public:
    MyHashMap(): data(base) {}
    
    void put(int key, int value) {
        int h = hash(key);
        for (auto it = data[h].begin(); it != data[h].end(); it++) {
            if ((*it).first == key) {
                (*it).second = value;
                return;
            }
        }
        data[h].push_back(make_pair(key, value));
    }
    
    int get(int key) {
        int h = hash(key);
        for (auto it = data[h].begin(); it != data[h].end(); it++) {
            if ((*it).first == key) {
                return (*it).second;
            }
        }
        return -1;
    }
    
    void remove(int key) {
        int h = hash(key);
        for (auto it = data[h].begin(); it != data[h].end(); it++) {
            if ((*it).first == key) {
                data[h].erase(it);
                return;
            }
        }
    }
};

740. 删除并获得点数

这道题可以算打家劫舍的plus版本，也是选定一个数字，与它相邻的两个数字带来的增益点数就不能算了。
但是把它转变成打家劫舍问题，首先得创建一个数组，数组的index表示，待删除的数，vals[index]表示删除这个数所获得的增益值是多少。

方法一 转变为打家劫舍问题

class Solution {
public:
    int robe(vector<int>&nums){
        int n = nums.size();
        int a = nums[0], b = max(nums[0],nums[1]);
        for(int i = 2; i < n; i++){
            int t = max(a+(nums[i]),b);
            a = b;
            b = t;
        }
        return b;
    }
    int deleteAndEarn(vector<int>& nums) {
        int n = nums.size();
        if(n == 1) return nums[0];
        int maxVal = 0;
        for(auto it:nums){
            maxVal = max(maxVal,it);
        }
        vector<int> vals(maxVal+1,0);
        for(auto it:nums){
            vals[it]+=it;
        }
        return robe(vals);
    }
};

时间复杂度：O(N+M)，其中 N 是数组nums 的长度，M 是 nums 中元素的最大值。

空间复杂度：O(M)。

方法二 排序+动态规划

class Solution {
public:
    int robe(vector<int>&nums){
        int n = nums.size();
        // if(n == 0) return 0;
        if(n == 1) return nums[0];
        int a = nums[0], b = max(nums[0],nums[1]);
        for(int i = 2; i < n; i++){
            int t = max(a+(nums[i]),b);
            a = b;
            b = t;
        }
        return b;
    }
    int deleteAndEarn(vector<int>& nums) {
        int n = nums.size();
        if(n == 1) return nums[0];
        int maxVal = 0;
        sort(nums.begin(),nums.end());
        vector<int> sums = {nums[0]};
        int ans = 0;
        for(int i =1; i< n; i++){
            int val = nums[i];
            if(val == nums[i-1]){
                sums.back() += val;
            }else if(val == nums[i-1]+1){
                sums.push_back(val);
            }else{
                ans += robe(sums);
                sums = {val};
            }
        }
        return ans+robe(sums);
    }
};

image.png