leetcode

0 class AllOne {

1 struct Node {

2 int freq = 0;

3 Node *prev = nullptr;

4 Node *next = nullptr;

5 unordered_set<string> keys;

6 };

7

8 unordered_map<string, Node *> map;

9 Node head = {0, nullptr, &tail};

10 Node tail = {0, &head, nullptr};

11

12 public:

13 void inc(const string &key) {

14 if (map.find(key) != map.end()) {

15 Node *node = map[key];

16 int freq = node->freq;

17 node->keys.erase(key);

18

19 Node *nnode = node->next;

20 if (nnode == &tail || nnode->freq != freq + 1) {

21 map[key] = node->next = nnode->prev = new Node(freq + 1, node, nnode, {key});

22 } else {

23 nnode->keys.insert(key);

24 map[key] = nnode;

25 }

26

27 if (node->keys.empty()) {

28 removeNode(node);

29 }

30 } else {

31 Node *firstNode = head.next;

32 if (firstNode == &tail || firstNode->freq > 1) {

33 map[key] = head.next = firstNode->prev = new Node(1, &head, firstNode, {key});

34 } else {

35 firstNode->keys.insert(key);

36 map[key] = firstNode;

37 }

38 }

39 }

40

41 void dec(const string &key) {

42 if (map.find(key) == map.end()) {

43 return;

44 }

45

46 Node *node = map[key];

47 node->keys.erase(key);

48

49 int freq = node->freq;

50 if (freq == 1) {

51 map.erase(key);

52 } else {

53 Node *pnode = node->prev;

54 if (pnode == &head || pnode->freq != freq - 1) {

55 map[key] = pnode->next = node->prev = new Node(freq - 1, pnode, node, {key});

56 } else {

57 pnode->keys.insert(key);

58 map[key] = pnode;

59 }

60 }

61

62 if (node->keys.empty()) {

63 removeNode(node);

64 }

65 }

66

67 string getMaxKey() const { return tail.prev == &head ? "" : *(tail.prev->keys.begin()); }

68

69 string getMinKey() const { return head.next == &tail ? "" : *(head.next->keys.begin()); }

70

71 private:

72 void removeNode(Node *node) {

73 Node *pnode = node->prev;

74 Node *nnode = node->next;

75

76 pnode->next = nnode;

77 nnode->prev = pnode;

78

79 delete node;

80 }

81 };