432_全O_1_的数据结构

难度：困难

题目

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

实现 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)

插入值时先从哈希表中查询，如果没有则创建插入到头节点后，如果存在则向后移动该节点的位置

删除值时从哈希表中取出要删除的节点，断开节点与前后的连接并减一，如果 value 变为0，则从 HashMap中删除，否则向前移动该节点的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
class AllOne {

    class ListNode{
        int value;
        String str;
        ListNode pre;
        ListNode next;
        public ListNode(int value, String str){
            this.value = value;
            this.str = str;
        }
        public void inc(){
            value = value+1;
        }
        public void dec(){
            value = value - 1;
        }
    }
    ListNode head, tail;
    Map<String, ListNode> map;
    public AllOne() {
        map = new HashMap<>();
        head = new ListNode(0,"");
        tail = new ListNode(Integer.MAX_VALUE, "");
        tail.pre = head;
        head.next = tail;
    }

    public void inc(String key) {
        if (map.containsKey(key)){
            ListNode curNode = map.get(key);
            // 将 curNode 删除
            curNode.next.pre = curNode.pre;
            curNode.pre.next = curNode.next;
            // 加一
            curNode.inc();

            // 寻找插入位置
            ListNode tempNode = curNode.next;
            // 找到下一个等于 curNode.value 的位置
            while (tempNode.value<curNode.value){
                tempNode = tempNode.next;
            }
            // 插入到 tempNode 前面
            tempNode.pre.next = curNode;
            curNode.pre = tempNode.pre;
            curNode.next = tempNode;
            tempNode.pre = curNode;
        }else {
            ListNode newNode = new ListNode(1,key);
            // 将 newNode 和前后连接
            newNode.pre = head;
            newNode.next = head.next;
            // 将前后与 newNode 连接
            newNode.next.pre = newNode;
            head.next = newNode;
            // 放入哈希表
            map.put(key,newNode);
        }
    }

    public void dec(String key) {
        ListNode curNode = map.get(key);
        // 将 curNode 删除
        curNode.pre.next = curNode.next;
        curNode.next.pre = curNode.pre;
        // 减一
        curNode.dec();
        if (curNode.value==0){
            map.remove(key);
            return;
        }
        // 寻找插入位置
        ListNode tempNode = curNode.pre;
        while (tempNode.value>curNode.value){
            tempNode = tempNode.pre;
        }
        // 插入到 tempNode 后面
        tempNode.next.pre = curNode;
        curNode.next = tempNode.next;
        curNode.pre = tempNode;
        tempNode.next = curNode;
    }

    public String getMaxKey() {
        if (tail.pre==head){
            return "";
        }
        return tail.pre.str;
    }

    public String getMinKey() {
        if (head.next==tail){
            return "";
        }
        return head.next.str;
    }
}