package com.bladewill.webservice.leetcode;
import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.locks.ReentrantLock;
/**
* 实现一个数据结构支持一下操作：
* * Inc(key) - 插入一个新的值为 1 的 key。或者使一个存在的 key 增加一，保证 key 不为空字符串。
* Dec(key) - 如果这个 key 的值是 1，那么把他从数据结构中移除掉。否者使一个存在的 key 值减一。如果这个 key 不存在，这个函数不做任何事情。key 保证不为空字符串。
* GetMaxKey() - 返回 key 中值最大的任意一个。如果没有元素存在，返回一个空字符串""。
* GetMinKey() - 返回 key 中值最小的任意一个。如果没有元素存在，返回一个空字符串""。
*/
public class MyAllOne {//重入锁，确保四个方法的线程安全
ReentrantLock lock = new ReentrantLock();
//存储节点顺序的双向链表
private DoubleLinkedList linkedList = new DoubleLinkedList();
//存储key与节点对应关系的hashap
private Map nodeMap = new HashMap<>();
/**
* 新增inc方法
* 插入一个新的值为 1 的 key。或者使一个存在的 key 增加一，保证 key 不为空字符串。
*
* @param key
*/
public void inc(String key) {
//不存在该key的节点
Node now;
if (!nodeMap.containsKey(key)) {
//则判断链表中是否存在val为1的节点，讲该key赋值给该节点
if (linkedList.head.next.val == 1) {
now = linkedList.head.next;
} else {
//如果链表中不存在val为1的节点，则创建一个新的节点
now = new Node();
linkedList.insertNodeAflterBase(now, linkedList.head);
}
//给nodeMap增加一个
now.val = 1;
now.keyMap.put(key, key);
nodeMap.put(key, now);
} else {
//已存在,调整nodemap的值，调整linkedList中的结构
now = nodeMap.get(key);
//如果下一个节点的val不为now+1，说明下一个节点为尾节点或者有跳层，需要新建节点
if(now.next.val != (now.val + 1)){
Node newNode = new Node();
linkedList.insertNodeBeforeBase(newNode, now.next);
}
now.next.val = now.val + 1;
now.next.keyMap.put(key, key);
now.keyMap.remove(key);
nodeMap.put(key, now.next);
if (now.keyMap.size() == 0) {
linkedList.removeNode(now);
}
}
}/**
* 新增dec方法
* 如果这个 key 的值是 1，那么把他从数据结构中移除掉。否则使一个存在的 key 值减一。如果这个 key 不存在，这个函数不做任何事情。key 保证不为空字符串。
*
* @param key
*/
public void dec(String key) {
if (nodeMap.containsKey(key)) {
//已存在,判断val的值
Node now = nodeMap.get(key);
//如果cal为1，无论如何都从node中清除，是否删除节点同意判断
if (now.val == 1) {
now.keyMap.remove(key);
nodeMap.remove(key);
} else {
//如果上层节点val不为now-1
if (now.pre.val != (now.val - 1)) {
Node newNode = new Node();
linkedList.insertNodeAflterBase(newNode, now.pre);
}
now.pre.val = now.val - 1;
now.pre.keyMap.put(key, key);
now.keyMap.remove(key);
nodeMap.put(key, now.pre);
}
//如果当前节点key为空，则移除节点
if (now.keyMap.size() == 0) {
linkedList.removeNode(now);
}
}
}/**
* GetMaxKey() - 返回 key 中值最大的任意一个。如果没有元素存在，返回一个空字符串""。
*
* @return
*/
public String getMaxKey() {
if (linkedList.tail.pre.val != -1) {
for (String s : linkedList.tail.pre.keyMap.keySet())
return s;
}
return "";
}/**
* GetMinKey() - 返回 key 中值最小的任意一个。如果没有元素存在，返回一个空字符串""。
*
* @return
*/
public String getMinKey() {
if (linkedList.head.next.val != -1) {
for (String s : linkedList.head.next.keyMap.keySet())
return s;
}
return "";
}class Node {
Node next;
Node pre;
int val;
Map keyMap = new HashMap<>();
}class DoubleLinkedList {
Node head, tail;
public DoubleLinkedList() {
head = new Node();
tail = new Node();
head.val = -1;
tail.val = -1;
head.next = tail;
tail.pre = head;
}public void insertNodeBeforeBase(Node now, Node base) {
base.pre.next = now;
now.pre = base.pre;
now.next = base;
base.pre = now;
}public void insertNodeAflterBase(Node now, Node base) {
base.next.pre = now;
now.next = base.next;
base.next = now;
now.pre = base;
}public void removeNode(Node now) {
Node pre = now.pre;
Node next = now.next;
pre.next = next;
next.pre = pre;
now = null;
}
}public static void main(String[] args) {
MyAllOne myAllOne = new MyAllOne();
myAllOne.inc("a");
myAllOne.inc("b");
myAllOne.inc("c");
myAllOne.inc("d");
myAllOne.inc("a");
myAllOne.inc("b");
myAllOne.inc("c");
myAllOne.inc("d");
myAllOne.inc("c");
myAllOne.inc("d");
myAllOne.inc("d");
myAllOne.inc("a");
System.out.println(myAllOne.getMinKey());
}
}
【话不多说，一道面试题，力扣有一个不要求多线程的】
