这篇文章主要介绍了golang刷leetcode技巧之如何实现全 O(1) 的数据结构，具有一定借鉴价值，感兴趣的朋友可以参考下，希望大家阅读完这篇文章之后大有收获，下面让小编带着大家一起了解一下。
请你实现一个数据结构支持以下操作：
Inc(key) - 插入一个新的值为 1 的 key。或者使一个存在的 key 增加一，保证 key 不为空字符串。
Dec(key) - 如果这个 key 的值是 1，那么把他从数据结构中移除掉。否则使一个存在的 key 值减一。如果这个 key 不存在，这个函数不做任何事情。key 保证不为空字符串。
GetMaxKey() - 返回 key 中值最大的任意一个。如果没有元素存在，返回一个空字符串"" 。
GetMinKey() - 返回 key 中值最小的任意一个。如果没有元素存在，返回一个空字符串""。
挑战：
你能够以 O(1) 的时间复杂度实现所有操作吗？
解题思路
1，这是lru的变体，用hash＋有序双链表的形式
2，每次inc和dec的时候将当前节点从链表中去除
3，然后找到合适的位置插入
4，注意，当inc后，后面的连续常数个值相等，需要特殊处理
5，dec类似
代码实现
计算
安全
数据库
网络和加速
企业服务
type Node struct{ next *Node prev *Node val int key string}type AllOne struct { head *Node tail *Node m map[string]*Node}/** Initialize your data structure here. */func Constructor() AllOne { ao:=AllOne{ head:&Node{}, tail:&Node{}, m:make(map[string]*Node), } ao.head.next=ao.tail ao.tail.prev=ao.head return ao}/** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */func (this *AllOne) Inc(key string) { if n,ok:=this.m[key];ok{ this.m[key].val++ next:=n.next if next==this.tail || next.val>=n.val{ return }else{ next.prev=n.prev n.prev.next=next for next.next!=this.tail && next.next.val<n.val{ next=next.next } n.next=next.next n.prev=next next.next.prev=n next.next=n } }else{ n:=&Node{ val:1, key:key, prev:this.head, next:this.head.next, } this.head.next.prev=n this.head.next=n this.m[key]=n } this.Print()}func(this*AllOne)Print(){ for n:=this.head.next ;n!=this.tail;n=n.next{ println(n.val) }}/** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */func (this *AllOne) Dec(key string) { if _,ok:=this.m[key];!ok { return } n:= this.m[key] if this.m[key].val>1{ n.val-- if n.prev==this.head || n.prev.val<=n.val{ return }else { prev:=n.prev prev.next=n.next n.next.prev=prev for prev.prev!=this.head && prev.prev.val>n.val{ prev=prev.prev } n.prev=prev.prev n.next=prev prev.prev.next=n prev.prev=n } }else{ n.prev.next=n.next n.next.prev=n.prev delete(this.m,key) } this.Print() }/** Returns one of the keys with maximal value. */func (this *AllOne) GetMaxKey() string { if this.head.next==this.tail{ return "" } return this.tail.prev.key}/** Returns one of the keys with Minimal value. */func (this *AllOne) GetMinKey() string { if this.head.next==this.tail{ return "" } return this.head.next.key}/** * Your AllOne object will be instantiated and called as such: * obj := Constructor(); * obj.Inc(key); * obj.Dec(key); * param_3 := obj.GetMaxKey(); * param_4 := obj.GetMinKey(); */感谢你能够认真阅读完这篇文章，希望小编分享的“golang刷leetcode技巧之如何实现全 O(1) 的数据结构”这篇文章对大家有帮助，同时也希望大家多多支持亿速云，关注亿速云行业资讯频道，更多相关知识等着你来学习!
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
原文链接：https://my.oschina.net/u/4586289/blog/4404126
