5 - 设计数据结构

有时候会碰见代码量很大，让你设计一个数据结构的题，如果没提前刷过一定会紧张，进而导致写不出来，一定要好好练习。

最大频率栈

确定基本数据结构

可以将栈 按频率拆分。例如示例1：

5入频率为1的栈，[5]
7入频率为1的栈，[5, 7]
5入频率为2的栈，[5, 7], [5]
7入频率为2的栈，[5, 7], [5, 7]
4入频率为1的栈，[5, 7, 4], [5, 7]
5入频率为3的栈，[5, 7, 4], [5, 7], [5]
元素出栈，最外侧元素为5，那么5出栈，[5, 7, 4], [5, 7]，......

因此，我们需要一个vector<stack<int>>来存储这些频率栈，另外，数字和它的频率的映射关系需要用一个unordered_map<int, int>来存。本题用到的数据结构如下：

unordered_map<int, int> m_numToFrequency;
vector<stack<int>> m_frequencyStk;

设计算法

void push(int key)

该函数要求我们将一个值为key的元素压栈。在元素入栈时，有如下情况：

有必要创建一个新栈（如上面的5入频率为1，2的栈），然后新元素入栈
新元素直接入已有的栈（如上面的4如频率为1的栈）

插入元素后，还要更新它的频率。

因此算法代码如下：

void push(int val) {
    // 是否有必要创建新栈
    if (m_numToFrequency[val] >= m_frequencyStk.size())
        m_frequencyStk.push_back({});
    // 新元素入栈, 更新它的频率
    m_frequencyStk[m_numToFrequency[val]].push(val);
    m_numToFrequency[val]++;
}

int pop()

该函数要求我们返回“栈顶”元素。我们直接返回频率最大的栈顶元素即可，如果元素出栈后栈空，记得删除这个栈。

参考代码如下：

int pop() {
    int ans = m_frequencyStk.back().top();
    m_frequencyStk.back().pop();
    m_numToFrequency[ans]--;

    // 别忘了删除空栈
    if (m_frequencyStk.back().empty())
        m_frequencyStk.pop_back();

    return ans;
}

餐盘栈

1172. 餐盘栈 - 力扣（LeetCode）

确定基本数据结构

给定每个栈的最大容量capacity，将元素存储在vector<stack<int>>中。对于入栈操作，它要找 下标最小的非满栈 入栈；对于出栈操作，它要找 下标最大的非空栈 出栈，而这样的要求容易想到使用set存储下标（因为优先队列有重复下标，而set刚好也是有序的）。

因此用到的基本数据结构如下：

int m_capacity;
vector<stack<int>> m_stks;
priority_queue<int, vector<int>, greater<int>> m_pushQ;
priority_queue<int> m_popQ;

设计算法

void push(int val)

该函数要求将val压入 下标最小的非满栈，分如下情况：

m_pushQ为空，说明当前栈都满了，或者是初始情况。此时应该给m_stks新建一个空栈，然后将该元素压入栈中，最后维护集合。
m_pushQ不为空，那么直接在m_stks[m_pushQ.top()]处将该元素压栈即可，最后维护集合。

参考代码如下：

void push(int val) {
    // 所有栈都满了/初始情况
    if (m_pushQ.empty())
    {
        m_stks.push_back({});
        m_pushQ.insert(m_stks.size() - 1);
    }
    // 该元素入栈
    m_stks[*m_pushQ.begin()].push(val);
    // 维护
    m_popQ.insert(*m_pushQ.begin());
    if (m_stks[*m_pushQ.begin()].size() >= m_capacity)
    {
        m_pushQ.erase(*m_pushQ.begin());
    }
}

int pop()

该函数要求返回下标最大的非空栈的栈顶元素，并将其出栈，分如下情况：

m_popQ为空，说明当前没有非空栈，返回-1。
m_popQ不空，那么进行popAtStack(m_popQ最后一个元素)即可。

参考代码如下：

int pop() {
    return m_popQ.empty() ? -1 : popAtStack(*(--m_popQ.end()));
}

int popAtStack(int index)

按要求返回对应的栈顶元素，然后出栈，最后维护集合；如果对应栈为空，那么返回-1。参考代码如下：

int popAtStack(int index) {
    if (m_stks.size() < index + 1 || m_stks[index].empty())
        return -1;

    int ans = m_stks[index].top();
    m_stks[index].pop();

    // 维护
    m_pushQ.insert(index);
    if (m_stks[index].empty())
        m_popQ.erase(index);

    return ans;
}

LRU缓存

146. LRU 缓存 - 力扣（LeetCode）

确定基本数据结构

这道题让设计一个LRU缓存类LRUCache，接下来康康怎么设计：

LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存。

这句话指出LRU是有容量的，因此得添加一个私有成员变量m_capacity。
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。

这句话指出存储的内容是{key, value}结构，并且要求给出key可以返回value，可考虑用unordered_map来存储两者的映射关系。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该逐出最久未使用的关键字。

这句话说明了LRU的核心算法内容，可以用堆，双向循环链表等数据结构存储{key-value}节点。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

这句话要求算法的时间复杂度，因此应该使用双向循环链表来存储{key-value}节点，这种数据结构插入、删除的复杂度为O(1)；至于映射关系可以用上面说过的unordered_map来存储，查询key得到value的时间复杂度也是O(1)。

接下来，先康康双向循环列表的单个节点是怎么定义的：

struct Node
{
    int key, val;
    Node *prev, *next;

    Node(int key, int val)
        : key(key), val(val), prev(nullptr), next(nullptr) 
    {}
};

然后是LRUCache的雏形：

class LRUCache {
private:
    struct Node
    {
        int key, val;
        Node *prev, *next;

        Node(int key, int val)
            : key(key), val(val), prev(nullptr), next(nullptr) 
        {}
    };

    // "删除"该位置的节点
    void remove(Node* node)
    {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
    // 将已有节点放至dummy后
    void push_front(Node* node)
    {
        node->prev = dummy;
        node->next = dummy->next;
        node->prev->next = node;
        node->next->prev = node;
    }
    // 获取指定Key的节点, 顺便更新最新使用
    Node* get_node(int key)
    {
        auto it = keyToNode.find(key);
        if (it == keyToNode.end())
            return nullptr;
        
        // 找到了
        Node* ans = it->second;
        remove(ans);
        push_front(ans);
        return ans;
    }
public:
    LRUCache(int capacity)
        : capacity(capacity)
    {
        dummy = new Node(-1, -1);
        dummy->prev = dummy->next = dummy;
    }
    
    int get(int key) {
    }
    
    void put(int key, int value) {
    }

private:
    int capacity;
    unordered_map<int, Node*> keyToNode;
    Node* dummy;
};

这里用一个假头节点Dummy充当双向循环链表的头节点，以方便操作。

设计算法

int get(int key)

有了上面的辅助函数get_node(int key)，我们只需对它进行封装即可：

int get(int key) {
    Node* node = get_node(key);
    return node ? node->val : -1;
}

void put(int key, int value)

put()分如下情况：

更新一个key存在的节点，只需更新该节点的值，然后按LRU规则，将它放在dummy->next。
更新一个key不存在的节点，得new一个，然后按LRU规则将它放在dummy->next。接下来检查容量是否超了，超了的话就把最老的节点（dummy->prev）删掉。

void put(int key, int value) {
    // key存在, 按LRU规则更新
    Node* node = get_node(key);
    if (node) 
    {
        node->val = value;
        return;
    }    

    // key不存在, 插入节点
    node = new Node(key, value);
    keyToNode[key] = node;
    push_front(node);

    // 如果超过容量, 就要删除最旧节点
    if (keyToNode.size() > capacity)
    {
        Node *oldest = dummy->prev;
        keyToNode.erase(oldest->key);
        remove(oldest);
        delete oldest;
    }
}

LFU缓存

460. LFU 缓存 - 力扣（LeetCode）

确定基本数据结构

在LRU的基础上添加了“计数器”这一概念，这个计数器也能用unordered_map来存。可看作好几个LRU在分开存储，它们的区别就是“计数”不同。例如，首先put(1,1)，在LRU[1]的假头节点后插入(1, 1)；然后再put(1,1)，就先把LRU[1]的(1, 1)删除，然后在LRU[2]的假头节点后插入(1, 1)。

因此用到的数据结构如下：

struct Node
{
    int key, val, freq;
    Node *prev, *next;

    Node(int key, int val, int freq) : key(key), val(val), freq(freq)
    {
        prev = next = nullptr;
    }
};

int m_capacity， m_minFreq;
unordered_map<int, Node*> m_keyToNode;
unordered_map<int, Node*> m_FreqToDummy; 

然后是有关双向循环链表的相关函数：

// 新建一个LRU链表, 返回假头节点的地址
Node* new_lru(int freq)
{
    Node* dummy = new Node(-1, -1, freq);
    dummy->prev = dummy->next = dummy;
    return dummy;
}

// "删除"当前节点
void remove(Node* node)
{
    node->prev->next = node->next;
    node->next->prev = node->prev;
}

// 将LRU[freq]的节点node插到表头
void push_front(int freq, Node* node)
{
    // 更新dummy
    auto it = m_FreqToDummy.find(freq);
    if (it == m_FreqToDummy.end())
        m_FreqToDummy[freq] = new_lru(freq);

    // 更新node
    Node* dummy = m_FreqToDummy[freq];
    node->prev = dummy;
    node->next = dummy->next;
    node->prev->next = node;
    node->next->prev = node;
}

// 获取key为key的节点, 顺便进行LFU更新
Node* get_node(int key)
{
    auto it = m_keyToNode.find(key);
    if (it == m_keyToNode.end())
        return nullptr;

    // 获取Node*, 然后按LFU更新
    Node* node = it->second;
    node->freq++;
    remove(node);
    push_front(node->freq, node);

    // 如果此时minFreq指向的LRU链表没节点了, 就更新minFreq
    if (m_FreqToDummy[m_minFreq]->next == m_FreqToDummy[m_minFreq])
           m_minFreq++;

    return node;
}

设计算法

int get(int key)

还是老样子：

int get(int key) {
    Node* node = get_node(key);
    eturn node ? node->val : -1;
}

void put(int key, int value)

和以前的类似，但要注意删除节点的策略，应删除 LRU[m_minFreq]的最老节点：

void put(int key, int value) {
    Node* node = get_node(key);
    // 老节点, 直接更换value
    if (node)
    {
        node->val = value;
        return;
    }
    // 如果大小超限, 就删除最旧且频率最少的
    if (m_keyToNode.size() >= m_capacity)
    {
        Node* dummy = m_FreqToDummy[m_minFreq];
        Node* oldest = dummy->prev;
        remove(oldest);
        m_keyToNode.erase(oldest->key);
        delete oldest;
    }
    // 新节点
    node = new Node(key, value, 1);
    m_keyToNode[key] = node;
    push_front(1, node);
    m_minFreq = 1;
}

最大频率栈​

确定基本数据结构​

设计算法​

void push(int key)​

int pop()​

餐盘栈​

确定基本数据结构​

设计算法​

void push(int val)​

int pop()​

int popAtStack(int index)​

LRU缓存​

确定基本数据结构​

设计算法​

int get(int key)​

void put(int key, int value)​

LFU缓存​

确定基本数据结构​

设计算法​

int get(int key)​

void put(int key, int value)​

最大频率栈

确定基本数据结构

设计算法

void push(int key)

int pop()

餐盘栈

确定基本数据结构

设计算法

void push(int val)

int pop()

int popAtStack(int index)

LRU缓存

确定基本数据结构

设计算法

int get(int key)

void put(int key, int value)

LFU缓存

确定基本数据结构

设计算法

int get(int key)

void put(int key, int value)