关于后端:月度刷题计划同款常见数据结构运用

5次阅读

共计 3608 个字符，预计需要花费 10 分钟才能阅读完成。

这是 LeetCode 上的 432. 全 O(1) 的数据结构 ，难度为艰难。

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

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

实现 AllOne 类：

AllOne() 初始化数据结构的对象。
inc(String key) 字符串 key 的计数减少 $1$。如果数据结构中尚不存在 key，那么插入计数为 $1$ 的 key。
dec(String key) 字符串 key 的计数缩小 $1$。如果 key 的计数在缩小后为 $0$，那么须要将这个 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 <= 10$
key 由小写英文字母组成
测试用例保障：在每次调用 dec 时，数据结构中总存在 key
最多调用 inc、dec、getMaxKey 和 getMinKey 办法 $5 * 10^4$ 次

题目要求咱们反对 $O(1)$ 的查问和批改，其中查问只需返回任意一个计数次数「最多」和「起码」的元素即可（如果有）。

尽管插入的字符串长度不超过 $10$（该数据范畴的含意为字符串的哈希计算耗费可看作常数），但单纯的应用「哈希表」仅能做到 $O(1)$ 的计数，无奈做到 $O(1)$ 查问。

咱们能够采取和实现一个 LRUCache & 实现一个 LFUCache 相似的思路，通过自定义节点并手写双链表来实现。

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

同时为了疾速晓得某个字符串属于哪个 Node，咱们还须要开一个「哈希表」进行定位（以字符串为哈希表的键，字符串所在 Node 作为值），当定位到字符串对应的 Node 之后则能够利用双向链表的 $O(1)$ 减少 / 批改 / 删除。

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

对应几个操作：

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

若存在：依据其所属的 Node 的计数 cnt 为多少，并联合以后是「减少计数」还是「缩小计数」来决定是找 Node 的「右节点」还是「左节点」，同时查看相邻节点的计数值 cnt 是否为目标值，对应要查看数值是 $cnt + 1$ 和 $cnt – 1$：
- 若相邻节点的 cnt 为目标值：即指标节点存在，将 key 从原 Node 的 set 汇合中移除，并增加到指标节点的汇合中，更新哈希表；
- 若相邻节点的 cnt 不是目标值：则须要创立相应的指标节点，并构建双向链表关系，把 key 存入新创建的指标节点，更新哈希表。
若不存在（只能是 inc 操作）：查找是否存在 $cnt = 1$ 的节点（也就是查看 hh.right 节点的计数值）：
- 如果存在 $cnt = 1$ 的指标节点：将 key 增加到指标节点的 set 汇合中，更新哈希表；
- 若不存在 $cnt = 1$ 的指标节点：创立相应的节点，并构建双向关系，并构建双向链表关系，把 key 存入新创建的指标节点，更新哈希表。

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

最初，为了确保 getMaxKey/getMinKey 操作可能严格 $O(1)$，咱们在进行 inc/dec 操作时咱们须要对一些 set 容量为 $0$ 的节点进行开释，即解除其所在双向链表的关系。

代码：

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 "";
    }
}