找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

微信名称:美国米群网

微 信 号:MeetQun

微信QQ:群: 320065698

查看: 273|回复: 3
收起左侧

[刷题记录板] 432. All O`one Data Structure

[复制链接]

23

主题

0

精华

28

积分

新米人

Rank: 1

积分
28
发表于 11-29-2016 05:18 AM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
  1. public class AllOne {
  2.     public class Node{
  3.         Node pre,next;
  4.         int count;
  5.         Set<String> set;
  6.         public Node(int count){
  7.             set= new LinkedHashSet<>();
  8.             this.count=count;
  9.         }
  10.     }
  11.     public void delete(Node node){
  12.         node.pre.next=node.next;
  13.         node.next.pre=node.pre;
  14.     }
  15.     public Node addNode(Node node,int count){   //insert at the node
  16.         Node newnode = new Node(count);
  17.         newnode.next=node.next;
  18.         node.next.pre=newnode;
  19.         node.next=newnode;
  20.         newnode.pre=node;
  21.         return newnode;
  22.     }
  23.    
  24.    

  25.     Node head;
  26.     Node tail;
  27.     Map<String,Node> map;

  28.     /** Initialize your data structure here. */
  29.     public AllOne() {
  30.         head = new Node(0);
  31.         tail = new Node(0);
  32.         head.next=tail;
  33.         tail.pre=head;
  34.         map= new HashMap<>();
  35.     }
  36.    
  37.     /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
  38.     public void inc(String key) {
  39.         if (map.containsKey(key)){
  40.             Node cur = map.get(key);
  41.             Node nextnode = cur.next;
  42.             cur.set.remove(key);
  43.             map.remove(key);
  44.             
  45.             if (nextnode.count != cur.count+1  ){
  46.                 Node newnode = addNode(cur,cur.count+1);
  47.                 newnode.set.add(key);
  48.                 map.put(key,newnode);
  49.             }
  50.             else{
  51.                 nextnode.set.add(key);
  52.                 map.put(key,nextnode);
  53.             }
  54.             
  55.             if (cur.set.size()==0){
  56.                 delete(cur);
  57.             }

  58.         }
  59.         else{
  60.             Node headnext = head.next;
  61.             if (headnext.count==1){
  62.                 headnext.set.add(key);
  63.                 map.put(key,headnext);
  64.             }
  65.             else{
  66.                 Node newnode = addNode(head,1);
  67.                 newnode.set.add(key);
  68.                 map.put(key,newnode);
  69.             }
  70.             
  71.         }
  72.         
  73.     }
  74.    
  75.     /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
  76.     public void dec(String key) {
  77.         Node curnode = map.get(key);
  78.         if (curnode==null) return;
  79.         curnode.set.remove(key);
  80.         map.remove(key);
  81.         
  82.         if (curnode.count!=1){
  83.             Node prenode = curnode.pre;
  84.             if (prenode.count== curnode.count-1){
  85.                 map.put(key,prenode);
  86.                 prenode.set.add(key);
  87.             }
  88.             else{
  89.                 Node newnode = addNode(prenode,curnode.count-1);
  90.                 newnode.set.add(key);
  91.                 map.put(key, newnode);
  92.             }
  93.          
  94.         }
  95.         if (curnode.set.size()==0){
  96.             delete(curnode);
  97.         }         
  98.         
  99.     }
  100.    
  101.     /** Returns one of the keys with maximal value. */
  102.     public String getMaxKey() {
  103.         Node tmp = tail.pre;
  104.         if (tmp==head) return "";
  105.         else{
  106.             return tmp.set.iterator().next();
  107.         }
  108.     }
  109.    
  110.     /** Returns one of the keys with Minimal value. */
  111.     public String getMinKey() {
  112.         Node tmp = head.next;
  113.         if (tmp==tail) return "";
  114.         else{
  115.             return tmp.set.iterator().next();
  116.         }
  117.     }
  118. }
复制代码

0

主题

0

精华

0

积分

新米人

Rank: 1

积分
0
发表于 11-29-2016 05:18 AM 来自美国米群网手机版 | 显示全部楼层
感谢taoqi610分享~~~
回复 支持 反对

使用道具 举报

0

主题

0

精华

1

积分

新米人

Rank: 1

积分
1
发表于 11-30-2016 12:19 AM | 显示全部楼层
感谢taoqi610分享~~~
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表