做设计做网站/淘宝数据分析

学习地址

双向链表

key为count数，value为存入的字符串
增加一个字符串，先判断其Node位置，再在双向链表中插入
删除也是
最大最小的字符串数在双向链表的表尾和表头

记录学习一下

class AllOne {Node root;Map<String, Node> nodes;public AllOne() {root = new Node();root.prev = root;root.next = root;  // 初始化链表哨兵，下面判断节点的 next 若为 root，则表示 next 为空（prev 同理）nodes = new HashMap<String, Node>();}public void inc(String key) {if (nodes.containsKey(key)) {Node cur = nodes.get(key);Node nxt = cur.next;if (nxt == root || nxt.count > cur.count + 1) {nodes.put(key, cur.insert(new Node(key, cur.count + 1)));} else {nxt.keys.add(key);nodes.put(key, nxt);}cur.keys.remove(key);if (cur.keys.isEmpty()) {cur.remove();}} else {  // key 不在链表中if (root.next == root || root.next.count > 1) {nodes.put(key, root.insert(new Node(key, 1)));} else {root.next.keys.add(key);nodes.put(key, root.next);}}}public void dec(String key) {Node cur = nodes.get(key);if (cur.count == 1) {  // key 仅出现一次，将其移出 nodesnodes.remove(key);} else {Node pre = cur.prev;if (pre == root || pre.count < cur.count - 1) {nodes.put(key, cur.prev.insert(new Node(key, cur.count - 1)));} else {pre.keys.add(key);nodes.put(key, pre);}}cur.keys.remove(key);if (cur.keys.isEmpty()) {cur.remove();}}public String getMaxKey() {return root.prev != null ? root.prev.keys.iterator().next() : "";}public String getMinKey() {return root.next != null ? root.next.keys.iterator().next() : "";}
}class Node {Node prev;Node next;Set<String> keys;int count;public Node() {this("", 0);}public Node(String key, int count) {this.count = count;keys = new HashSet<String>();keys.add(key);}public Node insert(Node node) {  // 在 this 后插入 nodenode.prev = this;node.next = this.next;node.prev.next = node;node.next.prev = node;return node;}public void remove() {this.prev.next = this.next;this.next.prev = this.prev;}
}