大一计算机的自学总结：数据结构设计相关题

前言

说实在的，感觉这种设计数据结构的题比链表题还要ex，尤其是当哈希表和链表一起上的时候！

一、设计有setAll功能的哈希表

#include <bits/stdc++.h>
using namespace std;

int cnt=0,setAllTime=0,setAllValue;
map<int,pair<int,int> >mySet;

void put(int x,int y)
{
    mySet[x]={y,cnt};
}

void get(int x)
{
    map<int,pair<int,int> >::iterator iter=mySet.find(x);
    if(iter==mySet.end())
    {
        cout<<-1<<endl;
    }
    else
    {
        if(mySet[x].second<setAllTime)
        {
            cout<<setAllValue<<endl;
        }
        else 
        {
            cout<<mySet[x].first<<endl;
        }
    }
}

int main()
{
    int n;
    cin>>n;
    int opt,x,y;
    for(int i=0;i<n;i++)
    {
        cin>>opt;
        if(opt==1)
        {
            cin>>x>>y;
            put(x,y);
            cnt++;
        }
        else if(opt==2)
        {
            cin>>x;
            get(x);
        }
        else
        {
            cin>>x;
            setAllTime=cnt++;
            setAllValue=x;
        }
    }
}

这个题若是不要求O(1)，setAll时直接全改一遍就行了。但这里要求时间复杂度为O(1)，所以要想新的思路。

这里引入“时间戳”的方法。每加入一个元素，让cnt++，模拟时间。之后若是有setAll的操作，就记下此时的时间，只有在拿数据的时候，若是该元素的加入时间在setAllTime之前，才输出setAll时的值。这样直接对结果操作就避免了把每个数据刷一遍。

二、LRU 缓存

class LRUCache {
public:
    struct doubleList
    {
        int key;
        int val;
        doubleList* last;
        doubleList* next;
    };

    map<int,doubleList*>m;
    doubleList* head=NULL;
    doubleList* tail=NULL;
    int cap;
    
    LRUCache(int capacity) {
        cap=capacity;
    }

    void add(doubleList* node)
    {
        if(node==NULL)
        {
            return ;
        }
        if(head==NULL)
        {
            head=node;
            tail=head;
        }
        else
        {
            tail->next=node;
            node->last=tail;
            tail=tail->next;
        }
    }

    void move(doubleList* node)
    {
        if(node==tail)
        {
            return ;
        }
        if(node==head)
        {
            head=node->next;
            head->last=NULL;
        }
        else
        {
            node->last->next=node->next;
            node->next->last=node->last;
        }
        tail->next=node;
        node->last=tail;
        tail=tail->next;
    }

    doubleList* removeHead()
    {
        if(head==NULL)
        {
            return NULL;
        }
        doubleList* ans=head;
        if(head==tail)
        {
            head=NULL;
            tail=NULL;
        }
        else
        {
            head=ans->next;
            ans->next=NULL;
            head->last=NULL;
        }
        return ans;
    }
    
    int get(int key) {
        map<int,doubleList*>::iterator iter=m.find(key);
        if(iter!=m.end())
        {
            doubleList* node=iter->second;
            move(node);
            return node->val;
        }
        return -1;
    }
    
    void put(int key, int value) {
        map<int,doubleList*>::iterator iter=m.find(key);
        if(iter!=m.end())
        {
            doubleList* node=iter->second;
            node->val=value;
            move(node);
        }
        else
        {
            if(m.size()==cap)
            {
                doubleList* node=removeHead();
                m.erase(node->key);
            }
            doubleList* node=new doubleList(key,value);
            m[key]=node;
            add(node);
        }
    }
};

这个题就开始上难度了，因为要时刻记录操作早晚的信息，所以考虑使用双链表结构记录操作早晚的信息让早操作的在头节点，晚操作的在尾节点。

之后，还需要一个map来记录值和对应链表上节点的地址。之后每次从map上找对应的节点，然后每次操作都对双链表进行操作，不断更新操作时间顺序即可。

三、O(1) 时间插入、删除和获取随机元素

class RandomizedSet {
public:

    map<int,int>m;
    vector<int>arr;

    RandomizedSet() {
        srand(time(0));
    }
    
    bool insert(int val) {
        map<int,int>::iterator iter=m.find(val);
        if(iter==m.end())
        {
            arr.push_back(val);
            m[val]=arr.size()-1;
            return true;
        }
        return false;
    }
    
    bool remove(int val) {
        map<int,int>::iterator iter=m.find(val);
        if(iter!=m.end())
        {
            arr[m[val]]=arr[arr.size()-1];
            m[arr[arr.size()-1]]=m[val];
            arr.pop_back();
            m.erase(val);
            return true;
        }
        return false;
    }
    
    int getRandom() {
        return arr[rand()%arr.size()];      
    }
};

这个题要建个vector来存所有元素，方便实现随机获取。之后，为了实现删除元素之后还能保证vector里每个位置都存着有效值，所以删除时将vector最后的元素移到要删除元素的位置。为了实现查找每个元素的位置，所以要建个map来记录元素信息和存的位置。

四、O(1) 时间插入、删除和获取随机元素 - 允许重复

class RandomizedCollection {
public:
    RandomizedCollection() {
        srand(time(0));
    }
    
    map<int,set<int> >m;
    vector<int>arr;

    bool insert(int val) {
        map<int,set<int> >::iterator iter=m.find(val);
        arr.push_back(val);
        m[val].insert(arr.size()-1);
        if(iter==m.end())
        {
            return true;
        }
        return false;
    }
    
    bool remove(int val) {
        map<int,set<int> >::iterator iter=m.find(val);
        if(iter!=m.end())
        {
            int idx=*(m[val].begin());
            arr[idx]=arr.back();
            m[val].erase(idx);
            m[arr.back()].erase(arr.size()-1);
            if(idx<arr.size()-1)
            {
                m[arr[idx]].insert(idx);
            }
            if(m[val].empty())
            {
                m.erase(val);
            }
            arr.pop_back();
            return true;
        }
        return false;
    }
    
    int getRandom() {
        return arr[rand()%arr.size()];
    }
};

允许重复的话map里的值就不能只存一个位置，所以需要将map里的值部分改为一个set，来存这个键在vector里额度所有位置。

五、数据流的中位数

class MedianFinder {
public:

    priority_queue<int>small;
    priority_queue<int,vector<int>,greater<int> >big;

    MedianFinder() {
        
    }

    void balance()
    {
        if(big.size()-small.size()==2||small.size()-big.size()==2)
        {
            if(big.size()>small.size())
            {
                small.push(big.top());
                big.pop();
            }
            else
            {
                big.push(small.top());
                small.pop();
            }
        }
    }
    
    void addNum(int num) {
        if(big.empty()||big.top()<=num)
        {
            big.push(num);
        }
        else
        {
            small.push(num);
        }
        balance();
    }
    
    double findMedian() {      
        if( (big.size()+small.size() )%2==0)
        {
            return (double)(big.top()+small.top())/2;
        }
        else
        {
            return big.size()>small.size()?big.top():small.top();
        }
    }
};

这个题主要是思路很巧妙，分析中位数的特点，可以发现，中位数，比所有比它小的数都大，比所有比它大的数都小。所以，为了只对两部分的最大最小值操作，所以建立一个大根堆和一个小根堆。因为中位数的特点，所以让大根堆里放较小的那部分数，小根堆里放较大的那部分数。这样，在所有数都放入后，两个堆的堆顶就是中位数的位置。

六、最大频率栈

class FreqStack {
public:

    map<int,vector<int> >maxCnt;//最大频率栈
    map<int,int>valCnt;//查询表

    FreqStack() {
        
    }
    
    void push(int val) {
        if(valCnt.find(val)==valCnt.end())
        {
            valCnt[val]=1;
            maxCnt[1].push_back(val);
        }
        else
        {
            maxCnt[++valCnt[val]].push_back(val);
        }
    }
    
    int pop() {
        int n=maxCnt[maxCnt.size()].back();
        if(--valCnt[n]==0)
        {
            valCnt.erase(n);
        }
        maxCnt[maxCnt.size()].pop_back();
        if(maxCnt[maxCnt.size()].empty())
        {
            maxCnt.erase(maxCnt.size());
        }
        return n;
    }
};

这个题就是思路也难想，代码也难写。为了实现记录频率这个信息，所以设立一个map，键是频率，值是一个vector，用来记录所有频率为当前键的值。之后，还需要一个map来记录每个数的最大频率，也就是最大频率map的键，用来查找并输出对应值。

根据栈的特性先进后出，所以每次插入只要在对应vector上push_back和pop_back即可，输出只要输出vector.back()即可。并且，因为是栈结构，所以当频率增加时，不需要将此元素从最大频率map中删除，只需要加入更大频率里即可。

七、全 O(1) 的数据结构

class AllOne {
public:

    struct doubleList
    {
        int cnt;
        set<string>s;
        doubleList* last;
        doubleList* next;
    };

    doubleList* head=new doubleList(0);
    doubleList* tail= new doubleList(INT_MAX);

    map<string,doubleList*>wordCnt;

    AllOne() {
        head->s.insert("");
        tail->s.insert("");
        head->last=NULL;
        head->next=tail;
        tail->last=head;
        tail->next=NULL;
    }

    void insert_back(doubleList* cur,doubleList* node)
    {
        cur->next->last=node;
        node->next=cur->next;
        node->last=cur;
        cur->next=node;
    }

    void remove(doubleList* node)
    {
        node->last->next=node->next;
        node->next->last=node->last;
    }
    
    void inc(string key) {
        if(wordCnt.find(key)==wordCnt.end())
        {
            if(head->next->cnt!=1)
            {
                doubleList* node=new doubleList(1);
                node->s.insert(key);
                insert_back(head,node);
                wordCnt[key]=node;
            }
            else
            {
                head->next->s.insert(key);
                wordCnt[key]=head->next;
            }
        }
        else
        {
            doubleList* node=wordCnt[key];
            if(node->next->cnt!=node->cnt+1)
            {
                doubleList* p=new doubleList(node->cnt+1);
                p->s.insert(key);
                insert_back(node,p);
                wordCnt[key]=p;
            }
            else
            {
                node->next->s.insert(key);
                wordCnt[key]=node->next;
            }
            node->s.erase(key);
            if(node->s.empty())
            {
                remove(node);
            }
        }
    }
    
    void dec(string key) {
        doubleList* node=wordCnt[key];
        if(node->cnt==1)
        {
            wordCnt.erase(key);
        }
        else
        {
            if(node->last->cnt!=node->cnt-1)
            {
                doubleList* p=new doubleList(node->cnt-1);
                p->s.insert(key);
                insert_back(node->last,p);
                wordCnt[key]=p;
            }
            else
            {
                wordCnt[key]=node->last;
                node->last->s.insert(key);
            }
        }
        node->s.erase(key);
        if(node->s.empty())
        {
            remove(node);
        }
    }
    
    string getMaxKey() {
        return *tail->last->s.begin();
    }
    
    string getMinKey() {
        return *head->next->s.begin();
    }
};

因为有要求时间复杂度O(1)，所以不能全遍历一遍，而且，因为不只是对最后加入的数进行操作，所以不能使用最大频率栈的思路，所以考虑使用双链表的结构。

首先，要设立头尾节点，只存空字符串，方便若没有东西时返回空字符串。之后，让双向链表存一个cnt一个set，来存频率为cnt的字符串。

之后的操作都是双向链表的，说难也不难，但说简单也不简单。

总结

yysy，虽然每写完一道数据结构设计题就有种再也不想碰这种题的感觉，但坚持下来确实对coding能力有不小的提升。

END