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]-- var new_idx int if this.map_string_cnt[key] == 0 { delete(this.map_string_cnt, key) new_idx = -1 } else { 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 = this.map_cnt_linkedlist[old_idx] this.map_cnt_linkedlist[old_idx].prev = newnode newnode.prev = prev_node prev_node.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) GetMaxKey() string { idx := this.tail.prev.val for key, _ := range this.map_cnt_string_struct[idx] { return key } return "" } func (this *AllOne) GetMinKey() string { idx := this.head.next.val for key, _ := range this.map_cnt_string_struct[idx] { return key } return "" } -- ※ 發信站: 批踢踢實業坊(ptt.org.tw), 來自: 42.72.18.46 (臺灣) ※ 文章網址: https://ptt.org.tw/Marginalman/M.1727621045.A.22F

→ JenniferLope: 大師 09/29 22:44

→ JIWP: 有夠長 09/29 22:45