All O`one Data Structure
class AllOne {
private Map<String,Node> map;
private DoubleLinkedList ddl;
/** Initialize your data structure here. */
public AllOne() {
map = new HashMap<>();
ddl = new DoubleLinkedList();
}
/** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
public void inc(String key) {
System.out.println("inc");
if(key == null || key.length() == 0)
return;
Node node = null;
if(!map.containsKey(key)){
//check ddl 中是否包含key
if(ddl.head.next.val == 1){
node = ddl.head.next;
node.addString(key);
}else{
node = new Node(1);
ddl.addAfterHead(node);
node.addString(key);
}
map.put(key,node);
}
else{
node = map.get(key);
map.put(key,ddl.update(node,key));
}
//ddl.dump();
ddl.printNode();
}
/** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
public void dec(String key) {
System.out.println("dec");
if(key == null || key.length() == 0)
return;
if(map.containsKey(key)){
Node node = map.get(key);
int val = node.val;
Node newNode = ddl.decUpdate(node,key);
if(val == 1){
map.remove(key);
}
else{
map.put(key,newNode);
}
}
//ddl.dump();
ddl.printNode();
}
/** Returns one of the keys with maximal value. */
public String getMaxKey() {
return ddl.getMax();
}
/** Returns one of the keys with Minimal value. */
public String getMinKey(){
return ddl.getMin();
}
class DoubleLinkedList{
private Node head;
private Node tail;
public DoubleLinkedList(){
this.head = new Node(-1);
this.tail = new Node(-1);
head.next = tail;
head.prev = null;
tail.next = null;
tail.prev = head;
}
public void dump(){
Node tmp = head.next;
while(tmp != tail && tmp != null){
System.out.print(tmp.val+" : ");
for(String s : tmp.getList()){
System.out.print(s + " ");
}
System.out.println();
tmp = tmp.next;
}
}
public void printNode(){
Node tmp = head;
while(tmp != null){
System.out.print(tmp.val+" -> ");
tmp = tmp.next;
}
}
public Node decUpdate(Node node, String s){
int curVal = node.val;
if(curVal == 1){
node.removeString(s);
if(node.isEmpty()){
remove(node);
return head;
}
return node;
}
else{
if(node.prev.val == curVal - 1){
Node prevNode = node.prev;
prevNode.addString(s);
node.removeString(s);
if(node.isEmpty()){
System.out.println("this node is empty, ready to remove");
remove(node);
}
return prevNode;
}
Node newNode = new Node(curVal - 1);
newNode.next = node;
newNode.prev = node.prev;
node.prev.next = newNode;
node.prev = newNode;
newNode.addString(s);
node.removeString(s);
if(node.isEmpty()){
remove(node);
}
return newNode;
}
}
public void addAfterHead(Node node){
node.next = head.next;
node.prev = head;
head.next.prev = node;
head.next = node;
}
public void remove(Node node){
node.prev.next = node.next;
node.next.prev = node.prev;
node.next = null;
node.prev = null;
}
public Node update(Node node,String s){
int curVal = node.val;
if(node.next.val == curVal + 1){
node.removeString(s);
node.next.addString(s);
if(node.isEmpty()){
remove(node);
return null;
}
}else{
Node newNode = new Node(curVal+1);
newNode.addString(s);
node.removeString(s);
newNode.next = node.next;
newNode.prev = node;
node.next.prev = newNode;
node.next = newNode;
if(node.isEmpty()){
remove(node);
return newNode;
}
}
return node.next;
}
public String getMax(){
if(tail.prev == head){
return "";
}
List<String> list = tail.prev.getList();
int size = tail.prev.listSize();
return list.isEmpty() ? "": list.get(size -1);
}
public String getMin(){
if(head.next == tail){
return "";
}
List<String> list = head.next.getList();
int size = head.next.listSize();
return list.isEmpty() ? "": list.get(size -1);
}
}
class Node{
public int val;
// store keys with same value
public List<String> list;
//store keys and it's index mapping
public Map<String, Integer> map;
//connect next and previous node
public Node next;
public Node prev;
public Node(int val){
this.val = val;
list = new ArrayList<>();
map = new HashMap<>();
next = null;
prev = null;
}
public void addString(String s){
list.add(s);
map.put(s,list.size()-1);
}
public boolean removeString(String s){
if(!map.containsKey(s)){
return false;
}
int indexOfS = map.get(s);
if(indexOfS != list.size()-1){
String last = list.get(list.size()-1);
list.set(indexOfS,last);
map.put(last,indexOfS);
}
map.remove(s);
list.remove(list.size()-1);
return true;
}
public boolean isEmpty(){
return list.isEmpty();
}
public int listSize(){
return list.size();
}
public List<String> getList(){
return list;
}
}
}
/**
* Your AllOne object will be instantiated and called as such:
* AllOne obj = new AllOne();
* obj.inc(key);
* obj.dec(key);
* String param_3 = obj.getMaxKey();
* String param_4 = obj.getMinKey();
*/Last updated