溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要介紹了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 *Nodeprev *Nodeval intkey string}type AllOne struct {head *Nodetail *Nodem 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.tailao.tail.prev=ao.headreturn 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.nextif next==this.tail || next.val>=n.val{return}else{next.prev=n.prevn.prev.next=nextfor next.next!=this.tail && next.next.val<n.val{next=next.next}n.next=next.nextn.prev=nextnext.next.prev=nnext.next=n}}else{n:=&Node{val:1,key:key,prev:this.head,next:this.head.next,}this.head.next.prev=nthis.head.next=nthis.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.prevprev.next=n.nextn.next.prev=prevfor prev.prev!=this.head && prev.prev.val>n.val{prev=prev.prev}n.prev=prev.prevn.next=prevprev.prev.next=nprev.prev=n}}else{n.prev.next=n.nextn.next.prev=n.prevdelete(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) 的數據結構”這篇文章對大家有幫助，同時也希望大家多多支持億速云，關注億速云行業資訊頻道，更多相關知識等著你來學習!
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
