LeetCode432-全O(1)的数据结构

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/all-oone-data-structure/

中文链接：https://leetcode-cn.com/problems/all-oone-data-structure/

题目详述

实现一个数据结构支持以下操作：

  1. Inc(key) - 插入一个新的值为 1 的 key。或者使一个存在的 key 增加一，保证 key 不为空字符串。
  2. Dec(key) - 如果这个 key 的值是 1，那么把他从数据结构中移除掉。否者使一个存在的 key 值减一。如果这个 key 不存在，这个函数不做任何事情。key 保证不为空字符串。
  3. GetMaxKey() - 返回 key 中值最大的任意一个。如果没有元素存在，返回一个空字符串""。
  4. GetMinKey() - 返回 key 中值最小的任意一个。如果没有元素存在，返回一个空字符串""。

挑战：以 O(1) 的时间复杂度实现所有操作。

题目详解

类似于 LeetCode146-LRU缓存机制，运用 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
public class LeetCode_00432 {

    class AllOne {
        private class Node {
            int value;
            Set<String> keys;
            Node pre;
            Node next;

            Node(int value) {
                this.value = value;
                this.keys = new HashSet<>();
            }
        }

        private Map<String, Node> map;
        private Node head;
        private Node tail;

        public AllOne() {
            map = new HashMap<>();
            head = new Node(0);
            tail = new Node(0);
            link(head, tail);
        }

        public void inc(String key) {
            Node node = map.get(key);
            if (node == null) {
                if (head.next.value == 1) {
                    map.put(key, head.next);
                    head.next.keys.add(key);
                } else {
                    addNodeAfter(head, key, 1);
                }
            } else {
                int newValue = node.value + 1;
                if (newValue == node.next.value) {
                    map.put(key, node.next);
                    node.next.keys.add(key);
                } else {
                    addNodeAfter(node, key, newValue);
                }
                node.keys.remove(key);
                if (node.keys.isEmpty()) {
                    link(node.pre, node.next);
                }
            }
        }


        public void dec(String key) {
            Node node = map.get(key);
            if (node == null) {
                return;
            }
            int newValue = node.value - 1;
            if (newValue == node.pre.value) {
                if (newValue == 0) {
                    map.remove(key);
                } else {
                    map.put(key, node.pre);
                    node.pre.keys.add(key);
                }
            } else {
                addNodeAfter(node.pre, key, newValue);
            }
            node.keys.remove(key);
            if (node.keys.isEmpty()) {
                link(node.pre, node.next);
            }
        }

        public String getMaxKey() {
            return head.next == tail ? "" : tail.pre.keys.iterator().next();
        }

        public String getMinKey() {
            return head.next == tail ? "" : head.next.keys.iterator().next();
        }

        private void link(Node node1, Node node2) {
            node1.next = node2;
            node2.pre = node1;
        }

        private void addNodeAfter(Node node, String key, int value) {
            Node newNode = new Node(value);
            newNode.keys.add(key);
            map.put(key, newNode);
            link(newNode, node.next);
            link(node, newNode);
        }
    }
}