题目

类型：设计

image.png

解题思路

自定义节点并手写双链表来实现
https://leetcode-cn.com/problems/all-oone-data-structure/solution/by-ac_oier-t26d/

代码

  1. class AllOne {
  2.     class Node {
  3.         int cnt;
  4.         Set<String> set = new HashSet<>();
  5.         Node left, right;
  6.         Node(int _cnt) {
  7.             cnt = _cnt;
  8.         }
  9.     }
  11.     Node hh, tt;
  12.     Map<String, Node> map = new HashMap<>();
  13.     public AllOne() {
  14.         hh = new Node(-1000); tt = new Node(-1000);
  15.         hh.right = tt; tt.left = hh;
  16.     }
  18.     void clear(Node node) {
  19.         if (node.set.size() == 0) {
  20.             node.left.right = node.right;
  21.             node.right.left = node.left;
  22.         }
  23.     }
  25.     public void inc(String key) {
  26.         if (map.containsKey(key)) {
  27.             Node node = map.get(key);
  28.             node.set.remove(key);
  29.             int cnt = node.cnt;
  30.             Node next = null;
  31.             if (node.right.cnt == cnt + 1) {
  32.                 next = node.right;
  33.             } else {
  34.                 next = new Node(cnt + 1);
  35.                 next.right = node.right;
  36.                 next.left = node;
  37.                 node.right.left = next;
  38.                 node.right = next;
  39.             }
  40.             next.set.add(key);
  41.             map.put(key, next);
  42.             clear(node);
  43.         } else {
  44.             Node node = null;
  45.             if (hh.right.cnt == 1) {
  46.                 node = hh.right;
  47.             } else {
  48.                 node = new Node(1);
  49.                 node.right = hh.right;
  50.                 node.left = hh;
  51.                 hh.right.left = node;
  52.                 hh.right = node;
  53.             }
  54.             node.set.add(key);
  55.             map.put(key, node);
  56.         }
  57.     }
  59.     public void dec(String key) {
  60.         Node node = map.get(key);
  61.         node.set.remove(key);
  62.         int cnt = node.cnt;
  63.         if (cnt == 1) {
  64.             map.remove(key);
  65.         } else {
  66.             Node prev = null;
  67.             if (node.left.cnt == cnt - 1) {
  68.                 prev = node.left;
  69.             } else {
  70.                 prev = new Node(cnt - 1);
  71.                 prev.right = node;
  72.                 prev.left = node.left;
  73.                 node.left.right = prev;
  74.                 node.left = prev;
  75.             }
  76.             prev.set.add(key);
  77.             map.put(key, prev);
  78.         }
  79.         clear(node);
  80.     }
  82.     public String getMaxKey() {
  83.         Node node = tt.left;
  84.         for (String str : node.set) return str;
  85.         return "";
  86.     }
  88.     public String getMinKey() {
  89.         Node node = hh.right;
  90.         for (String str : node.set) return str;
  91.         return "";
  92.     }
  93. }
  95. /**
  96.  * Your AllOne object will be instantiated and called as such:
  97.  * AllOne obj = new AllOne();
  98.  * obj.inc(key);
  99.  * obj.dec(key);
  100.  * String param_3 = obj.getMaxKey();
  101.  * String param_4 = obj.getMinKey();
  102.  */