[数据结构与算法]基于leetcode的算法训练：Day7

1、插入、删除和随机访问

题目描述：
设计一个支持在平均 时间复杂度 O(1) 下，执行以下操作的数据结构：

• insert(val)：当元素 val 不存在时返回 true ，并向集合中插入该项，否则返回 false 。
• remove(val)：当元素 val 存在时返回 true ，并从集合中移除该项，否则返回 false 。
• getRandom：随机返回现有集合中的一项。每个元素应该有 相同的概率 被返回。

题目链接：
插入、删除和随机访问传送门
WA code
样例通过了17/19，getRandom()使用srand的话输出的并不满足随机且概率相等这个条件

class RandomizedSet {
    struct Node{
        int val;
        Node* next=NULL;
    };
public:
    /** Initialize your data structure here. */
    Node*head=NULL;
    int len=0;
    int total=0;
    RandomizedSet() {
        head=new Node;
        total++;
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    bool insert(int val) {
        Node*p=head->next;
        Node*pre=head;
        total++;
        while(p!=NULL){
            if(p->val==val){
                return false;
            }
            if(p->val>val){
                Node*node=new Node;
                node->val=val;
                pre->next=node;
                node->next=p;
                break;
            }
            pre=p;
            p=p->next;
        }
        Node*node=new Node;
        node->val=val;
        pre->next=node;
        node->next=p;
        len++;
        return true;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    bool remove(int val) {
        total++;
        Node*p=head->next;
        Node*pre=head;
        while(p!=NULL){
            if(p->val==val){
                pre->next=p->next;
                delete(p);
                len--;
                return true;
            }
            pre=p;
            p=p->next;
        }
        return false;
    }
    
    /** Get a random element from the set. */
    int getRandom() {
        total++;
        int pos=total%len;
        Node*p=head->next;
        int cnt=0;
        while(p!=NULL){
            if(cnt==pos){
                return  p->val;
            }else{
                p=p->next;
                cnt++;
            }
        }
        return  -1;
    }
};

/**
 * 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();
 */

官方题解
为了满足插入、删除和随机访问元素操作的时间复杂度都是 O(1)，需要将变长数组和哈希表结合，变长数组中存储元素，哈希表中存储每个元素在变长数组中的下标.
学习了C++类的写法~
同时一些效率优化见code中的注释：

• emplace_back()
• 哈希表的.count()

class RandomizedSet {
   
public:
    /** Initialize your data structure here. */
    
    RandomizedSet() {
        srand((unsigned)time(NULL));//设置随机种子
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    bool insert(int val) {
        if(find(vec.begin(),vec.end(),val)!=vec.end()){//hash_table.count(val)!=0的效率更高
            return false;
        }else{
            vec.push_back(val);//emplace_back()的效率更高
            hash_table[val]=len;
            len++;
            return true;
        }
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    bool remove(int val) {
        if(find(vec.begin(),vec.end(),val)==vec.end()){//hash_table.count(val)==0的效率更高
            return false;
        }else{
            int pos=hash_table[val];
            hash_table[vec[len-1]]=pos;
            swap(vec[len-1],vec[pos]);
            len--;
            vec.pop_back();
            hash_table.erase(val);
            return true;
        }
    }
    
    /** Get a random element from the set. */
    int getRandom() {
       int pos=rand()%len;
       return vec[pos];
    }
private:
    unordered_map<int,int>hash_table;//哈希表存储：key-index映射
    vector<int>vec;//数组
    int len=0;
};

/**
 * 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();
 */

2、LRU

题目描述：
题目链接：
AC代码
时间复杂度和空间复杂度控制得都不是很好……但是还是很容易看懂思路：

• cnts用来存储当前key值上一次被使用时的时间，全局变量cur_time在每次执行函数的时候自增以记录时间
• mp用来记录key:value的对应关系

class LRUCache {
public:
    int Capacity;
    int cur_capacity=0;
    int cur_time=0;
    map<int,int>mp;//key:value
    map<int,int>cnts;//key:time
    LRUCache(int capacity) {
        Capacity=capacity;//初始化缓存
    }
    
    int get(int key) {
        cur_time++;
        if(mp.find(key)!=mp.end()){
            cnts[key]=cur_time;//更新当前key被想起来的时间
            return mp[key];
        }else{
            return -1;
        }
    }
    
    void put(int key, int value) {
        cur_time++;
        if(mp.find(key)!=mp.end()){
            cnts[key]=cur_time;//更新当前key被想起来的时间
            mp[key]=value;
        }else{
            if(cur_capacity<Capacity){
                //有空间，直接加
                cur_capacity++;
                cnts[key]=cur_time;//更新当前key被想起来的时间
                mp[key]=value;
            }else{
                //没有空间，需要删除一个最近没使用的
                int tkey,min_time=INT_MAX;
                for(map<int,int>::iterator it=cnts.begin();it!=cnts.end();it++){
                    if(it->second<min_time){
                        min_time=it->second;
                        tkey=it->first;
                    }
                }
                //删除
                cnts.erase(tkey);
                mp.erase(tkey);
                //插入
                cnts[key]=cur_time;//更新当前key被想起来的时间
                mp[key]=value;
            }
        }
    }
};

/**
 * 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);
 */