【月度刷题计划同款】常见数据结构运用

￡神魔★判官ぃ 2023-10-09 21:32 14阅读 0赞

### 题目描述 ###

这是 LeetCode 上的 **[432. 全 O(1) 的数据结构][432. _ O_1_]** ，难度为 **困难**。

Tag : 「双向链表」、「哈希表」

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

实现 `AllOne` 类：

*  `AllOne()` 初始化数据结构的对象。
 *  `inc(String key)` 字符串 `key` 的计数增加 111 。如果数据结构中尚不存在 `key` ，那么插入计数为 111 的 `key` 。
 *  `dec(String key)` 字符串 `key` 的计数减少 111 。如果 `key` 的计数在减少后为 000 ，那么需要将这个 `key` 从数据结构中删除。测试用例保证：在减少计数前，`key` 存在于数据结构中。
 *  `getMaxKey()` 返回任意一个计数最大的字符串。如果没有元素存在，返回一个空字符串 `""` 。
 *  `getMinKey()` 返回任意一个计数最小的字符串。如果没有元素存在，返回一个空字符串 `""` 。

示例：

输入
    ["AllOne", "inc", "inc", "getMaxKey", "getMinKey", "inc", "getMaxKey", "getMinKey"]
    [[], ["hello"], ["hello"], [], [], ["leet"], [], []]
    
    输出
    [null, null, null, "hello", "hello", null, "hello", "leet"]
    
    解释
    AllOne allOne = new AllOne();
    allOne.inc("hello");
    allOne.inc("hello");
    allOne.getMaxKey(); // 返回 "hello"
    allOne.getMinKey(); // 返回 "hello"
    allOne.inc("leet");
    allOne.getMaxKey(); // 返回 "hello"
    allOne.getMinKey(); // 返回 "leet"
    复制代码

提示：

*  1<=key.length<=101 <= key.length <= 101<=key.length<=10
 *  `key` 由小写英文字母组成
 *  测试用例保证：在每次调用 `dec` 时，数据结构中总存在 `key`
 *  最多调用 `inc`、`dec`、`getMaxKey` 和 `getMinKey` 方法 5∗1045 \* 10^45∗104 次

### 双向链表 + 哈希表 ###

题目要求我们支持 O(1)O(1)O(1) 的查询和修改，其中查询只需返回任意一个计数次数「最多」和「最少」的元素即可（如果有）。

虽然插入的字符串长度不超过 101010（该数据范围的含义为字符串的哈希计算消耗可看作常数），但单纯的使用「哈希表」仅能做到 O(1)O(1)O(1) 的计数，无法做到 O(1)O(1)O(1) 查询。

*我们可以采取和 [实现一个 LRUCache][LRUCache] & [实现一个 LFUCache][LFUCache] 类似的思路，通过自定义节点并手写双链表来实现。*

定义一个节点类 `Node`，除了包含用于实现双向链表的 `left` 和 `right` 以外，还包含一个数值类型的变量 `cnt`， 用于记录该节点存储的是计数次数为多少的元素，以及一个 `Set` 类型的容器，用于支持 O(1)O(1)O(1) 插入和删除元素，记作 `set`。

同时为了快速知道某个字符串属于哪个 `Node`，我们还需要开一个「哈希表」进行定位（以字符串为哈希表的键，字符串所在 `Node` 作为值），当定位到字符串对应的 `Node` 之后则可以利用双向链表的 O(1)O(1)O(1) 增加/修改/删除。

在双向链表中，起始只有两个哨兵节点 `hh` 和 `tt` ，当进行若干 `inc/dec` 操作后的基本形态为：

![format_png][]

对应几个操作：

`inc/dec` 操作：当对一个字符串 `key` 进行「增加计数」或「减少计数」时，先在哈希表中看 `key` 是否存在：

*  若存在：根据其所属的 `Node` 的计数 `cnt` 为多少，并结合当前是「增加计数」还是「减少计数」来决定是找 `Node` 的「右节点」还是「左节点」，同时检查相邻节点的计数值 `cnt` 是否为目标值，对应要检查数值是 cnt+1cnt + 1cnt+1 和 cnt−1cnt - 1cnt−1：
    
     *  若相邻节点的 `cnt` 为目标值：即目标节点存在，将 `key` 从原 `Node` 的 `set` 集合中移除，并添加到目标节点的集合中，更新哈希表；
     *  若相邻节点的 `cnt` 不是目标值：则需要创建相应的目标节点，并构建双向链表关系，把 `key` 存入新创建的目标节点，更新哈希表。
 *  若不存在（只能是 `inc` 操作）：查找是否存在 cnt=1cnt = 1cnt=1 的节点（也就是检查 `hh.right` 节点的计数值）：
    
     *  如果存在 cnt=1cnt = 1cnt=1 的目标节点：将 `key` 添加到目标节点的 `set` 集合中，更新哈希表；
     *  若不存在 cnt=1cnt = 1cnt=1 的目标节点：创建相应的节点，并构建双向关系，并构建双向链表关系，把 `key` 存入新创建的目标节点，更新哈希表。

`getMaxKey/getMinKey` 操作：分别从 `tt.left` 和 `hh.right` 中尝试查找，如果存在非哨兵节点，则从节点的 `set` 集合中取任意元素进行返回，否则返回空串。

最后，为了确保 `getMaxKey/getMinKey` 操作能够严格 O(1)O(1)O(1)，我们在进行 `inc/dec` 操作时我们需要对一些 `set` 容量为 000 的节点进行释放，即解除其所在双向链表的关系。

代码：

class AllOne {
    
        class Node {
            int cnt;
            Set<String> set = new HashSet<>();
            Node left, right;
            Node(int _cnt) {
                cnt = _cnt;
            }
        }
        
        Node hh, tt;
        Map<String, Node> map = new HashMap<>();
        public AllOne() {
            hh = new Node(-1000); tt = new Node(-1000);
            hh.right = tt; tt.left = hh;
        }
    
        void clear(Node node) {
            if (node.set.size() == 0) {
                node.left.right = node.right;
                node.right.left = node.left;
            }
        }
        
        public void inc(String key) {
            if (map.containsKey(key)) {
                Node node = map.get(key);
                node.set.remove(key);
                int cnt = node.cnt;
                Node next = null;
                if (node.right.cnt == cnt + 1) {
                    next = node.right;
                } else {
                    next = new Node(cnt + 1);
                    next.right = node.right;
                    next.left = node;
                    node.right.left = next;
                    node.right = next;
                }
                next.set.add(key);
                map.put(key, next);
                clear(node);
            } else {
                Node node = null;
                if (hh.right.cnt == 1) {
                    node = hh.right;
                } else {
                    node = new Node(1);
                    node.right = hh.right;
                    node.left = hh;
                    hh.right.left = node;
                    hh.right = node;
                }
                node.set.add(key);
                map.put(key, node);
            }
        }
        
        public void dec(String key) {
            Node node = map.get(key);
            node.set.remove(key);
            int cnt = node.cnt;
            if (cnt == 1) {
                map.remove(key);
            } else {
                Node prev = null;
                if (node.left.cnt == cnt - 1) {
                    prev = node.left;
                } else {
                    prev = new Node(cnt - 1);
                    prev.right = node;
                    prev.left = node.left;
                    node.left.right = prev;
                    node.left = prev;
                }
                prev.set.add(key);
                map.put(key, prev);
            }
            clear(node);
        }
        
        public String getMaxKey() {
            Node node = tt.left;
            for (String str : node.set) return str;
            return "";
        }
        
        public String getMinKey() {
            Node node = hh.right;
            for (String str : node.set) return str;
            return "";
        }
    }
    复制代码

*  时间复杂度：O(1)O(1)O(1)
 *  空间复杂度：O(n)O(n)O(n)

### 最后 ###

这是我们「刷穿 LeetCode」系列文章的第 `No.432` 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

作者：宫水三叶的刷题日记  
链接：https://juejin.cn/post/722948752817653356

[432. _ O_1_]: https://link.juejin.cn?target=https%3A%2F%2Fleetcode-cn.com%2Fproblems%2Fall-oone-data-structure%2Fsolution%2Fby-ac_oier-t26d%2F
[LRUCache]: https://link.juejin.cn?target=https%3A%2F%2Fmp.weixin.qq.com%2Fs%3F__biz%3DMzU4NDE3MTEyMA%3D%3D%26mid%3D2247486820%26idx%3D1%26sn%3D2055864e10848bce55afc4e2feda79a7%26chksm%3Dfd9ca67bcaeb2f6d2038706e32cafffd701d3d6b71b60c52a568ed6dc0e268d93f8a78498105%26token%3D146288031%26lang%3Dzh_CN%23rd
[LFUCache]: https://link.juejin.cn?target=https%3A%2F%2Fmp.weixin.qq.com%2Fs%3F__biz%3DMzU4NDE3MTEyMA%3D%3D%26mid%3D2247486856%26idx%3D1%26sn%3D59b2ed57e4a75eac0e63fc0cf08bed5d%26chksm%3Dfd9ca697caeb2f81f83cdc741375f9130c3fa40463edb4ae98d702354ca106378fdfe23735ad%26token%3D146288031%26lang%3Dzh_CN%23rd
[format_png]: https://img-blog.csdnimg.cn/img_convert/9cbeb1039702d4137654353ec1e490c8.webp?x-oss-process=image/format,png