432. All O`one Data Structure
请实作一个资料结构
包含以下功能
AllOne() : 初始化资料结构
inc(string key) : 将key的次数+1，如果本来没有key就将其插入
dec(string key) : 将key的次数-1，如果次数变为0就把key移除
getMaxKey() : 回传最大次数的key，如果有多个则会传任一个，若没有任何key回传-1
getMinKey() : 回传最小次数的key，如果有多个则回传任一个，若没有任何key回传-1
以上操作都要在O(1)时间复杂度内
思路:
用双向链结串行，该链结串行的value是目前出现字串的次数
且由小排到大
假设出现过的字串有
EX : A、A、A、A、B、B、B、B、C、C、D
则链结串行会是 1<->2<->4
建立3个hash table
table1 = map[字串]出现次数
table2 = map[次数]双向链结串行的node
table3 = map[次数]map[字串][是否存在]
要回传最小时，就去找双向链结串行的head，看次数是多少，接着随便回传一个相同次数的字串
要回传最大时，就去找双向链结串行的tail
就按照题目去维护双向链结串行和3个hash table
就可以实做出来了
golang code :
type doubly_linknode struct {
val int
prev *doubly_linknode
next *doubly_linknode
}
type AllOne struct {
head *doubly_linknode
tail *doubly_linknode
map_string_cnt map[string]int
map_cnt_linkedlist map[int]*doubly_linknode
map_cnt_string_struct map[int]map[string]struct{}
}
func Constructor() AllOne {
res := AllOne{}
res.map_cnt_linkedlist = make(map[int]*doubly_linknode)
res.map_cnt_string_struct = make(map[int]map[string]struct{})
res.map_string_cnt = make(map[string]int)
res.head = &doubly_linknode{-1, nil, nil}
res.tail = &doubly_linknode{math.MaxInt32, res.head, nil}
res.head.next = res.tail
res.map_cnt_string_struct[-1] = make(map[string]struct{})
res.map_cnt_string_struct[-1][""] = struct{}{}
res.map_cnt_string_struct[math.MaxInt32] = make(map[string]struct{})
res.map_cnt_string_struct[math.MaxInt32][""] = struct{}{}
return res
}
func (this *AllOne) Inc(key string) {
if _, ok := this.map_string_cnt[key]; !ok {
if _, ok1 := this.map_cnt_linkedlist[1]; !ok1 {
newnode := &doubly_linknode{1, nil, nil}
newnode.prev = this.head
newnode.next = this.head.next
this.head.next = newnode
newnode.next.prev = newnode
this.map_cnt_linkedlist[1] = newnode
}
this.map_string_cnt[key] = 1
if _, ok2 := this.map_cnt_string_struct[1]; !ok2 {
this.map_cnt_string_struct[1] = make(map[string]struct{})
}
this.map_cnt_string_struct[1][key] = struct{}{}
} else {
old_idx := this.map_string_cnt[key]
this.map_string_cnt[key]++
new_idx := this.map_string_cnt[key]
prev_node := this.map_cnt_linkedlist[old_idx].prev
next_node := this.map_cnt_linkedlist[old_idx].next
if len(this.map_cnt_string_struct[old_idx]) == 1 {
delete(this.map_cnt_string_struct, old_idx)
prev_node.next = next_node
next_node.prev = prev_node
delete(this.map_cnt_linkedlist, old_idx)
} else {
delete(this.map_cnt_string_struct[old_idx], key)
}
if _, ok1 := this.map_cnt_string_struct[new_idx]; !ok1 {
newnode := &doubly_linknode{new_idx, nil, nil}
this.map_cnt_linkedlist[new_idx] = newnode
if _, exist := this.map_cnt_linkedlist[old_idx]; !exist {
newnode.next = next_node
next_node.prev = newnode
newnode.prev = prev_node
prev_node.next = newnode
} else {
newnode.next = next_node
next_node.prev = newnode
newnode.prev = this.map_cnt_linkedlist[old_idx]
this.map_cnt_linkedlist[old_idx].next = newnode
}
}
if _, ok2 := this.map_cnt_string_struct[new_idx]; !ok2 {
this.map_cnt_string_struct[new_idx] = make(map[string]struct{})
}
this.map_cnt_string_struct[new_idx][key] = struct{}{}
}
}
func (this *AllOne) Dec(key string) {
old_idx := this.map_string_cnt[key]
this.map_string_cnt[key]