乐趣区

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

题目形容

这是 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
  • 最多调用 incdecgetMaxKeygetMinKey 办法 $5 * 10^4$ 次

双向链表 + 哈希表

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

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

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

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

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

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

对应几个操作:

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

  • 若存在:依据其所属的 Node 的计数 cnt 为多少,并联合以后是「减少计数」还是「缩小计数」来决定是找 Node 的「右节点」还是「左节点」,同时查看相邻节点的计数值 cnt 是否为目标值,对应要查看数值是 $cnt + 1$ 和 $cnt – 1$:

    • 若相邻节点的 cnt 为目标值:即指标节点存在,将 key 从原 Nodeset 汇合中移除,并增加到指标节点的汇合中,更新哈希表;
    • 若相邻节点的 cnt 不是目标值:则须要创立相应的指标节点,并构建双向链表关系,把 key 存入新创建的指标节点,更新哈希表。
  • 若不存在(只能是 inc 操作):查找是否存在 $cnt = 1$ 的节点(也就是查看 hh.right 节点的计数值):

    • 如果存在 $cnt = 1$ 的指标节点:将 key 增加到指标节点的 set 汇合中,更新哈希表;
    • 若不存在 $cnt = 1$ 的指标节点:创立相应的节点,并构建双向关系,并构建双向链表关系,把 key 存入新创建的指标节点,更新哈希表。

getMaxKey/getMinKey 操作:别离从 tt.lefthh.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 "";
    }
}
  • 工夫复杂度:$O(1)$
  • 空间复杂度:$O(n)$

最初

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

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

为了不便各位同学可能电脑上进行调试和提交代码,我建设了相干的仓库:https://github.com/SharingSource/LogicStack-LeetCode。

在仓库地址里,你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。

更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉

本文由 mdnice 多平台公布

退出移动版