溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊(cè)×
其他方式登錄
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶服務(wù)條款》

golang刷leetcode技巧之如何實(shí)現(xiàn)全 O(1) 的數(shù)據(jù)結(jié)構(gòu)

發(fā)布時(shí)間：2021-12-16 09:11:41 來(lái)源：億速云 閱讀：135 作者：小新 欄目：大數(shù)據(jù)

這篇文章主要介紹了golang刷leetcode技巧之如何實(shí)現(xiàn)全 O(1) 的數(shù)據(jù)結(jié)構(gòu)，具有一定借鑒價(jià)值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

請(qǐng)你實(shí)現(xiàn)一個(gè)數(shù)據(jù)結(jié)構(gòu)支持以下操作：

Inc(key) - 插入一個(gè)新的值為 1 的 key。或者使一個(gè)存在的 key 增加一，保證 key 不為空字符串。

Dec(key) - 如果這個(gè) key 的值是 1，那么把他從數(shù)據(jù)結(jié)構(gòu)中移除掉。否則使一個(gè)存在的 key 值減一。如果這個(gè) key 不存在，這個(gè)函數(shù)不做任何事情。key 保證不為空字符串。

GetMaxKey() - 返回 key 中值最大的任意一個(gè)。如果沒(méi)有元素存在，返回一個(gè)空字符串"" 。

GetMinKey() - 返回 key 中值最小的任意一個(gè)。如果沒(méi)有元素存在，返回一個(gè)空字符串""。

挑戰(zhàn)：

你能夠以 O(1) 的時(shí)間復(fù)雜度實(shí)現(xiàn)所有操作嗎？

解題思路

1，這是lru的變體，用hash＋有序雙鏈表的形式

2，每次inc和dec的時(shí)候?qū)?dāng)前節(jié)點(diǎn)從鏈表中去除

3，然后找到合適的位置插入

4，注意，當(dāng)inc后，后面的連續(xù)常數(shù)個(gè)值相等，需要特殊處理

5，dec類(lèi)似

代碼實(shí)現(xiàn)

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(); */

感謝你能夠認(rèn)真閱讀完這篇文章，希望小編分享的“golang刷leetcode技巧之如何實(shí)現(xiàn)全 O(1) 的數(shù)據(jù)結(jié)構(gòu)”這篇文章對(duì)大家有幫助，同時(shí)也希望大家多多支持億速云，關(guān)注億速云行業(yè)資訊頻道，更多相關(guān)知識(shí)等著你來(lái)學(xué)習(xí)!

向AI問(wèn)一下細(xì)節(jié)

免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手