这篇文章主要介绍了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 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 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) 的数据结构”这篇文章对大家有帮助，同时也希望大家多多支持创新互联，关注创新互联行业资讯频道，更多相关知识等着你来学习!
文章名称：golang刷leetcode技巧之如何实现全O(1)的数据结构
文章起源：
http://chengdu.cdxwcx.cn/article/poicjh.html
