017.数据结构设计高频题

前置知识：动态数组和扩容分析、【入门】009~012 的 链表入门内容、堆结构、哈希表、有序表和比较器的用法

注意：本节以数据结构设计高频题为主，并不涉及太难的数据结构设计题目

数据结构设计的更难题目，需要学习更多数据结构之后才能解决，如前缀树、并查集、线段树等

后续会更新【必备】、【扩展】、【挺难】视频，包含大量基础和高级数据结构最好懂的原理详解

更多更难的算法、数据结构题目会在“好题解析”系列进行讲解，这个系列将在原理详解系列结束后开始

题目1. setAll 功能的哈希表 §

题目描述 §

setAll：将哈希表所有 key 对应的 value 设置成指定值，但不能遍历，要求所有方法时间复杂度 O(1)

测试链接 §

设计有setAll功能的哈希表

思路 §

加时间戳

答案 §

package main
 
import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)
 
var (
	myMap = NewMyMap()
	n     int
	arr   []string
	key   int
	val   int
)
 
func main() {
	in := bufio.NewScanner(os.Stdin)
	out := bufio.NewWriterSize(os.Stdout, 4096)
	for in.Scan() {
		n, _ = strconv.Atoi(in.Text())
		if n == 0 {
			continue
		}
		myMap.Clear()
		for i := 0; i < n; i++ {
			in.Scan()
			arr = strings.Fields(in.Text())
			key, _ = strconv.Atoi(arr[1])
			switch arr[0] {
			case "1":
				val, _ = strconv.Atoi(arr[2])
				myMap.Set(key, val)
			case "2":
				fmt.Fprintln(out, myMap.Get(key))
			case "3":
				myMap.SetAll(key)
			}
		}
	}
    out.Flush()
}
 
type entry struct {
	time int // 添加时间
	val  int
}
 
type MyMap struct {
	data       map[int]entry
	curTime    int
	setAllTime int // 上一次 setAll 时间
	setAllVal  int // 上一次 setAll 的值
}
 
func NewMyMap() *MyMap {
	return &MyMap{
		data:       map[int]entry{},
		curTime:    0,
		setAllTime: -1, // 没有上一次 setAll
	}
}
 
func (m *MyMap) Set(k, v int) {
	m.data[k] = entry{m.curTime, v}
	m.curTime++
}
 
func (m *MyMap) SetAll(v int) {
	m.setAllTime = m.curTime
	m.curTime++
	m.setAllVal = v
}
 
func (m *MyMap) Get(k int) int {
	if ent, has := m.data[k]; !has {
		return -1
	} else if ent.time < m.setAllTime {
		return m.setAllVal
	} else {
		return ent.val
	}
}
 
func (m *MyMap) Clear() {
	// 牛客 go 版本太低，没有 clear 方法，只能重新建一个了
	// clear(m.data)
	m.data = map[int]entry{}
	m.curTime = 0
	m.setAllTime = -1
}

题目2.实现 LRU 结构 §

LRU 是 Least Recently Used 的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的值（页面）予以淘汰

LRU 缓存

题目3.插入、删除和获取随机元素 O(1) 时间的结构 §

题目描述 §

实现 RandomizedSet 类：

• RandomizedSet()：初始化 RandomizedSet 对象
• bool insert(int val)：当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
• bool remove(int val)：当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。
• int getRandom()：随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。

你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。

测试链接 §

380.O(1) 时间插入、删除和获取随机元素

思路 §

map + slice，删除时拿 slice 中最后一个元素“补洞”

代码 §

type RandomizedSet struct {
	mp  map[int]int // key: val; value: slice 中的索引
	arr []int
}
 
func Constructor() RandomizedSet {
	return RandomizedSet{
		mp:  map[int]int{},
		arr: []int{},
	}
}
 
func (this *RandomizedSet) Insert(val int) bool {
	if _, has := this.mp[val]; !has {
		this.mp[val] = len(this.arr)
		this.arr = append(this.arr, val)
		return true
	}
	return false
}
 
func (this *RandomizedSet) Remove(val int) bool {
	if idx, has := this.mp[val]; has {
		lastIdx := len(this.arr) - 1
		this.mp[this.arr[lastIdx]] = idx
		this.arr[idx] = this.arr[lastIdx]
		delete(this.mp, val)
		this.arr = this.arr[:lastIdx]
		return true
	}
	return false
}
 
func (this *RandomizedSet) GetRandom() int {
	return this.arr[rand.Intn(len(this.arr))]
}
 
/**
 * Your RandomizedSet object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Insert(val);
 * param_2 := obj.Remove(val);
 * param_3 := obj.GetRandom();
 */

题目4.插入、删除和获取随机元素 O(1) 时间且允许有重复数字的结构 §

题目描述 §

同 上题，但可以插入重复数字、删除时只删除一个、返回随机值方法要求每个元素被返回的概率与集合中包含的相同值的数量成 线性相关

测试链接 §

381.O(1) 时间插入、删除和获取随机元素 - 允许重复

代码 §

var (
	emptyStruct = struct{}{}
)
 
type RandomizedCollection struct {
	mp  map[int]map[int]struct{} // key: val; value: slice 索引的集合
	arr []int
}
 
func Constructor() RandomizedCollection {
	return RandomizedCollection{
		mp:  map[int]map[int]struct{}{},
		arr: []int{},
	}
}
 
func (this *RandomizedCollection) Insert(val int) bool {
	idxSet, has := this.mp[val]
	if !has {
		idxSet = map[int]struct{}{}
		this.mp[val] = idxSet
	}
	idxSet[len(this.arr)] = emptyStruct
	this.arr = append(this.arr, val)
	return !has
}
 
func (this *RandomizedCollection) Remove(val int) bool {
	idxSet, has := this.mp[val]
	if has {
		idx := 0
		// 获取 idxSet 的第一个元素
		for key := range idxSet {
			idx = key
			break
		}
		lastIdx := len(this.arr) - 1
		lastVal := this.arr[lastIdx]
		if val == lastVal {
			delete(idxSet, lastIdx)
		} else {
			this.mp[lastVal][idx] = emptyStruct
			this.arr[idx] = lastVal
			delete(this.mp[lastVal], lastIdx)
			delete(idxSet, idx)
		}
		this.arr = this.arr[:lastIdx]
		if len(idxSet) == 0 {
			delete(this.mp, val)
		}
	}
	return has
}
 
func (this *RandomizedCollection) GetRandom() int {
	return this.arr[rand.Intn(len(this.arr))]
}
 
/**
 * Your RandomizedCollection object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Insert(val);
 * param_2 := obj.Remove(val);
 * param_3 := obj.GetRandom();
 */

题目5.快速获得数据流的中位数的结构 §

题目描述 §

中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

• 例如 arr = [2,3,4] 的中位数是 3 。
• 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。

实现 MedianFinder 类:

• MedianFinder() 初始化 MedianFinder 对象。
• void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
• double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 $10^{-5}$ 以内的答案将被接受。

测试链接 §

295.数据流的中位数

思路 §

准备一个大根堆和一个小根堆，将较小一半放到大根堆、较大一半放到小根堆

答案 §

数据流的中位数

题目6.最大频率栈 §

题目描述 §

设计一个类似堆栈的数据结构，将元素推入堆栈，并从堆栈中弹出出现频率最高的元素。

实现 FreqStack 类:

• FreqStack() 构造一个空的堆栈。
• void push(int val) 将一个整数 val 压入栈顶。
• int pop() 删除并返回堆栈中出现频率最高的元素。
  • 如果出现频率最高的元素不只一个，则移除并返回最接近栈顶的元素。

测试链接 §

895.最大频率栈

思路 §

以词频为键创建多个栈，弹出时先从最高词频的栈开始弹出

答案 §

type FreqStack struct {
	topTimes   int           // 出现的最大次数
	stack      map[int][]int // key: 词频, value: 当前词频栈
	valueTimes map[int]int   // 词频表
}
 
func Constructor() FreqStack {
	return FreqStack{
		topTimes:   0,
		stack:      map[int][]int{},
		valueTimes: map[int]int{},
	}
}
 
func (this *FreqStack) Push(val int) {
	this.valueTimes[val]++
	curTimes := this.valueTimes[val]
	this.stack[curTimes] = append(this.stack[curTimes], val)
	if this.topTimes < curTimes {
		this.topTimes = curTimes
	}
}
 
func (this *FreqStack) Pop() int {
	topTimesVals := this.stack[this.topTimes]
	lastIdx := len(topTimesVals) - 1
	ans := topTimesVals[lastIdx]
	this.stack[this.topTimes] = topTimesVals[:lastIdx]
	if len(this.stack[this.topTimes]) == 0 {
		delete(this.stack, this.topTimes)
		this.topTimes--
	}
	this.valueTimes[ans]--
	if this.valueTimes[ans] == 0 {
		delete(this.valueTimes, ans)
	}
	return ans
}
 
/**
 * Your FreqStack object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(val);
 * param_2 := obj.Pop();
 */

题目7.全 O(1) 的数据结构 §

题目描述 §

请你设计一个用于存储字符串计数的数据结构，并能够返回计数最小和最大的字符串。

实现 AllOne 类：

• AllOne() 初始化数据结构的对象。
• inc(String key) 字符串 key 的计数增加 1 。如果数据结构中尚不存在 key ，那么插入计数为 1 的 key 。
• dec(String key) 字符串 key 的计数减少 1 。如果 key 的计数在减少后为 0 ，那么需要将这个 key 从数据结构中删除。测试用例保证：在减少计数前，key 存在于数据结构中。
• getMaxKey() 返回任意一个计数最大的字符串。如果没有元素存在，返回一个空字符串 "" 。
• getMinKey() 返回任意一个计数最小的字符串。如果没有元素存在，返回一个空字符串 "" 。

注意：每个函数都应当满足 O(1) 平均时间复杂度。

测试链接 §

432.全 O(1) 的数据结构

思路 §

双向链表（词频桶）+ map（词在哪个桶里）

答案 §

var (
	emptyStruct = struct{}{}
)
 
// 双向链表储存的结构
type bucket struct {
	times int                 // 词频
	words map[string]struct{} // 词
}
 
type AllOne struct {
	mp map[string]*list.Element // 词在哪个桶里
	l  list.List                // 词频桶
}
 
func Constructor() AllOne {
	return AllOne{
		mp: map[string]*list.Element{},
		l:  list.List{},
	}
}
 
func (this *AllOne) Inc(key string) {
	val, has := this.mp[key]
	if !has {
		if this.l.Len() == 0 || this.l.Front().Value.(bucket).times != 1 {
			this.l.PushFront(bucket{1, map[string]struct{}{}})
		}
		this.mp[key] = this.l.Front()
		this.l.Front().Value.(bucket).words[key] = emptyStruct
	} else {
		curBkt := val.Value.(bucket)
		var nextBkt bucket
		if val.Next() != nil && val.Next().Value.(bucket).times == curBkt.times+1 {
			nextBkt = val.Next().Value.(bucket)
		} else {
			nextBkt = bucket{curBkt.times + 1, map[string]struct{}{}}
			this.l.InsertAfter(nextBkt, val)
		}
		nextBkt.words[key] = emptyStruct
		this.mp[key] = val.Next()
		if len(curBkt.words) == 1 {
			this.l.Remove(val)
		} else {
			delete(curBkt.words, key)
		}
	}
}
 
func (this *AllOne) Dec(key string) {
	val, has := this.mp[key]
	if !has {
		return
	}
	curBkt := val.Value.(bucket)
	if curBkt.times-1 == 0 {
		if len(curBkt.words) == 1 {
			this.l.Remove(val)
		} else {
			delete(curBkt.words, key)
		}
		delete(this.mp, key)
		return
	}
 
	var prevBkt bucket
	if val.Prev() != nil && val.Prev().Value.(bucket).times == curBkt.times-1 {
		prevBkt = val.Prev().Value.(bucket)
	} else {
		prevBkt = bucket{curBkt.times - 1, map[string]struct{}{}}
		this.l.InsertBefore(prevBkt, val)
	}
	prevBkt.words[key] = emptyStruct
	this.mp[key] = val.Prev()
	if len(curBkt.words) == 1 {
		this.l.Remove(val)
	} else {
		delete(curBkt.words, key)
	}
}
 
func (this *AllOne) GetMaxKey() string {
	if this.l.Len() > 0 {
		for key := range this.l.Back().Value.(bucket).words {
			return key
		}
	}
	return ""
}
 
func (this *AllOne) GetMinKey() string {
	if this.l.Len() > 0 {
		for key := range this.l.Front().Value.(bucket).words {
			return key
		}
	}
	return ""
}
 
/**
 * 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();
 */

吐槽：Go 不用泛型，写的是真繁琐