高级数据结构设计力扣题目总结

Category： DSA

写在前面

下面的这些数据结构都用到了链表, 可见链表在数据库/缓存等底层构件中的重要作用.

跳表: 数组+链表节点

1206. 设计跳表 - 力扣（LeetCode）;(高级数据结构, 数据库常用)

需要设计多级结构以便降低查找的时间复杂度, 相当于在一般链表中采用了二分查找的思想, 空间换时间.

class Skiplist {
    static constexpr int level = 8;
    struct Node {
        int val;
        vector<Node*> next;
        Node(int _v) : val(_v) {
            next.resize(level, nullptr);
        }
    }* head;

public:
    Skiplist() : head(new Node(-1)) {
    }
    ~Skiplist() {
        delete head;
    }
    void find(int target, vector<Node*>& pre) {
        auto cur(head);
        for (int i{level - 1}; ~i; --i) {
            while (cur->next[i] && cur->next[i]->val < target)
                cur = cur->next[i];
            pre[i] = cur;
        }
    }
    bool search(int target) {
        vector<Node*> pre(level);
        find(target, pre);
        auto p = pre[0]->next[0];
        return p && p->val == target;
    }

    void add(int num) {
        vector<Node*> pre(level);
        find(num, pre);

        auto p = new Node(num);
        for (int i{}; i < level; ++i) {
            p->next[i] = pre[i]->next[i];
            pre[i]->next[i] = p;
            if (rand() % 2)
                break;
        }
    }

    bool erase(int num) {
        vector<Node*> pre(level);
        find(num, pre);
        auto p = pre[0]->next[0];
        if (!p || p->val != num)
            return false;
        for (int i{}; i < level && pre[i]->next[i] == p; ++i)
            pre[i]->next[i] = p->next[i];
        delete p;
        return true;
    }
};

LRU缓存: 一个哈希表+双向链表

146. LRU 缓存;面试题 16.25. LRU 缓存;剑指 Offer II 031. 最近最少使用缓存;

Least Recently Used 最近最少使用

记录使用情况时, 采用双向链表实现.

经典的缓存策略(算法)

核心思路

双向链表保存使用情况以及实际数据(节点内)
哈希表保存数据的键以及键指向的实际数据的指针(指向双向链表的节点)

一些细节

双向链表实现时采用头尾哑结点, 减少判断.
每次在双向链表头部插入, 尾部弹出
put()时需要考虑两种情况, 有值: 改, 无值: 加.
get()时需要转移对应节点到链表头, 并且更新哈希表指针位置

实现

首先给出STL+迭代器版: 太慢了, 迭代器失效(地址访问错误)太烦人了…

class LRUCache {
private:
    using pii = pair<int, int>;
    list<pii> lst; // 记录使用情况和实际键值对(数据)
    unordered_map<int, list<pii>::iterator> cache; // 存键及键指向数据的指针(迭代器)
    int capacity, size;

public:
    LRUCache(int _capacity) : capacity(_capacity), size(0) {}

    int get(int key) {
        if (!cache.count(key))
            return -1;
        auto it = cache[key];
        // 用过了, 移动到前面
        lst.emplace_front(*it);
        lst.erase(it);
        cache[key] = lst.begin(); // erase之后, 迭代器失效, 需要重新赋值
        return cache[key]->second;
    }

    void put(int key, int value) {
        if (!cache.count(key)) { // 没有, 添加
            lst.emplace_front(key, value);
            cache[key] = lst.begin();
            if (++size > capacity) {
                cache.erase(lst.back().first);
                lst.pop_back();
                --size;
            }
        } else { // 修改现有的值
            auto it = cache[key];
            lst.emplace_front(key, value);
            lst.erase(it);
            cache[key] = lst.begin(); // erase之后, 迭代器失效, 需要重新赋值
        }
    }
};

手写双向链表实现: (快很多, 注意dummy节点的使用, 减少判断)

class LRUCache {
    struct Node {
        int key, val;
        Node *prev, *next;
        Node() : Node(0, 0) {}
        Node(int _key, int _val) : Node(_key, _val, nullptr, nullptr) {}
        Node(int _key, int _val, Node* _prev, Node* _next)
            : key(_key), val(_val), prev(_prev), next(_next) {}
    };
    Node *head, *tail;
    void addToHead(Node* node) {
        node->next = head->next, node->prev = head;
        head->next->prev = node, head->next = node;
    }
    void delNode(Node* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
    void moveToHead(Node* node) {
        delNode(node);
        addToHead(node);
    }
    Node* delTail() {
        auto ans{tail->prev};
        delNode(ans);
        return ans;
    }
    int capacity;
    unordered_map<int, Node*> cache;

public:
    LRUCache(int _capacity)
        : capacity(_capacity), head(new Node), tail(new Node) {
        head->next = tail, tail->prev = head;
    }

    int get(int key) {
        if (!cache.count(key)) return -1;
        auto node = cache[key];
        moveToHead(node);
        return node->val;
    }

    void put(int key, int value) {
        if (cache.count(key)) {
            auto node = cache[key];
            moveToHead(node);
            node->val = value;
        } else {
            auto node = new Node(key, value);
            cache[key] = node;
            addToHead(node);
            if (cache.size() > capacity) {
                auto tmp = delTail();
                cache.erase(tmp->key);
                delete tmp;
            }
        }
    }
};

LFU缓存: 两个哈希表+N个双向链表

460. LFU 缓存;

Least Frequently Used 最不经常使用

题解参考了: 超详细图解+动图演示 460. LFU缓存;

思路

LFU(Least Frequently Used) 最近最不常用算法，它是根据频率维度来选择将要淘汰的元素，即删除访问频率最低的元素。如果两个元素的访问频率相同，则淘汰最久没被访问的元素。也就是说LFU淘汰的时候会选择两个维度，先比较频率，选择访问频率最小的元素；如果频率相同，则按时间维度淘汰掉最久远的那个元素。

获取: get()

如果key不存在则返回-1
如果key存在，则返回对应的value，同时:
- 将元素的访问频率+1
  - 将元素从访问频率i的链表中移除，放到频率i+1的链表中
  - 如果频率i的链表为空，则从频率哈希表中移除这个链表

放置: put()

如果key已经存在，修改对应的value，并将访问频率+1
- 将元素从访问频率i的链表中移除，放到频率i+1的链表中
- 如果频率i的链表为空，则从频率哈希表中移除这个链表
如果key不存在
- 缓存超过最大容量，则先删除访问频率最低的元素，再插入新元素
  - 新元素的访问频率为1，如果频率哈希表中不存在对应的链表, 需要创建
- 缓存没有超过最大容量，则插入新元素
  - 新元素的访问频率为1，如果频率哈希表中不存在对应的链表, 需要创建

实现

class LFUCache {
    struct Node {
        int key, val, cnt;
        Node *prev{}, *next{};
        Node() : Node(0, 0) {}
        Node(int _k, int _v, int _c = 1) : key(_k), val(_v), cnt(_c) {}
    };
    struct List {
        Node *head, *tail;
        List() : head(new Node), tail(new Node) {
            head->next = tail, tail->prev = head;
        }
        ~List() {
            delete head;
            delete tail;
        }
        void add2Head(Node *node) {
            node->next = head->next, node->prev = head;
            head->next->prev = node, head->next = node;
        }
        void delNode(Node *node) {
            node->prev->next = node->next;
            node->next->prev = node->prev;
        }
        bool empty() const { return head->next == tail; }
        Node *getTail() { return !empty() ? tail->prev : nullptr; }
    };
    void inc(Node *node) {
        int freq = node->cnt;
        auto lst = cntMap[freq];
        lst->delNode(node);
        if (freq == minCnt && lst->empty()) {
            ++minCnt;
            lst->~List(); // release when minCnt==freq==1
            cntMap.erase(freq);
        }
        auto next_list = cntMap[freq + 1];
        if (!next_list) {
            next_list = new List;
            cntMap[freq + 1] = next_list;
        }
        ++node->cnt;
        next_list->add2Head(node);
    }
    int cap, minCnt;
    unordered_map<int, Node *> cache;
    unordered_map<int, List *> cntMap;

public:
    LFUCache(int capacity) : cap(capacity), minCnt() {}

    int get(int key) {
        if (!cache.count(key)) return -1;
        auto node = cache[key];
        inc(node);
        return node->val;
    }

    void put(int key, int value) {
        if (!cap) return;
        Node *node;
        if (cache.count(key)) { // found, just modify
            node = cache[key];
            node->val = value;
            inc(node);
        } else {
            if (cache.size() == cap) {
                auto min_list = cntMap[minCnt];
                node = min_list->getTail();
                cache.erase(node->key);
                min_list->delNode(node);
                delete node;
            }
            node = new Node(key, value);
            auto lst = cntMap[1];
            if (!lst) {
                lst = new List;
                cntMap[1] = lst;
            }
            lst->add2Head(node);
            cache[key] = node;
            minCnt = 1;
        }
    }
};

O(1)数据结构: 哈希表+双向链表

432. 全 O(1) 的数据结构;

请你设计一个用于存储字符串计数的数据结构，并能够返回计数最小和最大的字符串。

实现 AllOne 类：

AllOne() 初始化数据结构的对象。 inc(String key) 字符串 key 的计数增加 1 。如果数据结构中尚不存在 key ，那么插入计数为 1 的 key 。 dec(String key) 字符串 key 的计数减少 1 。如果 key 的计数在减少后为 0 ，那么需要将这个 key 从数据结构中删除。测试用例保证：在减少计数前，key 存在于数据结构中。 getMaxKey() 返回任意一个计数最大的字符串。如果没有元素存在，返回一个空字符串 “” 。 getMinKey() 返回任意一个计数最小的字符串。如果没有元素存在，返回一个空字符串 “” 。注意：每个函数都应当满足 O(1) 平均时间复杂度。

使用双向链表以及哈希来做

class AllOne {
    struct Node {
        int cnt;
        unordered_set<string> Set;
        Node *pre, *next;
        Node(int _cnt = 0) : cnt(_cnt), pre(nullptr), next(nullptr) {}
    };
    void insertNode(Node* target, Node* node) { // target 后面插入 node
        node->next = target->next, node->pre = target;
        target->next->pre = node, target->next = node;
    }
    void deleteNode(Node* node) {
        node->pre->next = node->next;
        node->next->pre = node->pre;
        delete node;
        node = nullptr;
    }
    Node *head, *tail;
    unordered_map<string, Node*> Map;

public:
    AllOne() : head(new Node), tail(new Node) {
        head->next = tail, tail->pre = head; // double dummy
    }

    void inc(string key) {
        if (Map.count(key)) {                     // 在Map中
            Node* node = Map[key];
            node->Set.erase(key);                 // 删去旧的计数
            Node* tmp = nullptr;
            if (node->next->cnt == node->cnt + 1) // 有cnt+1次数的节点
                tmp = node->next;
            else
                insertNode(node, tmp = new Node(node->cnt + 1));
            tmp->Set.insert(key);
            Map[key] = tmp;
            if (node->Set.empty()) deleteNode(node);
        } else {
            Node* node = nullptr;
            if (head->next->cnt == 1) // 有cnt==1的节点
                node = head->next;
            else                      // 没有则创建
                insertNode(head, node = new Node(1));

            node->Set.insert(key);
            Map[key] = node;
        }
    }

    void dec(string key) {
        Node* node = Map[key];
        node->Set.erase(key);
        if (node->cnt == 1) {
            Map.erase(key);
        } else {
            Node* tmp = nullptr;
            if (node->pre->cnt == node->cnt - 1)
                tmp = node->pre;
            else
                insertNode(node->pre, tmp = new Node(node->cnt - 1));
            tmp->Set.insert(key);
            Map[key] = tmp;
        }
        if (node->Set.empty()) deleteNode(node);
    }

    string getMaxKey() {
        return tail->pre->Set.empty() ? ""s : *tail->pre->Set.begin();
    }

    string getMinKey() {
        return head->next->Set.empty() ? ""s : *head->next->Set.begin();
    }
};

上篇C++并发编程实战笔记(一)线程概念与基本控制

下篇Macos下c,c++编译器路径与源码位置