5 - 设计数据结构

发表于 更新于 分类于 ， ， 阅读次数： Waline： 本文字数： 6.5k 阅读时长 ≈ 5 分钟

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

最大频率栈

895. 最大频率栈 - 力扣（LeetCode）

确定基本数据结构

可以将栈 按频率拆分。例如示例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，接下来康康怎么设计：

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

    这句话指出LRU是有容量的，因此得添加一个私有成员变量m_capacity。

  2. int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。

    这句话指出存储的内容是{key, value}结构，并且要求给出key可以返回value，可考虑用unordered_map来存储两者的映射关系。

  3. void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

    这句话说明了LRU的核心算法内容，可以用堆，双向循环链表等数据结构存储{key-value}节点。

  4. 函数 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;
}