LeetCode Go · 数据结构设计（3）

来源与许可

题目版权归 LeetCode；题解来自 Doocs/leetcode，按 CC BY-SA 4.0 共享。补充 Go 代码来自灵茶山艾府、halfrost，保留 MIT 许可及逐题署名。本站提取 Go、调整分类及折叠排版；标注“本站整理”的 Go 解法依据题意与参考思路补写，按 CC BY-SA 4.0 共享。收录日期：2026-10-31；主题源版本：91ef8c241a5e。

本卷 30 题 · 点击题目展开，先独立思考，再查看解法。

911. 在线选举

中等1 种解法

标签：设计、数组、哈希表、二分查找

题目、示例与约束

给你两个整数数组 persons 和 times 。在选举中，第 i 张票是在时刻为 times[i] 时投给候选人 persons[i] 的。

对于发生在时刻 t 的每个查询，需要找出在 t 时刻在选举中领先的候选人的编号。

在 t 时刻投出的选票也将被计入我们的查询之中。在平局的情况下，最近获得投票的候选人将会获胜。

实现 TopVotedCandidate 类：

TopVotedCandidate(int[] persons, int[] times) 使用 persons 和 times 数组初始化对象。
int q(int t) 根据前面描述的规则，返回在时刻 t 在选举中领先的候选人的编号。

示例：

输入：
["TopVotedCandidate", "q", "q", "q", "q", "q", "q"]
[[[0, 1, 1, 0, 0, 1, 0], [0, 5, 10, 15, 20, 25, 30]], [3], [12], [25], [15], [24], [8]]
输出：
[null, 0, 1, 1, 0, 0, 1]

解释：
TopVotedCandidate topVotedCandidate = new TopVotedCandidate([0, 1, 1, 0, 0, 1, 0], [0, 5, 10, 15, 20, 25, 30]);
topVotedCandidate.q(3); // 返回 0 ，在时刻 3 ，票数分布为 [0] ，编号为 0 的候选人领先。
topVotedCandidate.q(12); // 返回 1 ，在时刻 12 ，票数分布为 [0,1,1] ，编号为 1 的候选人领先。
topVotedCandidate.q(25); // 返回 1 ，在时刻 25 ，票数分布为 [0,1,1,0,0,1] ，编号为 1 的候选人领先。（在平局的情况下，1 是最近获得投票的候选人）。
topVotedCandidate.q(15); // 返回 0
topVotedCandidate.q(24); // 返回 0
topVotedCandidate.q(8); // 返回 1

提示：

1 <= persons.length <= 5000
times.length == persons.length
0 <= persons[i] < persons.length
0 <= times[i] <= 10⁹
times 是一个严格递增的有序数组
times[0] <= t <= 10⁹
每个测试用例最多调用 10⁴ 次 q

方法一：二分查找 · Go 实现

思考

查询时刻 $t$ 的领先者，票数随投票变化。每次从前往后扫到 $t$ 为线性，查询次数较多时偏慢。 $t i m e s$ 严格递增，可预处理每个投票时刻的胜者：平票时取最近投票人。

查询时二分找到 $\leq t$ 的最后一次投票，直接返回该时刻记录的胜者。

我们可以在初始化时，记录每个时刻的胜者，然后在查询时，使用二分查找找到小于等于 $t$ 的最大时刻，返回该时刻的胜者。

初始化时，我们使用一个计数器 $c n t$ 记录每个候选人的票数，用一个变量 $c u r$ 记录当前领先的候选人。然后遍历每个时刻，更新 $c n t$ 和 $c u r$ ，并记录每个时刻的胜者。

查询时，我们使用二分查找找到小于等于 $t$ 的最大时刻，返回该时刻的胜者。

时间复杂度方面，初始化时，我们需要 $O (n)$ 的时间，查询时，我们需要 $O (\log n)$ 的时间。空间复杂度为 $O (n)$ 。

type TopVotedCandidate struct {
	times []int
	wins  []int
}

func Constructor(persons []int, times []int) TopVotedCandidate {
	n := len(persons)
	wins := make([]int, n)
	cnt := make([]int, n)
	cur := 0
	for i, p := range persons {
		cnt[p]++
		if cnt[cur] <= cnt[p] {
			cur = p
		}
		wins[i] = cur
	}
	return TopVotedCandidate{times, wins}
}

func (this *TopVotedCandidate) Q(t int) int {
	i := sort.SearchInts(this.times, t+1) - 1
	return this.wins[i]
}

/**
 * Your TopVotedCandidate object will be instantiated and called as such:
 * obj := Constructor(persons, times);
 * param_1 := obj.Q(t);
 */

力扣原题 · Doocs 题解来源

919. 完全二叉树插入器

中等1 种解法

标签：树、广度优先搜索、设计、二叉树

题目、示例与约束

完全二叉树 是每一层（除最后一层外）都是完全填充（即，节点数达到最大）的，并且所有的节点都尽可能地集中在左侧。

设计一种算法，将一个新节点插入到一棵完全二叉树中，并在插入后保持其完整。

实现 CBTInserter 类:

CBTInserter(TreeNode root) 使用头节点为 root 的给定树初始化该数据结构；
CBTInserter.insert(int v) 向树中插入一个值为 Node.val == val的新节点 TreeNode。使树保持完全二叉树的状态，并返回插入节点 TreeNode 的父节点的值；
CBTInserter.get_root() 将返回树的头节点。

示例 1：

输入
["CBTInserter", "insert", "insert", "get_root"]
[[[1, 2]], [3], [4], []]
输出
[null, 1, 2, [1, 2, 3, 4]]

解释
CBTInserter cBTInserter = new CBTInserter([1, 2]);
cBTInserter.insert(3);  // 返回 1
cBTInserter.insert(4);  // 返回 2
cBTInserter.get_root(); // 返回 [1, 2, 3, 4]

提示：

树中节点数量范围为 [1, 1000]
0 <= Node.val <= 5000
root 是完全二叉树
0 <= val <= 5000
每个测试用例最多调用 insert 和 get_root 操作 10⁴ 次

方法一：BFS · Go 实现

思考

完全二叉树插入总是填最左空位。每次从根层序寻找空位，插入次数较多时会重复遍历已满的节点。层序把节点存进数组后，下标满足堆性质：新节点的父节点在 $(s z - 1) / / 2$ ，插入与取根均为常数时间。

我们可以使用一个数组 $t r e e$ 来存储完全二叉树的所有节点。在初始化时，我们使用一个队列 $q$ 来层序遍历给定的树，并将所有节点存储到数组 $t r e e$ 中。

在插入节点时，我们可以通过数组 $t r e e$ 来找到新节点的父节点 $p$ 。然后我们创建一个新节点 $n o d e$ ，将其插入到数组 $t r e e$ 中，并将 $n o d e$ 作为 $p$ 的左子节点或右子节点。最后返回 $p$ 的值。

在获取根节点时，我们直接返回数组 $t r e e$ 的第一个元素。

时间复杂度方面，初始化时需要 $O (n)$ 的时间，插入节点和获取根节点的时间复杂度均为 $O (1)$ 。空间复杂度为 $O (n)$ 。其中 $n$ 为树中节点的数量。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
type CBTInserter struct {
	tree []*TreeNode
}

func Constructor(root *TreeNode) CBTInserter {
	q := []*TreeNode{root}
	tree := []*TreeNode{}
	for len(q) > 0 {
		for i := len(q); i > 0; i-- {
			node := q[0]
			q = q[1:]
			tree = append(tree, node)
			if node.Left != nil {
				q = append(q, node.Left)
			}
			if node.Right != nil {
				q = append(q, node.Right)
			}
		}
	}
	return CBTInserter{tree}
}

func (this *CBTInserter) Insert(val int) int {
	p := this.tree[(len(this.tree)-1)/2]
	node := &TreeNode{val, nil, nil}
	this.tree = append(this.tree, node)
	if p.Left == nil {
		p.Left = node
	} else {
		p.Right = node
	}
	return p.Val
}

func (this *CBTInserter) Get_root() *TreeNode {
	return this.tree[0]
}

/**
 * Your CBTInserter object will be instantiated and called as such:
 * obj := Constructor(root);
 * param_1 := obj.Insert(val);
 * param_2 := obj.Get_root();
 */

力扣原题 · Doocs 题解来源

933. 最近的请求次数

简单2 种解法

标签：设计、队列、数据流

题目、示例与约束

写一个 RecentCounter 类来计算特定时间范围内最近的请求。

请你实现 RecentCounter 类：

RecentCounter() 初始化计数器，请求数为 0 。
int ping(int t) 在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，然后返回在包含范围 [t - 3000, t] 内发生的请求数量，即新请求加上所有早于或等于 3000 毫秒前的请求。

保证每次对 ping 的调用都使用比之前更大的 t 值。

示例 1：

输入：
["RecentCounter", "ping", "ping", "ping", "ping"]
[[], [1], [100], [3001], [3002]]
输出：
[null, 1, 2, 3, 3]

解释：
RecentCounter recentCounter = new RecentCounter();
recentCounter.ping(1);     // requests = [1]，范围是 [-2999,1]，返回 1
recentCounter.ping(100);   // requests = [1, 100]，范围是 [-2900,100]，返回 2
recentCounter.ping(3001);  // requests = [1, 100, 3001]，范围是 [1,3001]，返回 3
recentCounter.ping(3002);  // requests = [1, 100, 3001, 3002]，范围是 [2,3002]，返回 3

提示：

1 <= t <= 10⁹
保证每次对 ping 调用所使用的 t 值都 严格递增
至多调用 ping 方法 10⁴ 次

方法一：队列 · Go 实现

思考

$t$ 严格递增，过期请求（小于 $t - 3000$ ）以后也不会再回来。用队列存请求时间，队头过期则弹出，队的大小即窗口内次数。

由题得知，t 是严格递增的，当一个元素不满足 [t - 3000, t] 条件时，在后续的请求当中，它也不可能满足。

对此，需要将其从记录容器中移除，减少无意义的比较。

可以使用队列。每次将 t 进入队尾，同时从队头开始，依次移除小于 t - 3000 的元素。然后返回队列的大小（q.size()）即可。

type RecentCounter struct {
	q []int
}

func Constructor() RecentCounter {
	return RecentCounter{[]int{}}
}

func (this *RecentCounter) Ping(t int) int {
	this.q = append(this.q, t)
	for this.q[0] < t-3000 {
		this.q = this.q[1:]
	}
	return len(this.q)
}

/**
 * Your RecentCounter object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Ping(t);
 */

方法二：二分查找 · Go 实现

思考

队列均摊线性，若希望按历史数组查询，因 $t$ 有序，二分定位 $t - 3000$ 的左端，答案为后缀长度。空间仍线性，单次查询多一次对数。

t 严格单调递增，非常适合用二分查找来定位 [t-3000, t] 的左右边界。

type RecentCounter struct {
	s []int
}

func Constructor() RecentCounter {
	return RecentCounter{[]int{}}
}

func (this *RecentCounter) Ping(t int) int {
	this.s = append(this.s, t)
	search := func(x int) int {
		left, right := 0, len(this.s)
		for left < right {
			mid := (left + right) >> 1
			if this.s[mid] >= x {
				right = mid
			} else {
				left = mid + 1
			}
		}
		return left
	}
	return len(this.s) - search(t-3000)
}

/**
 * Your RecentCounter object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Ping(t);
 */

力扣原题 · Doocs 题解来源

981. 基于时间的键值存储

中等1 种解法

标签：设计、哈希表、字符串、二分查找

题目、示例与约束

设计一个基于时间的键值数据结构，该结构可以在不同时间戳存储对应同一个键的多个值，并针对特定时间戳检索键对应的值。

实现 TimeMap 类：

TimeMap() 初始化数据结构对象
void set(String key, String value, int timestamp) 存储给定时间戳 timestamp 时的键 key 和值 value。
String get(String key, int timestamp) 返回一个值，该值在之前调用了 set，其中 timestamp_prev <= timestamp 。如果有多个这样的值，它将返回与最大 timestamp_prev 关联的值。如果没有值，则返回空字符串（""）。

示例 1：

输入：
["TimeMap", "set", "get", "get", "set", "get", "get"]
[[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]]
输出：
[null, null, "bar", "bar", null, "bar2", "bar2"]

解释：
TimeMap timeMap = new TimeMap();
timeMap.set("foo", "bar", 1);  // 存储键 "foo" 和值 "bar" ，时间戳 timestamp = 1   
timeMap.get("foo", 1);         // 返回 "bar"
timeMap.get("foo", 3);         // 返回 "bar", 因为在时间戳 3 和时间戳 2 处没有对应 "foo" 的值，所以唯一的值位于时间戳 1 处（即 "bar"） 。
timeMap.set("foo", "bar2", 4); // 存储键 "foo" 和值 "bar2" ，时间戳 timestamp = 4  
timeMap.get("foo", 4);         // 返回 "bar2"
timeMap.get("foo", 5);         // 返回 "bar2"

提示：

1 <= key.length, value.length <= 100
key 和 value 由小写英文字母和数字组成
1 <= timestamp <= 10⁷
set 操作中的时间戳 timestamp 都是严格递增的
最多调用 set 和 get 操作 2 * 10⁵ 次

方法一：哈希表 + 有序集合（或二分查找） · Go 实现

思考

set 的时间戳严格递增，同一 key 的历史天然有序。get 要不超过给定时间戳的最近一次值，线性扫描在 $2 \times 10^{5}$ 次调用下偏慢。按 key 存 $(t i m e s t a m p, v a l u e)$ 列表，查询时二分上界即可。

我们可以用哈希表 $kvt$ 记录键值对，其中键为字符串 $key$ ，值为一个有序集合，集合中的每个元素为一个二元组 $(timestamp, value)$ ，表示键 $key$ 在时间戳 $timestamp$ 时对应的值为 $value$ 。

当我们需要查询键 $key$ 在时间戳 $timestamp$ 时对应的值时，我们可以通过有序集合的方法找到最大的时间戳 ${timestamp}^{'}$ ，使得 ${timestamp}^{'} \leq timestamp$ ，然后返回对应的值即可。

时间复杂度方面，对于 $set$ 操作，由于哈希表的插入操作的时间复杂度为 $O (1)$ ，因此时间复杂度为 $O (1)$ 。对于 $get$ 操作，由于哈希表的查找操作的时间复杂度为 $O (1)$ ，而有序集合的查找操作的时间复杂度为 $O (\log n)$ ，因此时间复杂度为 $O (\log n)$ 。空间复杂度为 $O (n)$ ，其中 $n$ 为 $set$ 操作的次数。

type TimeMap struct {
	ktv map[string][]pair
}

func Constructor() TimeMap {
	return TimeMap{map[string][]pair{}}
}

func (this *TimeMap) Set(key string, value string, timestamp int) {
	this.ktv[key] = append(this.ktv[key], pair{timestamp, value})
}

func (this *TimeMap) Get(key string, timestamp int) string {
	pairs := this.ktv[key]
	i := sort.Search(len(pairs), func(i int) bool { return pairs[i].t > timestamp })
	if i > 0 {
		return pairs[i-1].v
	}
	return ""
}

type pair struct {
	t int
	v string
}

/**
 * Your TimeMap object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Set(key,value,timestamp);
 * param_2 := obj.Get(key,timestamp);
 */

力扣原题 · Doocs 题解来源

1032. 字符流

困难1 种解法

标签：设计、字典树、数组、字符串、数据流、AC 自动机

题目、示例与约束

设计一个算法：接收一个字符流，并检查这些字符的后缀是否是字符串数组 words 中的一个字符串。

例如，words = ["abc", "xyz"] 且字符流中逐个依次加入 4 个字符 'a'、'x'、'y' 和 'z' ，你所设计的算法应当可以检测到 "axyz" 的后缀 "xyz" 与 words 中的字符串 "xyz" 匹配。

按下述要求实现 StreamChecker 类：

StreamChecker(String[] words) ：构造函数，用字符串数组 words 初始化数据结构。
boolean query(char letter)：从字符流中接收一个新字符，如果字符流中的任一非空后缀能匹配 words 中的某一字符串，返回 true ；否则，返回 false。

示例：

输入：
["StreamChecker", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query"]
[[["cd", "f", "kl"]], ["a"], ["b"], ["c"], ["d"], ["e"], ["f"], ["g"], ["h"], ["i"], ["j"], ["k"], ["l"]]
输出：
[null, false, false, false, true, false, true, false, false, false, false, false, true]

解释：
StreamChecker streamChecker = new StreamChecker(["cd", "f", "kl"]);
streamChecker.query("a"); // 返回 False
streamChecker.query("b"); // 返回 False
streamChecker.query("c"); // 返回n False
streamChecker.query("d"); // 返回 True ，因为 'cd' 在 words 中
streamChecker.query("e"); // 返回 False
streamChecker.query("f"); // 返回 True ，因为 'f' 在 words 中
streamChecker.query("g"); // 返回 False
streamChecker.query("h"); // 返回 False
streamChecker.query("i"); // 返回 False
streamChecker.query("j"); // 返回 False
streamChecker.query("k"); // 返回 False
streamChecker.query("l"); // 返回 True ，因为 'kl' 在 words 中

提示：

1 <= words.length <= 2000
1 <= words[i].length <= 200
words[i] 由小写英文字母组成
letter 是一个小写英文字母
最多调用查询 4 * 10⁴ 次

方法一：前缀树 · Go 实现

思考

每次查询都对历史字符流做一次多模式匹配， $q \leq 4 \times 10^{4}$ 且模式总长可观，朴素扫描会重复读同一后缀。询问的是「当前流是否以某个单词结尾」，因此应按后缀匹配。

把每个单词反转后插入前缀树，查询时从流的末尾往前走树。单词最长 $200$ ，故只需回看有限界长。

构造时建反向前缀树，查询把新字母追加到缓冲并在树上走至多 $201$ 步，遇到结束标记即成功。

我们可以根据初始化时的字符串数组 $w o r d s$ 构建前缀树，前缀树的每个节点包含两个属性：

children：指向 $26$ 个字母的指针数组，用于存储当前节点的子节点。
is_end：标记当前节点是否为某个字符串的结尾。

在构造函数中，我们遍历字符串数组 $w o r d s$ ，对于每个字符串 $w$ ，我们将其反转后，逐个字符插入到前缀树中，插入结束后，将当前节点的 is_end 标记为 true。

在 query 函数中，我们将当前字符 $c$ 加入到字符流中，然后从后往前遍历字符流，对于每个字符 $c$ ，我们在前缀树中查找是否存在以 $c$ 为结尾的字符串，如果存在，返回 true，否则返回 false。注意到 $w o r d s$ 中的字符串长度不超过 $200$ ，因此查询时最多只需要遍历 $200$ 个字符。

时间复杂度方面，构造函数的时间复杂度为 $O (L)$ ，而 query 函数的时间复杂度为 $O (M)$ 。其中 $L$ 为字符串数组 $w o r d s$ 中所有字符串的长度之和，而 $M$ 为字符串数组 $w o r d s$ 中字符串的最大长度。空间复杂度 $O (L)$ 。

type Trie struct {
	children [26]*Trie
	isEnd    bool
}

func newTrie() Trie {
	return Trie{}
}

func (this *Trie) Insert(word string) {
	node := this
	for i := len(word) - 1; i >= 0; i-- {
		idx := word[i] - 'a'
		if node.children[idx] == nil {
			node.children[idx] = &Trie{}
		}
		node = node.children[idx]
	}
	node.isEnd = true
}

func (this *Trie) Search(word []byte) bool {
	node := this
	for i := len(word) - 1; i >= 0; i-- {
		idx := word[i] - 'a'
		if node.children[idx] == nil {
			return false
		}
		node = node.children[idx]
		if node.isEnd {
			return true
		}
	}
	return false
}

type StreamChecker struct {
	trie Trie
	s    []byte
}

func Constructor(words []string) StreamChecker {
	trie := newTrie()
	for _, w := range words {
		trie.Insert(w)
	}
	return StreamChecker{trie, []byte{}}
}

func (this *StreamChecker) Query(letter byte) bool {
	this.s = append(this.s, letter)
	return this.trie.Search(this.s)
}

/**
 * Your StreamChecker object will be instantiated and called as such:
 * obj := Constructor(words);
 * param_1 := obj.Query(letter);
 */

力扣原题 · Doocs 题解来源

1146. 快照数组

中等1 种解法

标签：设计、数组、哈希表、二分查找、可持久化数据结构

题目、示例与约束

实现支持下列接口的「快照数组」- SnapshotArray：

SnapshotArray(int length) - 初始化一个与指定长度相等的类数组的数据结构。初始时，每个元素都等于 0。
void set(index, val) - 会将指定索引 index 处的元素设置为 val。
int snap() - 获取该数组的快照，并返回快照的编号 snap_id（快照号是调用 snap() 的总次数减去 1）。
int get(index, snap_id) - 根据指定的 snap_id 选择快照，并返回该快照指定索引 index 的值。

示例：

输入：["SnapshotArray","set","snap","set","get"]
     [[3],[0,5],[],[0,6],[0,0]]
输出：[null,null,0,null,5]
解释：
SnapshotArray snapshotArr = new SnapshotArray(3); // 初始化一个长度为 3 的快照数组
snapshotArr.set(0,5);  // 令 array[0] = 5
snapshotArr.snap();  // 获取快照，返回 snap_id = 0
snapshotArr.set(0,6);
snapshotArr.get(0,0);  // 获取 snap_id = 0 的快照中 array[0] 的值，返回 5

提示：

1 <= length <= 50000
题目最多进行50000 次set，snap，和 get的调用。
0 <= index < length
0 <= snap_id < 我们调用 snap() 的总次数
0 <= val <= 10^9

方法一：数组 + 二分查找 · Go 实现

思考

每次 snap 若复制整个数组，空间与快照次数、长度之积成正比。每个下标只记录「快照编号 $\to$ 值」的变更历史，set 追加当前快照号与新值。get 在该下标的有序历史上二分到 $\leq s n a p_i d$ 的最后一次修改；若无修改则默认为 $0$ 。

我们维护一个长度为 $length$ 的数组，数组中的每个元素是一个列表，用来存储每次设置的值以及对应的快照 ID。

调用 set 方法时，将值和快照 ID 添加到对应索引的列表中。时间复杂度 $O (1)$ 。

调用 snap 方法时，我们先将快照 ID 加一，然后返回快照 ID 减一。时间复杂度 $O (1)$ 。

调用 get 方法时，我们使用二分查找找到对应位置的第一个快照 ID 大于 snap_id 的值，然后返回前一个的值。如果找不到，则返回 0。时间复杂度 $O (\log n)$ 。

空间复杂度 $O (n)$ 。

type SnapshotArray struct {
	arr [][][2]int
	i   int
}

func Constructor(length int) SnapshotArray {
	return SnapshotArray{make([][][2]int, length), 0}
}

func (this *SnapshotArray) Set(index int, val int) {
	this.arr[index] = append(this.arr[index], [2]int{this.i, val})
}

func (this *SnapshotArray) Snap() int {
	this.i++
	return this.i - 1
}

func (this *SnapshotArray) Get(index int, snap_id int) int {
	i := sort.Search(len(this.arr[index]), func(i int) bool { return this.arr[index][i][0] > snap_id }) - 1
	if i < 0 {
		return 0
	}
	return this.arr[index][i][1]
}

/**
 * Your SnapshotArray object will be instantiated and called as such:
 * obj := Constructor(length);
 * obj.Set(index,val);
 * param_2 := obj.Snap();
 * param_3 := obj.Get(index,snap_id);
 */

力扣原题 · Doocs 题解来源

1157. 子数组中占绝大多数的元素

困难1 种解法

标签：设计、树状数组、线段树、数组、二分查找、摩尔投票算法

题目、示例与约束

设计一个数据结构，有效地找到给定子数组的 多数元素 。

子数组的 多数元素 是在子数组中出现 threshold 次数或次数以上的元素。

实现 MajorityChecker 类:

MajorityChecker(int[] arr) 会用给定的数组 arr 对 MajorityChecker 初始化。
int query(int left, int right, int threshold) 返回子数组中的元素 arr[left...right] 至少出现 threshold 次数，如果不存在这样的元素则返回 -1。

示例 1：

输入:
["MajorityChecker", "query", "query", "query"]
[[[1, 1, 2, 2, 1, 1]], [0, 5, 4], [0, 3, 3], [2, 3, 2]]
输出：
[null, 1, -1, 2]

解释：
MajorityChecker majorityChecker = new MajorityChecker([1,1,2,2,1,1]);
majorityChecker.query(0,5,4); // 返回 1
majorityChecker.query(0,3,3); // 返回 -1
majorityChecker.query(2,3,2); // 返回 2

提示：

1 <= arr.length <= 2 * 10⁴
1 <= arr[i] <= 2 * 10⁴
0 <= left <= right < arr.length
threshold <= right - left + 1
2 * threshold > right - left + 1
调用 query 的次数最多为 10⁴

方法一：线段树 + 摩尔投票 + 二分查找 · Go 实现

思考

子数组众数查询次数多，不宜每次扫描。摩尔投票可在线段树上合并：区间候选众数及其抵消后的计数可按左右子区间合并。查询得到候选 $x$ 后，用各值的下标列表二分统计 $[l e f t, r i g h t]$ 内出现次数，与 $t h r e s h o l d$ 比较即可确认或否定。

我们注意到，题目需要我们找出特定区间内可能的众数，考虑使用线段树来维护每个区间内的候选众数以及其出现的次数。

我们定义线段树的每个节点为 Node，每个节点包含如下属性：

l：节点的左端点，下标从 $1$ 开始。
r：节点的右端点，下标从 $1$ 开始。
x：节点的候选众数。
cnt：节点的候选众数出现的次数。

线段树主要有以下几个操作：

build(u, l, r)：建立线段树。
pushup(u)：用子节点的信息更新父节点的信息。
query(u, l, r)：查询区间和。

在主函数的初始化方法中，我们先创建一个线段树，并且用哈希表 $d$ 记录每个元素在数组中的所有下标。

在 query(left, right, threshold) 方法中，我们直接调用线段树的 query 方法，得到候选众数 $x$ 。然后使用二分查找，找到 $x$ 在数组中第一个大于等于 $l e f t$ 的下标 $l$ ，以及第一个大于 $r i g h t$ 的下标 $r$ 。如果 $r - l \geq t h r e s h o l d$ ，则返回 $x$ ，否则返回 $- 1$ 。

时间复杂度方面，初始化方法的时间复杂度为 $O (n)$ ，查询方法的时间复杂度为 $O (\log n)$ 。空间复杂度为 $O (n)$ 。其中 $n$ 为数组的长度。

type node struct {
	l, r, x, cnt int
}

type segmentTree struct {
	nums []int
	tr   []*node
}

type pair struct{ x, cnt int }

func newSegmentTree(nums []int) *segmentTree {
	n := len(nums)
	tr := make([]*node, n<<2)
	for i := range tr {
		tr[i] = &node{}
	}
	t := &segmentTree{nums, tr}
	t.build(1, 1, n)
	return t
}

func (t *segmentTree) build(u, l, r int) {
	t.tr[u].l, t.tr[u].r = l, r
	if l == r {
		t.tr[u].x = t.nums[l-1]
		t.tr[u].cnt = 1
		return
	}
	mid := (l + r) >> 1
	t.build(u<<1, l, mid)
	t.build(u<<1|1, mid+1, r)
	t.pushup(u)
}

func (t *segmentTree) query(u, l, r int) pair {
	if t.tr[u].l >= l && t.tr[u].r <= r {
		return pair{t.tr[u].x, t.tr[u].cnt}
	}
	mid := (t.tr[u].l + t.tr[u].r) >> 1
	if r <= mid {
		return t.query(u<<1, l, r)
	}
	if l > mid {
		return t.query(u<<1|1, l, r)
	}
	left, right := t.query(u<<1, l, r), t.query(u<<1|1, l, r)
	if left.x == right.x {
		left.cnt += right.cnt
	} else if left.cnt >= right.cnt {
		left.cnt -= right.cnt
	} else {
		right.cnt -= left.cnt
		left = right
	}
	return left
}

func (t *segmentTree) pushup(u int) {
	if t.tr[u<<1].x == t.tr[u<<1|1].x {
		t.tr[u].x = t.tr[u<<1].x
		t.tr[u].cnt = t.tr[u<<1].cnt + t.tr[u<<1|1].cnt
	} else if t.tr[u<<1].cnt >= t.tr[u<<1|1].cnt {
		t.tr[u].x = t.tr[u<<1].x
		t.tr[u].cnt = t.tr[u<<1].cnt - t.tr[u<<1|1].cnt
	} else {
		t.tr[u].x = t.tr[u<<1|1].x
		t.tr[u].cnt = t.tr[u<<1|1].cnt - t.tr[u<<1].cnt
	}
}

type MajorityChecker struct {
	tree *segmentTree
	d    map[int][]int
}

func Constructor(arr []int) MajorityChecker {
	tree := newSegmentTree(arr)
	d := map[int][]int{}
	for i, x := range arr {
		d[x] = append(d[x], i)
	}
	return MajorityChecker{tree, d}
}

func (this *MajorityChecker) Query(left int, right int, threshold int) int {
	x := this.tree.query(1, left+1, right+1).x
	l := sort.SearchInts(this.d[x], left)
	r := sort.SearchInts(this.d[x], right+1)
	if r-l >= threshold {
		return x
	}
	return -1
}

/**
 * Your MajorityChecker object will be instantiated and called as such:
 * obj := Constructor(arr);
 * param_1 := obj.Query(left,right,threshold);
 */

力扣原题 · Doocs 题解来源

1166. 设计文件系统 🔒

中等1 种解法

标签：设计、字典树、哈希表、字符串

题目、示例与约束

你需要设计一个文件系统，你可以创建新的路径并将它们与不同的值关联。

路径的格式是一个或多个连接在一起的字符串，形式为： / ，后面跟着一个或多个小写英文字母。例如， " /leetcode" 和 "/leetcode/problems" 是有效路径，而空字符串 "" 和 "/" 不是。

实现 FileSystem 类:

bool createPath(string path, int value) 创建一个新的 path ，并在可能的情况下关联一个 value ，然后返回 true 。如果路径已经存在或其父路径不存在，则返回 false 。
int get(string path) 返回与 path 关联的值，如果路径不存在则返回 -1 。

示例 1：

输入： 
["FileSystem","create","get"]
[[],["/a",1],["/a"]]
输出： 
[null,true,1]
解释： 
FileSystem fileSystem = new FileSystem();

fileSystem.create("/a", 1); // 返回 true
fileSystem.get("/a"); // 返回 1

示例 2：

输入： 
["FileSystem","createPath","createPath","get","createPath","get"]
[[],["/leet",1],["/leet/code",2],["/leet/code"],["/c/d",1],["/c"]]
输出： 
[null,true,true,2,false,-1]
解释：
FileSystem fileSystem = new FileSystem();

fileSystem.createPath("/leet", 1); // 返回 true
fileSystem.createPath("/leet/code", 2); // 返回 true
fileSystem.get("/leet/code"); // 返回 2
fileSystem.createPath("/c/d", 1); // 返回 false 因为父路径 "/c" 不存在。
fileSystem.get("/c"); // 返回 -1 因为该路径不存在。

提示：

对两个函数的调用次数加起来小于等于 10⁴
2 <= path.length <= 100
1 <= value <= 10⁹

方法一：前缀树 · Go 实现

思考

路径按 / 分段，创建时父路径必须已存在且本路径尚未创建，查询则沿段下行。前缀树以路径段为边：插入时除最后一段外均须已有孩子，最后一段不能已存在；查找任一段缺失即返回 $- 1$ 。哈希孩子使每段查找为期望常数。

我们可以使用前缀树来存储路径，每个节点存储一个值，表示该节点对应的路径的值。

定义前缀树的节点结构如下：

children：子节点，使用哈希表存储，键为子节点的路径，值为子节点的引用；
v：当前节点对应的路径的值。

定义前缀树的方法如下：

insert(w, v)：插入路径 $w$ ，并将其对应的值设为 $v$ 。如果路径 $w$ 已经存在或其父路径不存在，则返回 false，否则返回 true。时间复杂度为 $O (| w |)$ ，其中 $| w |$ 为路径 $w$ 的长度；
search(w)：返回路径 $w$ 对应的值。如果路径 $w$ 不存在，则返回 $- 1$ 。时间复杂度为 $O (| w |)$ 。

总时间复杂度 $O (\sum_{w \in W} | w |)$ ，总空间复杂度 $O (\sum_{w \in W} | w |)$ ，其中 $W$ 为所有插入的路径的集合。

type trie struct {
	children map[string]*trie
	v        int
}

func newTrie(v int) *trie {
	return &trie{map[string]*trie{}, v}
}

func (t *trie) insert(w string, v int) bool {
	node := t
	ps := strings.Split(w, "/")
	for _, p := range ps[1 : len(ps)-1] {
		if _, ok := node.children[p]; !ok {
			return false
		}
		node = node.children[p]
	}
	if _, ok := node.children[ps[len(ps)-1]]; ok {
		return false
	}
	node.children[ps[len(ps)-1]] = newTrie(v)
	return true
}

func (t *trie) search(w string) int {
	node := t
	ps := strings.Split(w, "/")
	for _, p := range ps[1:] {
		if _, ok := node.children[p]; !ok {
			return -1
		}
		node = node.children[p]
	}
	return node.v
}

type FileSystem struct {
	trie *trie
}

func Constructor() FileSystem {
	return FileSystem{trie: newTrie(-1)}
}

func (this *FileSystem) CreatePath(path string, value int) bool {
	return this.trie.insert(path, value)
}

func (this *FileSystem) Get(path string) int {
	return this.trie.search(path)
}

/**
 * Your FileSystem object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.CreatePath(path,value);
 * param_2 := obj.Get(path);
 */

力扣原题 · Doocs 题解来源

1172. 餐盘栈

困难1 种解法

标签：栈、设计、哈希表、堆（优先队列）

题目、示例与约束

我们把无限数量 ∞ 的栈排成一行，按从左到右的次序从 0 开始编号。每个栈的的最大容量 capacity 都相同。

实现一个叫「餐盘」的类 DinnerPlates：

DinnerPlates(int capacity) - 给出栈的最大容量 capacity。
void push(int val) - 将给出的正整数 val 推入 从左往右第一个 没有满的栈。
int pop() - 返回 从右往左第一个 非空栈顶部的值，并将其从栈中删除；如果所有的栈都是空的，请返回 -1。
int popAtStack(int index) - 返回编号 index 的栈顶部的值，并将其从栈中删除；如果编号 index 的栈是空的，请返回 -1。

示例：

输入： 
["DinnerPlates","push","push","push","push","push","popAtStack","push","push","popAtStack","popAtStack","pop","pop","pop","pop","pop"]
[[2],[1],[2],[3],[4],[5],[0],[20],[21],[0],[2],[],[],[],[],[]]
输出：
[null,null,null,null,null,null,2,null,null,20,21,5,4,3,1,-1]

解释：
DinnerPlates D = DinnerPlates(2);  // 初始化，栈最大容量 capacity = 2
D.push(1);
D.push(2);
D.push(3);
D.push(4);
D.push(5);         // 栈的现状为：    2  4
                                    1  3  5
                                    ﹈ ﹈ ﹈
D.popAtStack(0);   // 返回 2。栈的现状为：      4
                                          1  3  5
                                          ﹈ ﹈ ﹈
D.push(20);        // 栈的现状为：  20  4
                                   1  3  5
                                   ﹈ ﹈ ﹈
D.push(21);        // 栈的现状为：  20  4 21
                                   1  3  5
                                   ﹈ ﹈ ﹈
D.popAtStack(0);   // 返回 20。栈的现状为：       4 21
                                            1  3  5
                                            ﹈ ﹈ ﹈
D.popAtStack(2);   // 返回 21。栈的现状为：       4
                                            1  3  5
                                            ﹈ ﹈ ﹈ 
D.pop()            // 返回 5。栈的现状为：        4
                                            1  3 
                                            ﹈ ﹈  
D.pop()            // 返回 4。栈的现状为：    1  3 
                                           ﹈ ﹈   
D.pop()            // 返回 3。栈的现状为：    1 
                                           ﹈   
D.pop()            // 返回 1。现在没有栈。
D.pop()            // 返回 -1。仍然没有栈。

提示：

1 <= capacity <= 20000
1 <= val <= 20000
0 <= index <= 100000
最多会对 push，pop，和 popAtStack 进行 200000 次调用。

方法一：栈数组 + 有序集合 · Go 实现

思考

push 必须落在最左侧未满栈，pop 落在最右侧非空栈，另可指定栈弹出。若每次从左扫描未满栈，操作次数大时偏慢。用栈数组存盘子，有序集合存未满下标，则最左未满为集合最小元；弹出后若成为未满则加回，最右空栈则收缩数组，保证 pop 对应最后一个非空栈。

我们定义以下数据结构或变量：

capacity：每个栈的容量；
stacks：栈数组，用于存储所有的栈，其中每个栈的最大容量都是 capacity；
not_full：有序集合，用于存储所有未满的栈在栈数组中的下标。

对于 push(val) 操作：

我们首先判断 not_full 是否为空，如果为空，则说明没有未满的栈，需要新建一个栈，然后将 val 压入该栈中，此时判断容量 capacity 是否大于 $1$ ，如果大于 $1$ ，则将该栈的下标加入 not_full 中。
如果 not_full 不为空，则说明有未满的栈，我们取出 not_full 中最小的下标 index，将 val 压入 stacks[index] 中，此时如果 stacks[index] 的容量等于 capacity，则将 index 从 not_full 中删除。

对于 popAtStack(index) 操作：

我们首先判断 index 是否在 stacks 的下标范围内，如果不在，则直接返回 $- 1$ 。如果 stacks[index] 为空，同样直接返回 $- 1$ 。
如果 stacks[index] 不为空，则弹出 stacks[index] 的栈顶元素 val。如果 index 等于 stacks 的长度减 $1$ ，则说明 stacks[index] 是最后一个栈，如果为空，我们循环将最后一个栈的下标从 not_full 中移出，并且在栈数组 stacks 中移除最后一个栈，直到最后一个栈不为空、或者栈数组 stacks 为空为止。否则，如果 stacks[index] 不是最后一个栈，我们将 index 加入 not_full 中。
最后返回 val。

对于 pop() 操作：

我们直接调用 popAtStack(stacks.length - 1) 即可。

时间复杂度 $O (n \times \log n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为操作次数。

type DinnerPlates struct {
	capacity int
	stacks   [][]int
	notFull  *redblacktree.Tree
}

func Constructor(capacity int) DinnerPlates {
	return DinnerPlates{capacity: capacity, notFull: redblacktree.NewWithIntComparator()}
}

func (this *DinnerPlates) Push(val int) {
	if this.notFull.Size() == 0 {
		this.stacks = append(this.stacks, []int{val})
		if this.capacity > 1 {
			this.notFull.Put(len(this.stacks)-1, nil)
		}
	} else {
		index, _ := this.notFull.Left().Key.(int)
		this.stacks[index] = append(this.stacks[index], val)
		if len(this.stacks[index]) == this.capacity {
			this.notFull.Remove(index)
		}
	}
}

func (this *DinnerPlates) Pop() int {
	return this.PopAtStack(len(this.stacks) - 1)
}

func (this *DinnerPlates) PopAtStack(index int) int {
	if index < 0 || index >= len(this.stacks) || len(this.stacks[index]) == 0 {
		return -1
	}
	val := this.stacks[index][len(this.stacks[index])-1]
	this.stacks[index] = this.stacks[index][:len(this.stacks[index])-1]
	if index == len(this.stacks)-1 && len(this.stacks[index]) == 0 {
		for len(this.stacks) > 0 && len(this.stacks[len(this.stacks)-1]) == 0 {
			this.notFull.Remove(len(this.stacks) - 1)
			this.stacks = this.stacks[:len(this.stacks)-1]
		}
	} else {
		this.notFull.Put(index, nil)
	}
	return val
}

/**
 * Your DinnerPlates object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * obj.Push(val);
 * param_2 := obj.Pop();
 * param_3 := obj.PopAtStack(index);
 */

力扣原题 · Doocs 题解来源

1206. 设计跳表

困难1 种解法

标签：设计、链表

题目、示例与约束

不使用任何库函数，设计一个跳表。

跳表是在 O(log(n)) 时间内完成增加、删除、搜索操作的数据结构。跳表相比于树堆与红黑树，其功能与性能相当，并且跳表的代码长度相较下更短，其设计思想与链表相似。

例如，一个跳表包含 [30, 40, 50, 60, 70, 90] ，然后增加 80、45 到跳表中，以下图的方式操作：

跳表中有很多层，每一层是一个短的链表。在第一层的作用下，增加、删除和搜索操作的时间复杂度不超过 O(n)。跳表的每一个操作的平均时间复杂度是 O(log(n))，空间复杂度是 O(n)。

了解更多 : https://oi-wiki.org/ds/skiplist/

在本题中，你的设计应该要包含这些函数：

bool search(int target) : 返回target是否存在于跳表中。
void add(int num): 插入一个元素到跳表。
bool erase(int num): 在跳表中删除一个值，如果 num 不存在，直接返回false. 如果存在多个 num ，删除其中任意一个即可。

注意，跳表中可能存在多个相同的值，你的代码需要处理这种情况。

示例 1:

输入
["Skiplist", "add", "add", "add", "search", "add", "search", "erase", "erase", "search"]
[[], [1], [2], [3], [0], [4], [1], [0], [1], [1]]
输出
[null, null, null, null, false, null, true, false, true, false]

解释
Skiplist skiplist = new Skiplist();
skiplist.add(1);
skiplist.add(2);
skiplist.add(3);
skiplist.search(0);   // 返回 false
skiplist.add(4);
skiplist.search(1);   // 返回 true
skiplist.erase(0);    // 返回 false，0 不在跳表中
skiplist.erase(1);    // 返回 true
skiplist.search(1);   // 返回 false，1 已被擦除

提示:

0 <= num, target <= 2 * 10⁴
调用search, add, erase操作次数不大于 5 * 10⁴

方法一：数据结构 · Go 实现

思考

每次操作可达 $5 \times 10^{4}$ ，有序数组插入删除为线性，平衡树虽可达 $O (\log n)$ 但实现偏重。跳表用多层前向指针模拟平衡树的分层索引：底层存全部键，上层稀疏抽样。

查找、插入、删除都从最高层向下降到不超过目标的最近节点，再进入下一层，期望跳跃次数为对数。新节点层数以概率 $p$ 向上生长，使高层保持稀疏。

实现上用带头节点的多层链表， $f i n d_c l o s e s t$ 在一层内滑到最接近目标的位置； $r a n d o m_l e v e l$ 决定新节点高度。期望每步 $O (\log n)$ ，空间与节点数及层高成正比。

跳表的核心思想是使用多个“层级”来存储数据，每一层都相当于一个索引。数据从底层的链表开始逐渐上升到更高层级的链表，最终形成一个多层链表结构。每一层的节点只包含部分数据，这样就可以通过跳跃来减少查找的时间。

在这个问题中，我们使用一个 $Node$ 类来表示跳表的节点，每个节点包含一个 $val$ 域和一个 $next$ 数组，数组的长度为 $level$ ，表示当前节点在每一层的下一个节点。我们使用一个 $Skiplist$ 类来实现跳表的操作。

跳表包含一个头节点 $head$ 和当前的最大层数 $level$ 。头节点的值设为 $- 1$ ，用于标识链表的起始位置。我们使用一个动态数组 $next$ 来存储指向后继节点的指针。

对于 $search$ 操作，我们从跳表的最高层开始，逐层向下遍历，直到找到目标节点或者确定目标节点不存在。每层都通过 $find_closest$ 方法跳跃到最接近目标的节点。

对于 $add$ 操作，我们首先随机决定新节点的层数。然后，从最高层开始，逐层找到每层中最接近新值的节点，并在相应位置插入新节点。如果插入的层数大于当前跳表的最大层数，我们需要更新跳表的层数。

对于 $erase$ 操作，类似于查找操作，遍历跳表的每一层，找到需要删除的节点并删除它。删除节点时需要更新每一层的 $next$ 指针。如果跳表的最高层没有节点，则需要减少跳表的层数。

另外，我们定义了一个 $random_level$ 方法来随机决定新节点的层数。该方法会生成一个 $[1, max_level]$ 之间的随机数，直到生成的随机数大于等于 $p$ 为止。还有一个 $find_closest$ 方法用于查找每一层中最接近目标值的节点。

上述操作的时间复杂度为 $O (\log n)$ ，其中 $n$ 为跳表的节点数。空间复杂度为 $O (n)$ 。

func init() { rand.Seed(time.Now().UnixNano()) }

const (
	maxLevel = 16
	p        = 0.5
)

type node struct {
	val  int
	next []*node
}

func newNode(val, level int) *node {
	return &node{
		val:  val,
		next: make([]*node, level),
	}
}

type Skiplist struct {
	head  *node
	level int
}

func Constructor() Skiplist {
	return Skiplist{
		head:  newNode(-1, maxLevel),
		level: 1,
	}
}

func (this *Skiplist) Search(target int) bool {
	p := this.head
	for i := this.level - 1; i >= 0; i-- {
		p = findClosest(p, i, target)
		if p.next[i] != nil && p.next[i].val == target {
			return true
		}
	}
	return false
}

func (this *Skiplist) Add(num int) {
	level := randomLevel()
	if level > this.level {
		this.level = level
	}
	node := newNode(num, level)
	p := this.head
	for i := this.level - 1; i >= 0; i-- {
		p = findClosest(p, i, num)
		if i < level {
			node.next[i] = p.next[i]
			p.next[i] = node
		}
	}
}

func (this *Skiplist) Erase(num int) bool {
	ok := false
	p := this.head
	for i := this.level - 1; i >= 0; i-- {
		p = findClosest(p, i, num)
		if p.next[i] != nil && p.next[i].val == num {
			p.next[i] = p.next[i].next[i]
			ok = true
		}
	}
	for this.level > 1 && this.head.next[this.level-1] == nil {
		this.level--
	}
	return ok
}

func findClosest(p *node, level, target int) *node {
	for p.next[level] != nil && p.next[level].val < target {
		p = p.next[level]
	}
	return p
}

func randomLevel() int {
	level := 1
	for level < maxLevel && rand.Float64() < p {
		level++
	}
	return level
}

/**
 * Your Skiplist object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Search(target);
 * obj.Add(num);
 * param_3 := obj.Erase(num);
 */

力扣原题 · Doocs 题解来源

1244. 力扣排行榜 🔒

中等1 种解法

标签：设计、哈希表、排序

题目、示例与约束

新一轮的「力扣杯」编程大赛即将启动，为了动态显示参赛者的得分数据，需要设计一个排行榜 Leaderboard。

请你帮忙来设计这个 Leaderboard 类，使得它有如下 3 个函数：

addScore(playerId, score)：
- 假如参赛者已经在排行榜上，就给他的当前得分增加 score 点分值并更新排行。
- 假如该参赛者不在排行榜上，就把他添加到榜单上，并且将分数设置为 score。
top(K)：返回前 K 名参赛者的 得分总和。
reset(playerId)：将指定参赛者的成绩清零（换句话说，将其从排行榜中删除）。题目保证在调用此函数前，该参赛者已有成绩，并且在榜单上。

请注意，在初始状态下，排行榜是空的。

示例 1：

输入： 
["Leaderboard","addScore","addScore","addScore","addScore","addScore","top","reset","reset","addScore","top"]
[[],[1,73],[2,56],[3,39],[4,51],[5,4],[1],[1],[2],[2,51],[3]]
输出：
[null,null,null,null,null,null,73,null,null,null,141]

解释： 
Leaderboard leaderboard = new Leaderboard ();
leaderboard.addScore(1,73);   // leaderboard = [[1,73]];
leaderboard.addScore(2,56);   // leaderboard = [[1,73],[2,56]];
leaderboard.addScore(3,39);   // leaderboard = [[1,73],[2,56],[3,39]];
leaderboard.addScore(4,51);   // leaderboard = [[1,73],[2,56],[3,39],[4,51]];
leaderboard.addScore(5,4);    // leaderboard = [[1,73],[2,56],[3,39],[4,51],[5,4]];
leaderboard.top(1);           // returns 73;
leaderboard.reset(1);         // leaderboard = [[2,56],[3,39],[4,51],[5,4]];
leaderboard.reset(2);         // leaderboard = [[3,39],[4,51],[5,4]];
leaderboard.addScore(2,51);   // leaderboard = [[2,51],[3,39],[4,51],[5,4]];
leaderboard.top(3);           // returns 141 = 51 + 51 + 39;

提示：

1 <= playerId, K <= 10000
题目保证 K 小于或等于当前参赛者的数量
1 <= score <= 100
最多进行 1000 次函数调用

方法一：Go 实现（灵茶山艾府） · Go 实现

灵茶山艾府 · 源码 · MIT 许可

本站根据 Go 源码整理，非作者原文。

思路：用包级映射保存玩家的累计分数。AddScore 直接累加，Reset 把分数置零并保留该玩家的键。Top 复制映射中的全部分数，升序排序，再累加最后 k 项。Constructor 会重新初始化这个共享映射。

复杂度：设 P 为映射中保存的玩家数（包括重置为零的玩家）。Constructor 为 O(1)，AddScore、Reset 平均为 O(1)，Top 时间为 O(P log(P+1)+k)。持久状态占 O(P) 空间，每次 Top 另需 O(P) 辅助空间。

import "sort"

// github.com/EndlessCheng/codeforces-go
type Leaderboard struct{}

var s map[int]int

func Constructor() (_ Leaderboard) {
	s = map[int]int{}
	return
}

func (Leaderboard) AddScore(playerId, score int) {
	s[playerId] += score
}

func (Leaderboard) Top(k int) (ans int) {
	a := make([]int, 0, len(s))
	for _, v := range s {
		a = append(a, v)
	}
	sort.Ints(a)
	for _, v := range a[len(a)-k:] {
		ans += v
	}
	return
}

func (Leaderboard) Reset(playerId int) {
	s[playerId] = 0
}

/**
 * Your Leaderboard object will be instantiated and called as such:
 * obj := Constructor();
 * obj.AddScore(playerId,score);
 * param_2 := obj.Top(K);
 * obj.Reset(playerId);
 */

力扣原题 · Doocs 题解来源

1261. 在受污染的二叉树中查找元素

中等1 种解法

标签：树、深度优先搜索、广度优先搜索、设计、哈希表、二叉树

题目、示例与约束

给出一个满足下述规则的二叉树：

root.val == 0
对于任意 treeNode：
1. 如果 treeNode.val 为 x 且 treeNode.left != null，那么 treeNode.left.val == 2 * x + 1
2. 如果 treeNode.val 为 x 且 treeNode.right != null，那么 treeNode.right.val == 2 * x + 2

现在这个二叉树受到「污染」，所有的 treeNode.val 都变成了 -1。

请你先还原二叉树，然后实现 FindElements 类：

FindElements(TreeNode* root) 用受污染的二叉树初始化对象，你需要先把它还原。
bool find(int target) 判断目标值 target 是否存在于还原后的二叉树中并返回结果。

示例 1：

输入：
["FindElements","find","find"]
[[[-1,null,-1]],[1],[2]]
输出：
[null,false,true]
解释：
FindElements findElements = new FindElements([-1,null,-1]); 
findElements.find(1); // return False 
findElements.find(2); // return True

示例 2：

输入：
["FindElements","find","find","find"]
[[[-1,-1,-1,-1,-1]],[1],[3],[5]]
输出：
[null,true,true,false]
解释：
FindElements findElements = new FindElements([-1,-1,-1,-1,-1]);
findElements.find(1); // return True
findElements.find(3); // return True
findElements.find(5); // return False

示例 3：

输入：
["FindElements","find","find","find","find"]
[[[-1,null,-1,-1,null,-1]],[2],[3],[4],[5]]
输出：
[null,true,false,false,true]
解释：
FindElements findElements = new FindElements([-1,null,-1,-1,null,-1]);
findElements.find(2); // return True
findElements.find(3); // return False
findElements.find(4); // return False
findElements.find(5); // return True

提示：

TreeNode.val == -1
二叉树的高度不超过 20
节点的总数在 [1, 10⁴] 之间
调用 find() 的总次数在 [1, 10⁴] 之间
0 <= target <= 10⁶

方法一：DFS + 哈希表 · Go 实现

思考

被污染后值全是 $- 1$ ，但父子仍满足 $l e f t = 2 x + 1$ 、 $r i g h t = 2 x + 2$ ，根为 $0$ 。查找可达 $10^{4}$ 次，不宜每次从根重算路径。

构造时 DFS 恢复每个节点的值并放入哈希集合； $f i n d$ 只查询集合。一次遍历换来常数查找。

我们先通过 DFS 遍历二叉树，将节点值恢复为原来的值，并将所有节点值存入哈希表中。然后在查找时，只需要判断哈希表中是否存在目标值即可。

时间复杂度方面，初始化时需要遍历二叉树，时间复杂度为 $O (n)$ ，查找时只需要判断哈希表中是否存在目标值，时间复杂度为 $O (1)$ 。空间复杂度 $O (n)$ 。其中 $n$ 为二叉树节点个数。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
type FindElements struct {
	s map[int]bool
}

func Constructor(root *TreeNode) FindElements {
	root.Val = 0
	s := map[int]bool{}
	var dfs func(*TreeNode)
	dfs = func(root *TreeNode) {
		s[root.Val] = true
		if root.Left != nil {
			root.Left.Val = root.Val*2 + 1
			dfs(root.Left)
		}
		if root.Right != nil {
			root.Right.Val = root.Val*2 + 2
			dfs(root.Right)
		}
	}
	dfs(root)
	return FindElements{s}
}

func (this *FindElements) Find(target int) bool {
	return this.s[target]
}

/**
 * Your FindElements object will be instantiated and called as such:
 * obj := Constructor(root);
 * param_1 := obj.Find(target);
 */

力扣原题 · Doocs 题解来源

1286. 字母组合迭代器

中等2 种解法

标签：设计、字符串、回溯、迭代器

题目、示例与约束

请你设计一个迭代器类 CombinationIterator ，包括以下内容：

CombinationIterator(string characters, int combinationLength) 一个构造函数，输入参数包括：用一个 有序且字符唯一 的字符串 characters（该字符串只包含小写英文字母）和一个数字 combinationLength 。
函数 next() ，按 字典序 返回长度为 combinationLength 的下一个字母组合。
函数 hasNext() ，只有存在长度为 combinationLength 的下一个字母组合时，才返回 true

示例 1：

输入:
["CombinationIterator", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[["abc", 2], [], [], [], [], [], []]
输出：
[null, "ab", true, "ac", true, "bc", false]
解释：
CombinationIterator iterator = new CombinationIterator("abc", 2); // 创建迭代器 iterator
iterator.next(); // 返回 "ab"
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 "ac"
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 "bc"
iterator.hasNext(); // 返回 false

提示：

1 <= combinationLength <= characters.length <= 15
characters 中每个字符都不同
每组测试数据最多对 next 和 hasNext 调用 10⁴次
题目保证每次调用函数 next 时都存在下一个字母组合。

方法一：DFS 回溯 · Go 实现

思考

字符互异且长度不超过 $15$ ，组合数有限。预生成全部长度为 $c o m b i n a t i o n L e n g t h$ 的组合后， $n e x t$ / $h a s N e x t$ 只做下标移动。DFS 按从左到右选或不选，保证字典序。

我们通过 $D F S$ 枚举，预处理生成所有长度为 $c o m b i n a t i o n L e n g t h$ 的字符串，存放到 $c s$ 数组中。

type CombinationIterator struct {
	cs  []string
	idx int
}

func Constructor(characters string, combinationLength int) CombinationIterator {
	t := []byte{}
	n := len(characters)
	cs := []string{}
	var dfs func(int)
	dfs = func(i int) {
		if len(t) == combinationLength {
			cs = append(cs, string(t))
			return
		}
		if i == n {
			return
		}
		t = append(t, characters[i])
		dfs(i + 1)
		t = t[:len(t)-1]
		dfs(i + 1)
	}
	dfs(0)
	return CombinationIterator{cs, 0}
}

func (this *CombinationIterator) Next() string {
	ans := this.cs[this.idx]
	this.idx++
	return ans
}

func (this *CombinationIterator) HasNext() bool {
	return this.idx < len(this.cs)
}

/**
 * Your CombinationIterator object will be instantiated and called as such:
 * obj := Constructor(characters, combinationLength);
 * param_1 := obj.Next();
 * param_2 := obj.HasNext();
 */

方法二：二进制编码 · Go 实现

思考

方法一占用与组合数成正比的数组。用长度为 $n$ 的二进制掩码表示子集，从满掩码向下扫，只输出恰有 $c o m b i n a t i o n L e n g t h$ 个 $1$ 的掩码，按位还原字符。按需生成，不必存下全部串。

我们看个例子，对于 $a b c d$ ，若 $c o m b i n a t i o n L e n g t h$ 为 2，则 $c s$ 就是 $a b, a c, a d, b c, b d, c d, . . .$ 。

对应的二进制数为：

观察到上述规律后，我们依次按照二进制编码从大到小的规律，将所有字符串依次求出。

所谓的长度 $c o m b i n a t i o n L e n g t h$ ，只需要满足二进制编码中 $1$ 的个数满足要求即可。

type CombinationIterator struct {
	curr int
	size int
	cs   []byte
}

func Constructor(characters string, combinationLength int) CombinationIterator {
	n := len(characters)
	curr := (1 << n) - 1
	size := combinationLength
	cs := make([]byte, n)
	for i := range characters {
		cs[n-i-1] = characters[i]
	}
	return CombinationIterator{curr, size, cs}
}

func (this *CombinationIterator) Next() string {
	for this.curr >= 0 && bits.OnesCount(uint(this.curr)) != this.size {
		this.curr--
	}
	ans := []byte{}
	for i := range this.cs {
		if (this.curr >> i & 1) == 1 {
			ans = append(ans, this.cs[i])
		}
	}
	for i, j := 0, len(ans)-1; i < j; i, j = i+1, j-1 {
		ans[i], ans[j] = ans[j], ans[i]
	}
	this.curr--
	return string(ans)
}

func (this *CombinationIterator) HasNext() bool {
	for this.curr >= 0 && bits.OnesCount(uint(this.curr)) != this.size {
		this.curr--
	}
	return this.curr >= 0
}

/**
 * Your CombinationIterator object will be instantiated and called as such:
 * obj := Constructor(characters, combinationLength);
 * param_1 := obj.Next();
 * param_2 := obj.HasNext();
 */

力扣原题 · Doocs 题解来源

1348. 推文计数

中等1 种解法

标签：设计、哈希表、字符串、二分查找、有序集合、排序

题目、示例与约束

一家社交媒体公司正试图通过分析特定时间段内出现的推文数量来监控其网站上的活动。这些时间段可以根据特定的频率（ 每分钟 、每小时 或 每一天 ）划分为更小的 时间段 。

例如，周期 [10,10000] （以秒为单位）将被划分为以下频率的 时间块 :

每分钟 (60秒块)： [10,69], [70,129], [130,189], ..., [9970,10000]
每小时 (3600秒块)：[10,3609], [3610,7209], [7210,10000]
每天 (86400秒块)： [10,10000]

注意，最后一个块可能比指定频率的块大小更短，并且总是以时间段的结束时间结束(在上面的示例中为 10000 )。

设计和实现一个API来帮助公司进行分析。

实现 TweetCounts 类:

TweetCounts() 初始化 TweetCounts 对象。
存储记录时间的 tweetName (以秒为单位)。
List<integer> getTweetCountsPerFrequency(String freq, String tweetName, int startTime, int endTime) 返回一个整数列表，表示给定时间 [startTime, endTime] （单位秒）和频率频率中，每个 时间块 中带有 tweetName 的 tweet 的数量。
- freq 是 “minute” 、 “hour” 或 “day” 中的一个，分别表示 每分钟 、 每小时 或 每一天 的频率。

示例：

输入：
["TweetCounts","recordTweet","recordTweet","recordTweet","getTweetCountsPerFrequency","getTweetCountsPerFrequency","recordTweet","getTweetCountsPerFrequency"]
[[],["tweet3",0],["tweet3",60],["tweet3",10],["minute","tweet3",0,59],["minute","tweet3",0,60],["tweet3",120],["hour","tweet3",0,210]]

输出：
[null,null,null,null,[2],[2,1],null,[4]]

解释：
TweetCounts tweetCounts = new TweetCounts();
tweetCounts.recordTweet("tweet3", 0);
tweetCounts.recordTweet("tweet3", 60);
tweetCounts.recordTweet("tweet3", 10);                             // "tweet3" 发布推文的时间分别是 0, 10 和 60 。
tweetCounts.getTweetCountsPerFrequency("minute", "tweet3", 0, 59); // 返回 [2]。统计频率是每分钟（60 秒），因此只有一个有效时间间隔 [0,60> - > 2 条推文。
tweetCounts.getTweetCountsPerFrequency("minute", "tweet3", 0, 60); // 返回 [2,1]。统计频率是每分钟（60 秒），因此有两个有效时间间隔 1) [0,60> - > 2 条推文，和 2) [60,61> - > 1 条推文。 
tweetCounts.recordTweet("tweet3", 120);                            // "tweet3" 发布推文的时间分别是 0, 10, 60 和 120 。
tweetCounts.getTweetCountsPerFrequency("hour", "tweet3", 0, 210);  // 返回 [4]。统计频率是每小时（3600 秒），因此只有一个有效时间间隔 [0,211> - > 4 条推文。

提示：

0 <= time, startTime, endTime <= 10⁹
0 <= endTime - startTime <= 10⁴
recordTweet 和 getTweetCountsPerFrequency，最多有 10⁴ 次操作。

方法一：Go 解法（本站整理） · Go 实现

Doocs 参考题解 · CC BY-SA 4.0

基于 Doocs 参考改写：沿用 Python「用户哈希表 + 有序时间表 + 分桶二分」方法。标准库没有 SortedList，因此用排序切片保存每个名字的全部时间，RecordTweet 二分定位并移动尾部插入，保留重复时间。查询按频率切成左闭右开区间，使用两次二分得到每个区间的记录数，最后一桶截到 endTime+1。

变量与复杂度：T 为该名字已有记录数，B=⌊(endTime−startTime)/频率⌋+1 为桶数，总记录数为 N。插入 O(T)（切片移动，不误称 O(log T)），查询 O(B log(T+1))，存储 O(N)，查询结果空间 O(B)。总操作≤10⁴，插入最坏累计约 5·10⁷ 个整数移动；查询时间跨度≤10⁴，分钟桶数≤167，满足约束。

平台接口：Constructor() TweetCounts，RecordTweet(tweetName string, time int)，GetTweetCountsPerFrequency(freq, tweetName string, startTime, endTime int) []int。该题为顺序设计题，不要求并发调用。

出处与许可：基于 Doocs 原题及参考资料，固定提交 91ef8c241a5eaabf96f9ca8d45cfb1a338bcb011；Go 代码及本说明按 CC BY-SA 4.0 共享。

// 依据 Doocs/leetcode 题目与参考资料进行 Go 改写/整理。
// 来源：https://github.com/doocs/leetcode/blob/91ef8c241a5eaabf96f9ca8d45cfb1a338bcb011/solution/1300-1399/1348.Tweet%20Counts%20Per%20Frequency/README.md
// 许可：CC BY-SA 4.0，https://creativecommons.org/licenses/by-sa/4.0/

import "sort"

type TweetCounts struct{ times map[string][]int }

func Constructor() TweetCounts { return TweetCounts{times: map[string][]int{}} }
func (t *TweetCounts) RecordTweet(tweetName string, time int) {
	a := t.times[tweetName]
	i := sort.SearchInts(a, time)
	a = append(a, 0)
	copy(a[i+1:], a[i:])
	a[i] = time
	t.times[tweetName] = a
}
func (t *TweetCounts) GetTweetCountsPerFrequency(freq, tweetName string, startTime, endTime int) []int {
	width := 60
	switch freq {
	case "hour":
		width = 3600
	case "day":
		width = 86400
	}
	a := t.times[tweetName]
	answer := make([]int, (endTime-startTime)/width+1)
	for i := range answer {
		lo := startTime + i*width
		hi := lo + width
		if hi > endTime+1 {
			hi = endTime + 1
		}
		answer[i] = sort.SearchInts(a, hi) - sort.SearchInts(a, lo)
	}
	return answer
}

力扣原题 · Doocs 题解来源

1352. 最后 K 个数的乘积

中等1 种解法

标签：设计、数组、数学、数据流、前缀和

题目、示例与约束

设计一个算法，该算法接受一个整数流并检索该流中最后 k 个整数的乘积。

实现 ProductOfNumbers 类：

ProductOfNumbers() 用一个空的流初始化对象。
void add(int num) 将数字 num 添加到当前数字列表的最后面。
int getProduct(int k) 返回当前数字列表中，最后 k 个数字的乘积。你可以假设当前列表中始终至少包含 k 个数字。

题目数据保证：任何时候，任一连续数字序列的乘积都在 32 位整数范围内，不会溢出。

示例：

输入：
["ProductOfNumbers","add","add","add","add","add","getProduct","getProduct","getProduct","add","getProduct"]
[[],[3],[0],[2],[5],[4],[2],[3],[4],[8],[2]]

输出：
[null,null,null,null,null,null,20,40,0,null,32]

解释：
ProductOfNumbers productOfNumbers = new ProductOfNumbers();
productOfNumbers.add(3);        // [3]
productOfNumbers.add(0);        // [3,0]
productOfNumbers.add(2);        // [3,0,2]
productOfNumbers.add(5);        // [3,0,2,5]
productOfNumbers.add(4);        // [3,0,2,5,4]
productOfNumbers.getProduct(2); // 返回 20 。最后 2 个数字的乘积是 5 * 4 = 20
productOfNumbers.getProduct(3); // 返回 40 。最后 3 个数字的乘积是 2 * 5 * 4 = 40
productOfNumbers.getProduct(4); // 返回  0 。最后 4 个数字的乘积是 0 * 2 * 5 * 4 = 0
productOfNumbers.add(8);        // [3,0,2,5,4,8]
productOfNumbers.getProduct(2); // 返回 32 。最后 2 个数字的乘积是 4 * 8 = 32

提示：

0 <= num <= 100
1 <= k <= 4 * 10⁴
add 和 getProduct 最多被调用 4 * 10⁴ 次。
在任何时间点流的乘积都在 32 位整数范围内。

进阶：您能否同时将 GetProduct 和 Add 的实现改为 O(1) 时间复杂度，而不是 O(k) 时间复杂度？

方法一：前缀积 · Go 实现

思考

动态追加数字并查询末尾 $k$ 个的积。每次重乘是 $O (k)$ ，调用可达 $4 \times 10^{4}$ 。前缀积使区间积变成两次取值相除。遇到 $0$ 时其后任何含该 $0$ 的积都是 $0$ ，因此把前缀重置为 $[1]$ ，查询时若长度不足 $k$ 则说明窗口里有 $0$ 。

我们初始化一个数组 $s$ ，其中 $s [i]$ 表示前 $i$ 个数字的乘积。

当调用 add(num) 时，我们判断 num 是否为 $0$ ，若是，则将 $s$ 置为 [1]，否则将 $s$ 的最后一个元素乘以 num，并将结果添加到 $s$ 的末尾。

当调用 getProduct(k) 时，此时判断 $s$ 的长度是否小于等于 $k$ ，若是，则返回 $0$ ，否则返回 $s$ 的最后一个元素除以 $s$ 的倒数第 $k + 1$ 个元素。即 $s [- 1] / s [- k - 1]$ 。

时间复杂度 $O (1)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为调用 add 的次数。

type ProductOfNumbers struct {
	s []int
}

func Constructor() ProductOfNumbers {
	return ProductOfNumbers{[]int{1}}
}

func (this *ProductOfNumbers) Add(num int) {
	if num == 0 {
		this.s = []int{1}
		return
	}
	this.s = append(this.s, this.s[len(this.s)-1]*num)
}

func (this *ProductOfNumbers) GetProduct(k int) int {
	n := len(this.s)
	if n <= k {
		return 0
	}
	return this.s[len(this.s)-1] / this.s[len(this.s)-k-1]
}

/**
 * Your ProductOfNumbers object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Add(num);
 * param_2 := obj.GetProduct(k);
 */

力扣原题 · Doocs 题解来源

1357. 每隔 n 个顾客打折

中等1 种解法

标签：设计、数组、哈希表

题目、示例与约束

超市里正在举行打折活动，每隔 n 个顾客会得到 discount 的折扣。

超市里有一些商品，第 i 种商品为 products[i] 且每件单品的价格为 prices[i] 。

结账系统会统计顾客的数目，每隔 n 个顾客结账时，该顾客的账单都会打折，折扣为 discount （也就是如果原本账单为 x ，那么实际金额会变成 x - (discount * x) / 100 ），然后系统会重新开始计数。

顾客会购买一些商品， product[i] 是顾客购买的第 i 种商品， amount[i] 是对应的购买该种商品的数目。

请你实现 Cashier 类：

Cashier(int n, int discount, int[] products, int[] prices) 初始化实例对象，参数分别为打折频率 n ，折扣大小 discount ，超市里的商品列表 products 和它们的价格 prices 。
double getBill(int[] product, int[] amount) 返回账单的实际金额（如果有打折，请返回打折后的结果）。返回结果与标准答案误差在 10^-5 以内都视为正确结果。

示例 1：

输入
["Cashier","getBill","getBill","getBill","getBill","getBill","getBill","getBill"]
[[3,50,[1,2,3,4,5,6,7],[100,200,300,400,300,200,100]],[[1,2],[1,2]],[[3,7],[10,10]],[[1,2,3,4,5,6,7],[1,1,1,1,1,1,1]],[[4],[10]],[[7,3],[10,10]],[[7,5,3,1,6,4,2],[10,10,10,9,9,9,7]],[[2,3,5],[5,3,2]]]
输出
[null,500.0,4000.0,800.0,4000.0,4000.0,7350.0,2500.0]
解释
Cashier cashier = new Cashier(3,50,[1,2,3,4,5,6,7],[100,200,300,400,300,200,100]);
cashier.getBill([1,2],[1,2]);                        // 返回 500.0, 账单金额为 = 1 * 100 + 2 * 200 = 500.
cashier.getBill([3,7],[10,10]);                      // 返回 4000.0
cashier.getBill([1,2,3,4,5,6,7],[1,1,1,1,1,1,1]);    // 返回 800.0 ，账单原本为 1600.0 ，但由于该顾客是第三位顾客，他将得到 50% 的折扣，所以实际金额为 1600 - 1600 * (50 / 100) = 800 。
cashier.getBill([4],[10]);                           // 返回 4000.0
cashier.getBill([7,3],[10,10]);                      // 返回 4000.0
cashier.getBill([7,5,3,1,6,4,2],[10,10,10,9,9,9,7]); // 返回 7350.0 ，账单原本为 14700.0 ，但由于系统计数再次达到三，该顾客将得到 50% 的折扣，实际金额为 7350.0 。
cashier.getBill([2,3,5],[5,3,2]);                    // 返回 2500.0

提示：

1 <= n <= 10^4
0 <= discount <= 100
1 <= products.length <= 200
1 <= products[i] <= 200
products 列表中不会有重复的元素。
prices.length == products.length
1 <= prices[i] <= 1000
1 <= product.length <= products.length
product[i] 在 products 出现过。
amount.length == product.length
1 <= amount[i] <= 1000
最多有 1000 次对 getBill 函数的调用。
返回结果与标准答案误差在 10^-5 以内都视为正确结果。

方法一：哈希表 + 模拟 · Go 实现

思考

第 $n, 2 n, \dots$ 位顾客整单打折，其余原价。商品编号到单价是静态映射，用哈希表在初始化时一次建好。计数器对 $n$ 取模，模为 $0$ 时对账单乘折扣，否则原样返回。

我们使用哈希表 $d$ 存储每件商品的编号和单价，在初始化时将 products 和 prices 一一对应存入哈希表。

同时维护一个顾客计数器 $i$ ，初始值为 $0$ 。

对于 getBill 操作：

将计数器加一并取模： $i = (i + 1) mod n$ ，表示当前是第几位顾客结账；
遍历本次购买的商品编号和数量，计算账单总额 $x = \sum_{j} d [product [j]] \times amount [j]$ ；
若 $i = 0$ ，说明当前顾客是第 $n$ 位顾客，应对整单打折，返回 $x - \frac{discount \times x}{100}$ ；否则直接返回 $x$ 。

初始化的时间复杂度为 $O (n)$ ，其中 $n$ 为商品种类数。每次 getBill 的时间复杂度为 $O (m)$ ，其中 $m$ 为本次购买商品的种类数。空间复杂度为 $O (n)$ 。

type Cashier struct {
	i        int
	n        int
	discount int
	d        map[int]int
}

func Constructor(n int, discount int, products []int, prices []int) Cashier {
	d := make(map[int]int)
	for i := 0; i < len(products); i++ {
		d[products[i]] = prices[i]
	}
	return Cashier{i: 0, n: n, discount: discount, d: d}
}

func (this *Cashier) GetBill(product []int, amount []int) float64 {
	this.i = (this.i + 1) % this.n
	x := 0
	for i := 0; i < len(product); i++ {
		x += this.d[product[i]] * amount[i]
	}
	if this.i == 0 {
		return float64(x) - float64(this.discount)*float64(x)/100.0
	}
	return float64(x)
}

/**
 * Your Cashier object will be instantiated and called as such:
 * obj := Constructor(n, discount, products, prices);
 * param_1 := obj.GetBill(product,amount);
 */

力扣原题 · Doocs 题解来源

1381. 设计一个支持增量操作的栈

中等1 种解法

标签：栈、设计、数组

题目、示例与约束

请你设计一个支持对其元素进行增量操作的栈。

实现自定义栈类 CustomStack ：

CustomStack(int maxSize)：用 maxSize 初始化对象，maxSize 是栈中最多能容纳的元素数量。
void push(int x)：如果栈还未增长到 maxSize ，就将 x 添加到栈顶。
int pop()：弹出栈顶元素，并返回栈顶的值，或栈为空时返回 -1 。
void inc(int k, int val)：栈底的 k 个元素的值都增加 val 。如果栈中元素总数小于 k ，则栈中的所有元素都增加 val 。

示例：

输入：
["CustomStack","push","push","pop","push","push","push","increment","increment","pop","pop","pop","pop"]
[[3],[1],[2],[],[2],[3],[4],[5,100],[2,100],[],[],[],[]]
输出：
[null,null,null,2,null,null,null,null,null,103,202,201,-1]
解释：
CustomStack stk = new CustomStack(3); // 栈是空的 []
stk.push(1);                          // 栈变为 [1]
stk.push(2);                          // 栈变为 [1, 2]
stk.pop();                            // 返回 2 --> 返回栈顶值 2，栈变为 [1]
stk.push(2);                          // 栈变为 [1, 2]
stk.push(3);                          // 栈变为 [1, 2, 3]
stk.push(4);                          // 栈仍然是 [1, 2, 3]，不能添加其他元素使栈大小变为 4
stk.increment(5, 100);                // 栈变为 [101, 102, 103]
stk.increment(2, 100);                // 栈变为 [201, 202, 103]
stk.pop();                            // 返回 103 --> 返回栈顶值 103，栈变为 [201, 202]
stk.pop();                            // 返回 202 --> 返回栈顶值 202，栈变为 [201]
stk.pop();                            // 返回 201 --> 返回栈顶值 201，栈变为 []
stk.pop();                            // 返回 -1 --> 栈为空，返回 -1

提示：

1 <= maxSize, x, k <= 1000
0 <= val <= 100
每种方法 increment，push 以及 pop 分别最多调用 1000 次

方法一：数组模拟 · Go 实现

思考

$increment$ 要把栈底 $k$ 个元素都加 $val$ 。若每次扫描栈内，三种操作各 $10^{3}$ 次尚可，但可以做到 $O (1)$ ：差分数组 $add [i]$ 表示位置 $i$ 及以下应加的增量。增量记在第 $min (k, size) - 1$ 位；弹出时把该位增量传给下一层并清零，使懒标记随出栈下沉。

我们可以用一个数组 $s t k$ 来模拟栈，用一个整数 $i$ 表示下一个入栈的元素位置。另外，我们还需要一个数组 $a d d$ 来记录每个位置上的增量累加值。

调用 $p u s h (x)$ 时，如果 $i < m a x S i z e$ ，我们将 $x$ 放入 $s t k [i]$ 中，并将 $i$ 加一。

调用 $p o p ()$ 时，如果 $i \leq 0$ ，说明栈为空，返回 $- 1$ 。否则我们将 $i$ 减一，答案为 $s t k [i] + a d d [i]$ ，然后我们将 $a d d [i - 1]$ 加上 $a d d [i]$ ，并将 $a d d [i]$ 清零。最后返回答案。

调用 $i n c r e m e n t (k, v a l)$ 时，如果 $i > 0$ ，我们将 $a d d [min (i, k) - 1]$ 加上 $v a l$ 。

时间复杂度 $O (1)$ ，空间复杂度 $O (n)$ 。其中 $n$ 是栈的最大容量。

type CustomStack struct {
	stk []int
	add []int
	i   int
}

func Constructor(maxSize int) CustomStack {
	return CustomStack{make([]int, maxSize), make([]int, maxSize), 0}
}

func (this *CustomStack) Push(x int) {
	if this.i < len(this.stk) {
		this.stk[this.i] = x
		this.i++
	}
}

func (this *CustomStack) Pop() int {
	if this.i <= 0 {
		return -1
	}
	this.i--
	ans := this.stk[this.i] + this.add[this.i]
	if this.i > 0 {
		this.add[this.i-1] += this.add[this.i]
	}
	this.add[this.i] = 0
	return ans
}

func (this *CustomStack) Increment(k int, val int) {
	if this.i > 0 {
		this.add[min(k, this.i)-1] += val
	}
}

/**
 * Your CustomStack object will be instantiated and called as such:
 * obj := Constructor(maxSize);
 * obj.Push(x);
 * param_2 := obj.Pop();
 * obj.Increment(k,val);
 */

力扣原题 · Doocs 题解来源

1396. 设计地铁系统

中等1 种解法

标签：设计、哈希表、字符串

题目、示例与约束

地铁系统跟踪不同车站之间的乘客出行时间，并使用这一数据来计算从一站到另一站的平均时间。

实现 UndergroundSystem 类：

void checkIn(int id, string stationName, int t)
- 通行卡 ID 等于 id 的乘客，在时间 t ，从 stationName 站进入
- 乘客一次只能从一个站进入
void checkOut(int id, string stationName, int t)
- 通行卡 ID 等于 id 的乘客，在时间 t ，从 stationName 站离开
double getAverageTime(string startStation, string endStation)
- 返回从 startStation 站到 endStation 站的平均时间
- 平均时间会根据截至目前所有从 startStation 站直接到达 endStation 站的行程进行计算，也就是从 startStation 站进入并从 endStation 离开的行程
- 从 startStation 到 endStation 的行程时间与从 endStation 到 startStation 的行程时间可能不同
- 在调用 getAverageTime 之前，至少有一名乘客从 startStation 站到达 endStation 站

你可以假设对 checkIn 和 checkOut 方法的所有调用都是符合逻辑的。如果一名乘客在时间 t₁ 进站、时间 t₂ 出站，那么 t₁ < t₂ 。所有时间都按时间顺序发生。

示例 1：

输入
["UndergroundSystem","checkIn","checkIn","checkIn","checkOut","checkOut","checkOut","getAverageTime","getAverageTime","checkIn","getAverageTime","checkOut","getAverageTime"]
[[],[45,"Leyton",3],[32,"Paradise",8],[27,"Leyton",10],[45,"Waterloo",15],[27,"Waterloo",20],[32,"Cambridge",22],["Paradise","Cambridge"],["Leyton","Waterloo"],[10,"Leyton",24],["Leyton","Waterloo"],[10,"Waterloo",38],["Leyton","Waterloo"]]

输出
[null,null,null,null,null,null,null,14.00000,11.00000,null,11.00000,null,12.00000]

解释
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(45, "Leyton", 3);
undergroundSystem.checkIn(32, "Paradise", 8);
undergroundSystem.checkIn(27, "Leyton", 10);
undergroundSystem.checkOut(45, "Waterloo", 15);  // 乘客 45 "Leyton" -> "Waterloo" ，用时 15-3 = 12
undergroundSystem.checkOut(27, "Waterloo", 20);  // 乘客 27 "Leyton" -> "Waterloo" ，用时 20-10 = 10
undergroundSystem.checkOut(32, "Cambridge", 22); // 乘客 32 "Paradise" -> "Cambridge" ，用时 22-8 = 14
undergroundSystem.getAverageTime("Paradise", "Cambridge"); // 返回 14.00000 。只有一个 "Paradise" -> "Cambridge" 的行程，(14) / 1 = 14
undergroundSystem.getAverageTime("Leyton", "Waterloo");    // 返回 11.00000 。有两个 "Leyton" -> "Waterloo" 的行程，(10 + 12) / 2 = 11
undergroundSystem.checkIn(10, "Leyton", 24);
undergroundSystem.getAverageTime("Leyton", "Waterloo");    // 返回 11.00000
undergroundSystem.checkOut(10, "Waterloo", 38);  // 乘客 10 "Leyton" -> "Waterloo" ，用时 38-24 = 14
undergroundSystem.getAverageTime("Leyton", "Waterloo");    // 返回 12.00000 。有三个 "Leyton" -> "Waterloo" 的行程，(10 + 12 + 14) / 3 = 12

示例 2：

输入
["UndergroundSystem","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime"]
[[],[10,"Leyton",3],[10,"Paradise",8],["Leyton","Paradise"],[5,"Leyton",10],[5,"Paradise",16],["Leyton","Paradise"],[2,"Leyton",21],[2,"Paradise",30],["Leyton","Paradise"]]

输出
[null,null,null,5.00000,null,null,5.50000,null,null,6.66667]

解释
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(10, "Leyton", 3);
undergroundSystem.checkOut(10, "Paradise", 8); // 乘客 10 "Leyton" -> "Paradise" ，用时 8-3 = 5
undergroundSystem.getAverageTime("Leyton", "Paradise"); // 返回 5.00000 ，(5) / 1 = 5
undergroundSystem.checkIn(5, "Leyton", 10);
undergroundSystem.checkOut(5, "Paradise", 16); // 乘客 5 "Leyton" -> "Paradise" ，用时 16-10 = 6
undergroundSystem.getAverageTime("Leyton", "Paradise"); // 返回 5.50000 ，(5 + 6) / 2 = 5.5
undergroundSystem.checkIn(2, "Leyton", 21);
undergroundSystem.checkOut(2, "Paradise", 30); // 乘客 2 "Leyton" -> "Paradise" ，用时 30-21 = 9
undergroundSystem.getAverageTime("Leyton", "Paradise"); // 返回 6.66667 ，(5 + 6 + 9) / 3 = 6.66667

提示：

1 <= id, t <= 10⁶
1 <= stationName.length, startStation.length, endStation.length <= 10
所有字符串由大小写英文字母与数字组成
总共最多调用 checkIn、checkOut 和 getAverageTime 方法 2 * 10⁴ 次
与标准答案误差在 10^-5 以内的结果都被视为正确结果

方法一：哈希表 · Go 实现

思考

进站、出站、查询两站平均耗时，均需 $O (1)$ 。用 $id$ 映射到进站时刻与站名；出站时把耗时累加到 $(start, end)$ 对应的（总时间，次数）。查询即相除。

我们用两个哈希表来存储数据，其中：

ts：存储乘客的 id 和乘客的进站时间和进站站点。其中键为乘客的 id，值为元组 (t, stationName)。
d：存储乘客的进站站点和出站站点，以及乘客的行程时间和行程次数。其中键为元组 (startStation, endStation)，值为元组 (totalTime, count)。

当乘客进站时，我们将乘客的 id 和进站时间和进站站点存入 ts 中，即 ts[id] = (t, stationName)。

当乘客出站时，我们从 ts 中取出乘客的进站时间和进站站点 (t0, station)，然后计算乘客的行程时间 $t - t_{0}$ ，并将乘客的行程时间和行程次数存入 d 中。

当我们要求某个乘客的平均行程时间时，我们从 d 中取出乘客的行程时间和行程次数 (totalTime, count)，然后计算平均行程时间 $t o t a l T i m e / c o u n t$ 即可。

时间复杂度 $O (1)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为乘客的数量。

type UndergroundSystem struct {
	ts map[int]pair
	d  map[station][2]int
}

func Constructor() UndergroundSystem {
	return UndergroundSystem{
		ts: make(map[int]pair),
		d:  make(map[station][2]int),
	}
}

func (this *UndergroundSystem) CheckIn(id int, stationName string, t int) {
	this.ts[id] = pair{t, stationName}
}

func (this *UndergroundSystem) CheckOut(id int, stationName string, t int) {
	p := this.ts[id]
	s := station{p.a, stationName}
	if _, ok := this.d[s]; !ok {
		this.d[s] = [2]int{t - p.t, 1}
	} else {
		this.d[s] = [2]int{this.d[s][0] + t - p.t, this.d[s][1] + 1}
	}

}

func (this *UndergroundSystem) GetAverageTime(startStation string, endStation string) float64 {
	s := station{startStation, endStation}
	return float64(this.d[s][0]) / float64(this.d[s][1])
}

type station struct {
	a string
	b string
}

type pair struct {
	t int
	a string
}

/**
 * Your UndergroundSystem object will be instantiated and called as such:
 * obj := Constructor();
 * obj.CheckIn(id,stationName,t);
 * obj.CheckOut(id,stationName,t);
 * param_3 := obj.GetAverageTime(startStation,endStation);
 */

力扣原题 · Doocs 题解来源

1429. 第一个唯一数字 🔒

中等1 种解法

标签：设计、队列、数组、哈希表、数据流

题目、示例与约束

给定一系列整数，插入一个队列中，找出队列中第一个唯一整数。

实现 FirstUnique 类：

FirstUnique(int[] nums) 用数组里的数字初始化队列。
int showFirstUnique() 返回队列中的 第一个唯一 整数的值。如果没有唯一整数，返回 -1。（译者注：此方法不移除队列中的任何元素）
void add(int value) 将 value 插入队列中。

示例 1：

输入：
["FirstUnique","showFirstUnique","add","showFirstUnique","add","showFirstUnique","add","showFirstUnique"]
[[[2,3,5]],[],[5],[],[2],[],[3],[]]
输出：
[null,2,null,2,null,3,null,-1]
解释：
FirstUnique firstUnique = new FirstUnique([2,3,5]);
firstUnique.showFirstUnique(); // 返回 2
firstUnique.add(5);            // 此时队列为 [2,3,5,5]
firstUnique.showFirstUnique(); // 返回 2
firstUnique.add(2);            // 此时队列为 [2,3,5,5,2]
firstUnique.showFirstUnique(); // 返回 3
firstUnique.add(3);            // 此时队列为 [2,3,5,5,2,3]
firstUnique.showFirstUnique(); // 返回 -1

示例 2：

输入：
["FirstUnique","showFirstUnique","add","add","add","add","add","showFirstUnique"]
[[[7,7,7,7,7,7]],[],[7],[3],[3],[7],[17],[]]
输出：
[null,-1,null,null,null,null,null,17]
解释：
FirstUnique firstUnique = new FirstUnique([7,7,7,7,7,7]);
firstUnique.showFirstUnique(); // 返回 -1
firstUnique.add(7);            // 此时队列为 [7,7,7,7,7,7,7]
firstUnique.add(3);            // 此时队列为 [7,7,7,7,7,7,7,3]
firstUnique.add(3);            // 此时队列为 [7,7,7,7,7,7,7,3,3]
firstUnique.add(7);            // 此时队列为 [7,7,7,7,7,7,7,3,3,7]
firstUnique.add(17);           // 此时队列为 [7,7,7,7,7,7,7,3,3,7,17]
firstUnique.showFirstUnique(); // 返回 17

示例 3：

输入：
["FirstUnique","showFirstUnique","add","showFirstUnique"]
[[[809]],[],[809],[]]
输出：
[null,809,null,-1]
解释：
FirstUnique firstUnique = new FirstUnique([809]);
firstUnique.showFirstUnique(); // 返回 809
firstUnique.add(809);          // 此时队列为 [809,809]
firstUnique.showFirstUnique(); // 返回 -1

提示：

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^8
1 <= value <= 10^8
最多调用 5000 次 showFirstUnique 和 add 。

方法一：哈希表 + 双端队列 · Go 实现

思考

需要在多次 add 后仍能 $O (1)$ 回答「最早出现且只出现一次的数」。仅用计数器无法保留出现顺序，仅用队列则删除中间重复元素不便。

计数器记录频次，OrderedDict 按首次成为唯一的顺序保存当前频次为 $1$ 的键。add 时若频次变为 $1$ 则插入，变为 $2$ 则删除；showFirstUnique 取字典的第一个键。

我们可以使用哈希表 $c n t$ 统计每个数字出现的次数，使用双端队列 $q$ 按顺序维护出现的数字。

调用 showFirstUnique 方法时，判断队列 $q$ 的队头元素是否在哈希表 $c n t$ 中出现的次数是否为 $1$ ，如果是，则返回队头元素，否则将队头元素弹出，直到队列为空或者队头元素在哈希表 $c n t$ 中出现的次数为 $1$ ，如果队列为空，则返回 $- 1$ 。

调用 add 方法时，将数字加入哈希表 $c n t$ 中，并将数字加入队列 $q$ 中。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为数组 $n u m s$ 的长度。

type FirstUnique struct {
	cnt map[int]int
	q   []int
}

func Constructor(nums []int) FirstUnique {
	cnt := map[int]int{}
	for _, v := range nums {
		cnt[v]++
	}
	return FirstUnique{cnt, nums}
}

func (this *FirstUnique) ShowFirstUnique() int {
	for len(this.q) > 0 && this.cnt[this.q[0]] != 1 {
		this.q = this.q[1:]
	}
	if len(this.q) > 0 {
		return this.q[0]
	}
	return -1
}

func (this *FirstUnique) Add(value int) {
	this.cnt[value]++
	this.q = append(this.q, value)
}

/**
 * Your FirstUnique object will be instantiated and called as such:
 * obj := Constructor(nums);
 * param_1 := obj.ShowFirstUnique();
 * obj.Add(value);
 */

力扣原题 · Doocs 题解来源

1472. 设计浏览器历史记录

中等1 种解法

标签：栈、设计、数组、链表、数据流、双向链表

题目、示例与约束

你有一个只支持单个标签页的 浏览器 ，最开始你浏览的网页是 homepage ，你可以访问其他的网站 url ，也可以在浏览历史中后退 steps 步或前进 steps 步。

请你实现 BrowserHistory 类：

BrowserHistory(string homepage) ，用 homepage 初始化浏览器类。
void visit(string url) 从当前页跳转访问 url 对应的页面。执行此操作会把浏览历史前进的记录全部删除。
string back(int steps) 在浏览历史中后退 steps 步。如果你只能在浏览历史中后退至多 x 步且 steps > x ，那么你只后退 x 步。请返回后退至多 steps 步以后的 url 。
string forward(int steps) 在浏览历史中前进 steps 步。如果你只能在浏览历史中前进至多 x 步且 steps > x ，那么你只前进 x 步。请返回前进至多 steps步以后的 url 。

示例：

输入：
["BrowserHistory","visit","visit","visit","back","back","forward","visit","forward","back","back"]
[["leetcode.com"],["google.com"],["facebook.com"],["youtube.com"],[1],[1],[1],["linkedin.com"],[2],[2],[7]]
输出：
[null,null,null,null,"facebook.com","google.com","facebook.com",null,"linkedin.com","google.com","leetcode.com"]

解释：
BrowserHistory browserHistory = new BrowserHistory("leetcode.com");
browserHistory.visit("google.com");       // 你原本在浏览 "leetcode.com" 。访问 "google.com"
browserHistory.visit("facebook.com");     // 你原本在浏览 "google.com" 。访问 "facebook.com"
browserHistory.visit("youtube.com");      // 你原本在浏览 "facebook.com" 。访问 "youtube.com"
browserHistory.back(1);                   // 你原本在浏览 "youtube.com" ，后退到 "facebook.com" 并返回 "facebook.com"
browserHistory.back(1);                   // 你原本在浏览 "facebook.com" ，后退到 "google.com" 并返回 "google.com"
browserHistory.forward(1);                // 你原本在浏览 "google.com" ，前进到 "facebook.com" 并返回 "facebook.com"
browserHistory.visit("linkedin.com");     // 你原本在浏览 "facebook.com" 。 访问 "linkedin.com"
browserHistory.forward(2);                // 你原本在浏览 "linkedin.com" ，你无法前进任何步数。
browserHistory.back(2);                   // 你原本在浏览 "linkedin.com" ，后退两步依次先到 "facebook.com" ，然后到 "google.com" ，并返回 "google.com"
browserHistory.back(7);                   // 你原本在浏览 "google.com"， 你只能后退一步到 "leetcode.com" ，并返回 "leetcode.com"

提示：

1 <= homepage.length <= 20
1 <= url.length <= 20
1 <= steps <= 100
homepage 和 url 都只包含 '.' 或者小写英文字母。
最多调用 5000 次 visit， back 和 forward 函数。

方法一：双栈 · Go 实现

思考

visit 会丢掉前进历史，back/forward 在一条时间线上移动。用栈 $s t k 1$ 保存到当前页的路径， $s t k 2$ 保存前进页。访问新页时压入 $s t k 1$ 并清空 $s t k 2$ ；后退把页弹到 $s t k 2$ ，前进则反向弹回。

我们可以使用两个栈 $stk1$ 和 $stk2$ 分别存储浏览后退页面和前进页面。初始时 $stk1$ 包含 $homepage$ ，而 $stk2$ 为空。

调用 $visit (u r l)$ 时，我们将 $url$ 加入 $stk1$ ，并清空 $stk2$ 。时间复杂度 $O (1)$ 。

调用 $back (s t e p s)$ 时，我们将 $stk1$ 的栈顶元素弹出并加入 $stk2$ ，重复这一操作 $s t e p s$ 次，直到 $stk1$ 的长度为 $1$ 或者 $s t e p s$ 为 $0$ 。最后返回 $stk1$ 的栈顶元素。时间复杂度 $O (steps)$ 。

调用 $forward (s t e p s)$ 时，我们将 $stk2$ 的栈顶元素弹出并加入 $stk1$ ，重复这一操作 $s t e p s$ 次，直到 $stk2$ 为空或者 $s t e p s$ 为 $0$ 。最后返回 $stk1$ 的栈顶元素。时间复杂度 $O (steps)$ 。

空间复杂度 $O (n)$ ，其中 $n$ 是浏览历史记录的长度。

type BrowserHistory struct {
	stk1 []string
	stk2 []string
}

func Constructor(homepage string) BrowserHistory {
	t := BrowserHistory{[]string{}, []string{}}
	t.Visit(homepage)
	return t
}

func (this *BrowserHistory) Visit(url string) {
	this.stk1 = append(this.stk1, url)
	this.stk2 = []string{}
}

func (this *BrowserHistory) Back(steps int) string {
	for i := 0; i < steps && len(this.stk1) > 1; i++ {
		this.stk2 = append(this.stk2, this.stk1[len(this.stk1)-1])
		this.stk1 = this.stk1[:len(this.stk1)-1]
	}
	return this.stk1[len(this.stk1)-1]
}

func (this *BrowserHistory) Forward(steps int) string {
	for i := 0; i < steps && len(this.stk2) > 0; i++ {
		this.stk1 = append(this.stk1, this.stk2[len(this.stk2)-1])
		this.stk2 = this.stk2[:len(this.stk2)-1]
	}
	return this.stk1[len(this.stk1)-1]
}

/**
 * Your BrowserHistory object will be instantiated and called as such:
 * obj := Constructor(homepage);
 * obj.Visit(url);
 * param_2 := obj.Back(steps);
 * param_3 := obj.Forward(steps);
 */

力扣原题 · Doocs 题解来源

1476. 子矩形查询

中等1 种解法

标签：设计、数组、矩阵

题目、示例与约束

请你实现一个类 SubrectangleQueries ，它的构造函数的参数是一个 rows x cols 的矩形（这里用整数矩阵表示），并支持以下两种操作：

1. updateSubrectangle(int row1, int col1, int row2, int col2, int newValue)

用 newValue 更新以 (row1,col1) 为左上角且以 (row2,col2) 为右下角的子矩形。

2. getValue(int row, int col)

返回矩形中坐标 (row,col) 的当前值。

示例 1：

输入：
["SubrectangleQueries","getValue","updateSubrectangle","getValue","getValue","updateSubrectangle","getValue","getValue"]
[[[[1,2,1],[4,3,4],[3,2,1],[1,1,1]]],[0,2],[0,0,3,2,5],[0,2],[3,1],[3,0,3,2,10],[3,1],[0,2]]
输出：
[null,1,null,5,5,null,10,5]
解释：
SubrectangleQueries subrectangleQueries = new SubrectangleQueries([[1,2,1],[4,3,4],[3,2,1],[1,1,1]]);  
// 初始的 (4x3) 矩形如下：
// 1 2 1
// 4 3 4
// 3 2 1
// 1 1 1
subrectangleQueries.getValue(0, 2); // 返回 1
subrectangleQueries.updateSubrectangle(0, 0, 3, 2, 5);
// 此次更新后矩形变为：
// 5 5 5
// 5 5 5
// 5 5 5
// 5 5 5 
subrectangleQueries.getValue(0, 2); // 返回 5
subrectangleQueries.getValue(3, 1); // 返回 5
subrectangleQueries.updateSubrectangle(3, 0, 3, 2, 10);
// 此次更新后矩形变为：
// 5   5   5
// 5   5   5
// 5   5   5
// 10  10  10 
subrectangleQueries.getValue(3, 1); // 返回 10
subrectangleQueries.getValue(0, 2); // 返回 5

示例 2：

输入：
["SubrectangleQueries","getValue","updateSubrectangle","getValue","getValue","updateSubrectangle","getValue"]
[[[[1,1,1],[2,2,2],[3,3,3]]],[0,0],[0,0,2,2,100],[0,0],[2,2],[1,1,2,2,20],[2,2]]
输出：
[null,1,null,100,100,null,20]
解释：
SubrectangleQueries subrectangleQueries = new SubrectangleQueries([[1,1,1],[2,2,2],[3,3,3]]);
subrectangleQueries.getValue(0, 0); // 返回 1
subrectangleQueries.updateSubrectangle(0, 0, 2, 2, 100);
subrectangleQueries.getValue(0, 0); // 返回 100
subrectangleQueries.getValue(2, 2); // 返回 100
subrectangleQueries.updateSubrectangle(1, 1, 2, 2, 20);
subrectangleQueries.getValue(2, 2); // 返回 20

提示：

最多有 500 次updateSubrectangle 和 getValue 操作。
1 <= rows, cols <= 100
rows == rectangle.length
cols == rectangle[i].length
0 <= row1 <= row2 < rows
0 <= col1 <= col2 < cols
1 <= newValue, rectangle[i][j] <= 10^9
0 <= row < rows
0 <= col < cols

方法一 · Go 实现

思考

更新至多 $500$ 次，矩阵至多 $100 \times 100$ 。每次更新若改写子矩形，总写入可达 $500 \cdot 10^{4}$ 。改为只记录更新矩形，查询时从后往前找最先覆盖该格的更新，没有则返回原值。

type SubrectangleQueries struct {
	g   [][]int
	ops [][]int
}

func Constructor(rectangle [][]int) SubrectangleQueries {
	return SubrectangleQueries{rectangle, [][]int{}}
}

func (this *SubrectangleQueries) UpdateSubrectangle(row1 int, col1 int, row2 int, col2 int, newValue int) {
	this.ops = append(this.ops, []int{row1, col1, row2, col2, newValue})
}

func (this *SubrectangleQueries) GetValue(row int, col int) int {
	for i := len(this.ops) - 1; i >= 0; i-- {
		op := this.ops[i]
		if op[0] <= row && row <= op[2] && op[1] <= col && col <= op[3] {
			return op[4]
		}
	}
	return this.g[row][col]
}

/**
 * Your SubrectangleQueries object will be instantiated and called as such:
 * obj := Constructor(rectangle);
 * obj.UpdateSubrectangle(row1,col1,row2,col2,newValue);
 * param_2 := obj.GetValue(row,col);
 */

力扣原题 · Doocs 题解来源

1483. 树节点的第 K 个祖先

困难1 种解法

标签：位运算、树、深度优先搜索、广度优先搜索、设计、二分查找、动态规划

题目、示例与约束

给你一棵树，树上有 n 个节点，按从 0 到 n-1 编号。树以父节点数组的形式给出，其中 parent[i] 是节点 i 的父节点。树的根节点是编号为 0 的节点。

树节点的第 k 个祖先节点是从该节点到根节点路径上的第 k 个节点。

实现 TreeAncestor 类：

TreeAncestor（int n， int[] parent） 对树和父数组中的节点数初始化对象。
getKthAncestor(int node, int k) 返回节点 node 的第 k 个祖先节点。如果不存在这样的祖先节点，返回 -1 。

示例 1：

输入：
["TreeAncestor","getKthAncestor","getKthAncestor","getKthAncestor"]
[[7,[-1,0,0,1,1,2,2]],[3,1],[5,2],[6,3]]

输出：
[null,1,0,-1]

解释：
TreeAncestor treeAncestor = new TreeAncestor(7, [-1, 0, 0, 1, 1, 2, 2]);

treeAncestor.getKthAncestor(3, 1);  // 返回 1 ，它是 3 的父节点
treeAncestor.getKthAncestor(5, 2);  // 返回 0 ，它是 5 的祖父节点
treeAncestor.getKthAncestor(6, 3);  // 返回 -1 因为不存在满足要求的祖先节点

提示：

1 <= k <= n <= 5 * 10⁴
parent[0] == -1 表示编号为 0 的节点是根节点。
对于所有的 0 < i < n ，0 <= parent[i] < n 总成立
0 <= node < n
至多查询 5 * 10⁴ 次

方法一：动态规划 + 倍增 · Go 实现

思考

$n$ 与查询次数均为 $5 \times 10^{4}$ ，沿父指针走 $k$ 步单次可达 $O (n)$ 。预处理 $p [i] [j]$ 为 $i$ 向上 $2^{j}$ 步的祖先， $p [i] [j] = p [p [i] [j - 1]] [j - 1]$ 。

查询时按 $k$ 的二进制位跳跃，每位 $O (1)$ ，共 $O (\log n)$ 。

题目要我们寻找节点 $n o d e$ 的第 $k$ 个祖先节点，如果暴力求解，需要从 $n o d e$ 开始向上遍历 $k$ 次，时间复杂度为 $O (k)$ ，显然会超时。

我们可以使用动态规划，结合倍增的思想来处理。

我们定义 $p [i] [j]$ 表示节点 $i$ 的第 $2^{j}$ 个祖先节点，即 $p [i] [j]$ 表示节点 $i$ 向上走 $2^{j}$ 步的节点。那么我们可以得到状态转移方程：

p [i] [j] = p [p [i] [j - 1]] [j - 1]

即：要想找到节点 $i$ 的第 $2^{j}$ 个祖先节点，我们可以先找到节点 $i$ 的第 $2^{j - 1}$ 个祖先节点，然后再找到该节点的第 $2^{j - 1}$ 个祖先节点即可。所以，我们要找到每个节点的距离为 $2^{j}$ 的祖先节点，直到达到树的最大高度。

之后对于每次查询，我们可以把 $k$ 拆成二进制的表示形式，然后根据二进制中 $1$ 的位置，累计向上查询，最终得到节点 $n o d e$ 的第 $k$ 个祖先节点。

时间复杂度方面，初始化为 $O (n \times \log n)$ ，查询为 $O (\log n)$ 。空间复杂度 $O (n \times \log n)$ 。其中 $n$ 为树的节点数。

相似题目：

2836. 在传球游戏中最大化函数值

type TreeAncestor struct {
	p [][18]int
}

func Constructor(n int, parent []int) TreeAncestor {
	p := make([][18]int, n)
	for i, fa := range parent {
		p[i][0] = fa
		for j := 1; j < 18; j++ {
			p[i][j] = -1
		}
	}
	for j := 1; j < 18; j++ {
		for i := range p {
			if p[i][j-1] == -1 {
				continue
			}
			p[i][j] = p[p[i][j-1]][j-1]
		}
	}
	return TreeAncestor{p}
}

func (this *TreeAncestor) GetKthAncestor(node int, k int) int {
	for i := 17; i >= 0; i-- {
		if k>>i&1 == 1 {
			node = this.p[node][i]
			if node == -1 {
				break
			}
		}
	}
	return node
}

/**
 * Your TreeAncestor object will be instantiated and called as such:
 * obj := Constructor(n, parent);
 * param_1 := obj.GetKthAncestor(node,k);
 */

力扣原题 · Doocs 题解来源

1500. 设计文件分享系统 🔒

中等1 种解法

标签：设计、哈希表、数据流、排序、堆（优先队列）

题目、示例与约束

我们需要使用一套文件分享系统来分享一个非常大的文件，该文件由 m 个从 1 到 m 编号的 文件块 组成。

当用户加入系统时，系统应为其注册 一个独有 的 ID。这个独有的 ID 应当被相应的用户使用一次，但是当用户离开系统时，其 ID 应可以被（后续新注册的用户）再次使用。

用户可以请求文件中的某个指定的文件块，系统应当返回拥有这个文件块的所有用户的 ID。如果用户收到 ID 的非空列表，就表示成功接收到请求的文件块。

实现 FileSharing 类：

FileSharing(int m) 初始化该对象，文件有 m 个文件块。
int join(int[] ownedChunks)：一个新用户加入系统，并拥有文件的一些文件块。系统应当为该用户注册一个 ID，该 ID 应是未被其他用户占用的最小正整数。返回注册的 ID。
void leave(int userID)：ID 为 userID 的用户将离开系统，你不能再从该用户提取文件块了。
int[] request(int userID, int chunkID)：ID 为 userID 的用户请求编号为 chunkID 的文件块。返回拥有这个文件块的所有用户的 ID 所构成的列表或数组，按升序排列。

示例:

输入:
["FileSharing","join","join","join","request","request","leave","request","leave","join"]
[[4],[[1,2]],[[2,3]],[[4]],[1,3],[2,2],[1],[2,1],[2],[[]]]
输出:
[null,1,2,3,[2],[1,2],null,[],null,1]
解释:
FileSharing fileSharing = new FileSharing(4); // 我们用该系统分享由 4 个文件块组成的文件。

fileSharing.join([1, 2]);    // 一个拥有文件块 [1,2] 的用户加入系统，为其注册 id = 1 并返回 1。

fileSharing.join([2, 3]);    // 一个拥有文件块 [2,3] 的用户加入系统，为其注册 id = 2 并返回 2。

fileSharing.join([4]);       // 一个拥有文件块 [4] 的用户加入系统，为其注册 id = 3 并返回 3。

fileSharing.request(1, 3);   // id = 1 的用户请求第 3 个文件块，只有 id = 2 的用户拥有文件块，返回 [2] 。注意，现在用户 1 现拥有文件块 [1,2,3]。

fileSharing.request(2, 2);   // id = 2 的用户请求第 2 个文件块，id 为 [1,2] 的用户拥有该文件块，所以我们返回 [1,2] 。

fileSharing.leave(1);        // id = 1 的用户离开系统，其所拥有的所有文件块不再对其他用户可用。

fileSharing.request(2, 1);   // id = 2 的用户请求第 1 个文件块，系统中没有用户拥有该文件块，所以我们返回空列表 [] 。

fileSharing.leave(2);        // id = 2 的用户离开系统。

fileSharing.join([]);        // 一个不拥有任何文件块的用户加入系统，为其注册 id = 1 并返回 1 。注意，id 1 和 2 空闲，可以重新使用。

提示:

1 <= m <= 10⁵
0 <= ownedChunks.length <= min(100, m)
1 <= ownedChunks[i] <= m
ownedChunks 的值是互不相同的。
1 <= chunkID <= m
当你正确地注册用户 ID 时，题目保证 userID 是系统中的一个已注册用户。
join、 leave 和 request 最多被调用 10⁴ 次。
每次对 leave 的调用都有对应的对 join 的调用。

进阶：

当系统以用户的 IP 地址而不是独有 ID 来识别用户，且用户断开连接后以相同 IP 重新连接系统时，会发生什么？
当用户频繁加入并退出系统，且该用户不请求任何文件块时，你的解决方案仍然保持高效吗？
当所有用户同时加入系统，请求所有文件并离开时，你的解决方案仍然保持高效吗？
如果系统用于分享 n 个文件，其中第 i 个文件由 m[i] 组成，你需要如何修改？

方法一：Go 解法（本站整理） · Go 实现

Doocs 参考题解 · CC BY-SA 4.0

基于 Doocs 参考改写：沿用参考 Python 的递增新编号、小根堆复用离开编号，以及用户持有文件块集合。为避免每次请求扫描所有在线用户，另维护「块→持有者」的反向集合。Join 优先取堆顶最小空闲编号并建立双向关联；Leave 删除全部关联后回收编号；Request 先复制并排序当前持有者列表，仅当列表非空时将文件块加入请求者集合，返回的列表不包含此次新增持有关系。

变量与复杂度：U 为已分配过的编号数量，C 为当前用户持有块数，K 为被请求块的现有持有者数，A 为全部用户-块关联数。Join/Leave 为 O(C+log(U+1))，Request 为 O(K log(K+1))，对象空间 O(U+A)，返回列表 O(K)。小根堆使用标准库 container/heap，无第三方依赖。

平台接口：Constructor(m int) FileSharing，Join(ownedChunks []int) int，Leave(userID int)，Request(userID, chunkID int) []int。沿用题目对合法块号和已注册用户的保证，m 仅表示合法编号上界；空答案返回空切片。该题不要求并发。

出处与许可：基于 Doocs 原题及参考资料，固定提交 91ef8c241a5eaabf96f9ca8d45cfb1a338bcb011；Go 代码及本说明按 CC BY-SA 4.0 共享。

// 依据 Doocs/leetcode 题目与参考资料进行 Go 改写/整理。
// 来源：https://github.com/doocs/leetcode/blob/91ef8c241a5eaabf96f9ca8d45cfb1a338bcb011/solution/1500-1599/1500.Design%20a%20File%20Sharing%20System/README.md
// 许可：CC BY-SA 4.0，https://creativecommons.org/licenses/by-sa/4.0/

import (
	"container/heap"
	"sort"
)

type freeIDs []int

func (h freeIDs) Len() int            { return len(h) }
func (h freeIDs) Less(i, j int) bool  { return h[i] < h[j] }
func (h freeIDs) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *freeIDs) Push(v interface{}) { *h = append(*h, v.(int)) }
func (h *freeIDs) Pop() interface{}   { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }

type FileSharing struct {
	next   int
	free   freeIDs
	users  map[int]map[int]bool
	owners map[int]map[int]bool
}

func Constructor(m int) FileSharing {
	return FileSharing{next: 1, users: map[int]map[int]bool{}, owners: map[int]map[int]bool{}}
}
func (f *FileSharing) add(user, chunk int) {
	f.users[user][chunk] = true
	if f.owners[chunk] == nil {
		f.owners[chunk] = map[int]bool{}
	}
	f.owners[chunk][user] = true
}
func (f *FileSharing) Join(ownedChunks []int) int {
	id := f.next
	if len(f.free) > 0 {
		id = heap.Pop(&f.free).(int)
	} else {
		f.next++
	}
	f.users[id] = map[int]bool{}
	for _, chunk := range ownedChunks {
		f.add(id, chunk)
	}
	return id
}
func (f *FileSharing) Leave(userID int) {
	for chunk := range f.users[userID] {
		delete(f.owners[chunk], userID)
		if len(f.owners[chunk]) == 0 {
			delete(f.owners, chunk)
		}
	}
	delete(f.users, userID)
	heap.Push(&f.free, userID)
}
func (f *FileSharing) Request(userID, chunkID int) []int {
	answer := make([]int, 0, len(f.owners[chunkID]))
	for user := range f.owners[chunkID] {
		answer = append(answer, user)
	}
	sort.Ints(answer)
	if len(answer) > 0 {
		f.add(userID, chunkID)
	}
	return answer
}

力扣原题 · Doocs 题解来源

1570. 两个稀疏向量的点积 🔒

中等1 种解法

标签：设计、数组、哈希表、双指针、线性代数

题目、示例与约束

给定两个稀疏向量，计算它们的点积（数量积）。

实现类 SparseVector：

SparseVector(nums) 以向量 nums 初始化对象。
dotProduct(vec) 计算此向量与 vec 的点积。

稀疏向量 是指绝大多数分量为 0 的向量。你需要高效地存储这个向量，并计算两个稀疏向量的点积。

进阶：当其中只有一个向量是稀疏向量时，你该如何解决此问题？

示例 1：

输入：nums1 = [1,0,0,2,3], nums2 = [0,3,0,4,0]
输出：8
解释：v1 = SparseVector(nums1) , v2 = SparseVector(nums2)
v1.dotProduct(v2) = 1*0 + 0*3 + 0*0 + 2*4 + 3*0 = 8

示例 2：

输入：nums1 = [0,1,0,0,0], nums2 = [0,0,0,0,2]
输出：0
解释：v1 = SparseVector(nums1) , v2 = SparseVector(nums2)
v1.dotProduct(v2) = 0*0 + 1*0 + 0*0 + 0*0 + 0*2 = 0

示例 3：

输入：nums1 = [0,1,0,0,2,0,0], nums2 = [1,0,0,0,3,0,4]
输出：6

提示：

n == nums1.length == nums2.length
1 <= n <= 10^5
0 <= nums1[i], nums2[i] <= 100

方法一：哈希表 · Go 实现

思考

稀疏向量点积只需对两向量同时非零的下标累加。存下全部 $n$ 个分量再相乘，会在大量零上浪费时间，而 $n \leq 10^{5}$ 。

构造时只把非零项写入「下标 $\to$ 值」的哈希表。点积时遍历更短的那张表，用 $g e t$ 探测另一侧。非零项远少于 $n$ 时明显更快。

我们用哈希表 $d$ 来存储非零元素，其中键为下标，值为对应的值。我们遍历 $nums$ ，如果 $nums [i]$ 不为 $0$ ，我们就将 $(i, nums [i])$ 加入到哈希表 $d$ 中。

在计算点积时，我们遍历非零元素较少的哈希表，并判断另一个哈希表中是否存在对应的键，如果存在就将对应的值相乘并累加到答案中。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为数组长度。

type SparseVector struct {
	d map[int]int
}

func Constructor(nums []int) SparseVector {
	d := map[int]int{}
	for i, x := range nums {
		if x != 0 {
			d[i] = x
		}
	}
	return SparseVector{d}
}

// Return the dotProduct of two sparse vectors
func (this *SparseVector) dotProduct(vec SparseVector) (ans int) {
	a, b := this.d, vec.d
	if len(a) > len(b) {
		a, b = b, a
	}
	for i, x := range a {
		if y, has := b[i]; has {
			ans += x * y
		}
	}
	return
}

/**
 * Your SparseVector object will be instantiated and called as such:
 * v1 := Constructor(nums1);
 * v2 := Constructor(nums2);
 * ans := v1.dotProduct(v2);
 */

力扣原题 · Doocs 题解来源

1586. 二叉搜索树迭代器 II 🔒

中等2 种解法

标签：栈、树、设计、二叉搜索树、二叉树、迭代器

题目、示例与约束

实现二叉搜索树（BST）的中序遍历迭代器 BSTIterator 类：

BSTIterator(TreeNode root) 初始化 BSTIterator 类的实例。二叉搜索树的根节点 root 作为构造函数的参数传入。内部指针使用一个不存在于树中且小于树中任意值的数值来初始化。
boolean hasNext() 如果当前指针在中序遍历序列中，存在右侧数值，返回 true ，否则返回 false 。
int next() 将指针在中序遍历序列中向右移动，然后返回移动后指针所指数值。
boolean hasPrev() 如果当前指针在中序遍历序列中，存在左侧数值，返回 true ，否则返回 false 。
int prev() 将指针在中序遍历序列中向左移动，然后返回移动后指针所指数值。

注意，虽然我们使用树中不存在的最小值来初始化内部指针，第一次调用 next() 需要返回二叉搜索树中最小的元素。

你可以假设 next() 和 prev() 的调用总是有效的。即，当 next()/prev() 被调用的时候，在中序遍历序列中一定存在下一个/上一个元素。

进阶：你可以不提前遍历树中的值来解决问题吗？

示例 1:

输入
["BSTIterator", "next", "next", "prev", "next", "hasNext", "next", "next", "next", "hasNext", "hasPrev", "prev", "prev"]
[[[7, 3, 15, null, null, 9, 20]], [null], [null], [null], [null], [null], [null], [null], [null], [null], [null], [null], [null]]
输出
[null, 3, 7, 3, 7, true, 9, 15, 20, false, true, 15, 9]

解释
// 划线的元素表示指针当前的位置。
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]); // 当前状态为 <u> </u> [3, 7, 9, 15, 20]
bSTIterator.next(); // 状态变为 [<u>3</u>, 7, 9, 15, 20], 返回 3
bSTIterator.next(); // 状态变为 [3, <u>7</u>, 9, 15, 20], 返回 7
bSTIterator.prev(); // 状态变为 [<u>3</u>, 7, 9, 15, 20], 返回 3
bSTIterator.next(); // 状态变为 [3, <u>7</u>, 9, 15, 20], 返回 7
bSTIterator.hasNext(); // 返回 true
bSTIterator.next(); // 状态变为 [3, 7, <u>9</u>, 15, 20], 返回 9
bSTIterator.next(); // 状态变为 [3, 7, 9, <u>15</u>, 20], 返回 15
bSTIterator.next(); // 状态变为 [3, 7, 9, 15, <u>20</u>], 返回 20
bSTIterator.hasNext(); // 返回 false
bSTIterator.hasPrev(); // 返回 true
bSTIterator.prev(); // 状态变为 [3, 7, 9, <u>15</u>, 20], 返回 15
bSTIterator.prev(); // 状态变为 [3, 7, <u>9</u>, 15, 20], 返回 9

提示:

树中节点个数的范围是 [1, 10⁵] 。
0 <= Node.val <= 10⁶
最多调用 10⁵ 次 hasNext、 next、 hasPrev 和 prev 。

方法一：中序遍历 + 数组 · Go 实现

思考

迭代器要同时支持 $n e x t$ 与 $p r e v$ ，调用达 $10^{5}$ 次。只保存当前指针的栈式中序可以前进，回退却要重新找前驱。

中序遍历把 BST 展成有序数组，用下标 $i$ 表示当前位置。前进、后退都是 $i \pm 1$ ，判空即比较边界。初始化线性，之后每次操作常数时间。

我们可以使用中序遍历将二叉搜索树的所有节点的值存储到数组 $n u m s$ 中，然后使用数组实现迭代器。我们定义一个指针 $i$ ，初始时 $i = - 1$ ，表示指向数组 $n u m s$ 中的一个元素。每次调用 $n e x t ()$ 时，我们将 $i$ 的值加 $1$ ，并返回 $n u m s [i]$ ；每次调用 $p r e v ()$ 时，我们将 $i$ 的值减 $1$ ，并返回 $n u m s [i]$ 。

时间复杂度方面，初始化迭代器需要 $O (n)$ 的时间，其中 $n$ 是二叉搜索树的节点数。每次调用 $n e x t ()$ 和 $p r e v ()$ 都需要 $O (1)$ 的时间。空间复杂度方面，我们需要 $O (n)$ 的空间存储二叉搜索树的所有节点的值。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
type BSTIterator struct {
	nums []int
	i, n int
}

func Constructor(root *TreeNode) BSTIterator {
	nums := []int{}
	var dfs func(*TreeNode)
	dfs = func(root *TreeNode) {
		if root == nil {
			return
		}
		dfs(root.Left)
		nums = append(nums, root.Val)
		dfs(root.Right)
	}
	dfs(root)
	return BSTIterator{nums, -1, len(nums)}
}

func (this *BSTIterator) HasNext() bool {
	return this.i < this.n-1
}

func (this *BSTIterator) Next() int {
	this.i++
	return this.nums[this.i]
}

func (this *BSTIterator) HasPrev() bool {
	return this.i > 0
}

func (this *BSTIterator) Prev() int {
	this.i--
	return this.nums[this.i]
}

/**
 * Your BSTIterator object will be instantiated and called as such:
 * obj := Constructor(root);
 * param_1 := obj.HasNext();
 * param_2 := obj.Next();
 * param_3 := obj.HasPrev();
 * param_4 := obj.Prev();
 */

方法二：显式栈中序遍历 + 数组 · Go 实现

思考

迭代器要同时支持 $n e x t$ 与 $p r e v$ ，调用达 $10^{5}$ 次。只保存当前指针的栈式中序可以前进，回退却要重新找前驱。先把整棵树展成有序数组，再用下标移动，在较短的树上是对的。

结点个数可达 $10^{5}$ 。左链使这次中序按结点个数递归，调用栈会溢出。

二叉搜索树的中序次序就是结点值的非降序。每个结点先走完左子树，再记下自己，再走右子树，不需要返回值。

因此用显式栈做中序遍历，把结点值写入 $n u m s$ 。指针 $i$ 初值为 $- 1$ 。 $n e x t$ 和 $p r e v$ 分别把 $i$ 加一或减一后返回 $n u m s [i]$ ，是否还能移动则比较 $i$ 与数组边界。

我们用显式栈做中序遍历，把二叉搜索树的所有结点值写入数组 $n u m s$ ，再用这个数组实现迭代器。进入结点时压入退出标记和左孩子；退出时把结点值加入 $n u m s$ ，再压入右孩子。指针 $i$ 初始为 $- 1$ 。每次调用 $n e x t ()$ 时，将 $i$ 加 $1$ 并返回 $n u m s [i]$ ；每次调用 $p r e v ()$ 时，将 $i$ 减 $1$ 并返回 $n u m s [i]$ 。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
type BSTIterator struct {
	nums []int
	i, n int
}

func Constructor(root *TreeNode) BSTIterator {
	nums := []int{}
	type frame struct {
		node  *TreeNode
		state int
	}
	stk := []frame{{root, 0}}
	for len(stk) > 0 {
		cur := stk[len(stk)-1]
		stk = stk[:len(stk)-1]
		node, state := cur.node, cur.state
		if node == nil {
			continue
		}
		if state == 0 {
			stk = append(stk, frame{node, 1}, frame{node.Left, 0})
			continue
		}
		nums = append(nums, node.Val)
		stk = append(stk, frame{node.Right, 0})
	}
	return BSTIterator{nums, -1, len(nums)}
}

func (this *BSTIterator) HasNext() bool {
	return this.i < this.n-1
}

func (this *BSTIterator) Next() int {
	this.i++
	return this.nums[this.i]
}

func (this *BSTIterator) HasPrev() bool {
	return this.i > 0
}

func (this *BSTIterator) Prev() int {
	this.i--
	return this.nums[this.i]
}

/**
 * Your BSTIterator object will be instantiated and called as such:
 * obj := Constructor(root);
 * param_1 := obj.HasNext();
 * param_2 := obj.Next();
 * param_3 := obj.HasPrev();
 * param_4 := obj.Prev();
 */

力扣原题 · Doocs 题解来源

1600. 王位继承顺序

中等2 种解法

标签：树、深度优先搜索、设计、哈希表

题目、示例与约束

一个王国里住着国王、他的孩子们、他的孙子们等等。每一个时间点，这个家庭里有人出生也有人死亡。

这个王国有一个明确规定的王位继承顺序，第一继承人总是国王自己。我们定义递归函数 Successor(x, curOrder) ，给定一个人 x 和当前的继承顺序，该函数返回 x 的下一继承人。

Successor(x, curOrder):
    如果 x 没有孩子或者所有 x 的孩子都在 curOrder 中：
        如果 x 是国王，那么返回 null
        否则，返回 Successor(x 的父亲, curOrder)
    否则，返回 x 不在 curOrder 中最年长的孩子

比方说，假设王国由国王，他的孩子 Alice 和 Bob （Alice 比 Bob 年长）和 Alice 的孩子 Jack 组成。

一开始， curOrder 为 ["king"].
调用 Successor(king, curOrder) ，返回 Alice ，所以我们将 Alice 放入 curOrder 中，得到 ["king", "Alice"] 。
调用 Successor(Alice, curOrder) ，返回 Jack ，所以我们将 Jack 放入 curOrder 中，得到 ["king", "Alice", "Jack"] 。
调用 Successor(Jack, curOrder) ，返回 Bob ，所以我们将 Bob 放入 curOrder 中，得到 ["king", "Alice", "Jack", "Bob"] 。
调用 Successor(Bob, curOrder) ，返回 null 。最终得到继承顺序为 ["king", "Alice", "Jack", "Bob"] 。

通过以上的函数，我们总是能得到一个唯一的继承顺序。

请你实现 ThroneInheritance 类：

ThroneInheritance(string kingName) 初始化一个 ThroneInheritance 类的对象。国王的名字作为构造函数的参数传入。
void birth(string parentName, string childName) 表示 parentName 新拥有了一个名为 childName 的孩子。
void death(string name) 表示名为 name 的人死亡。一个人的死亡不会影响 Successor 函数，也不会影响当前的继承顺序。你可以只将这个人标记为死亡状态。
string[] getInheritanceOrder() 返回除去死亡人员的当前继承顺序列表。

示例：

输入：
["ThroneInheritance", "birth", "birth", "birth", "birth", "birth", "birth", "getInheritanceOrder", "death", "getInheritanceOrder"]
[["king"], ["king", "andy"], ["king", "bob"], ["king", "catherine"], ["andy", "matthew"], ["bob", "alex"], ["bob", "asha"], [null], ["bob"], [null]]
输出：
[null, null, null, null, null, null, null, ["king", "andy", "matthew", "bob", "alex", "asha", "catherine"], null, ["king", "andy", "matthew", "alex", "asha", "catherine"]]

解释：
ThroneInheritance t= new ThroneInheritance("king"); // 继承顺序：king
t.birth("king", "andy"); // 继承顺序：king > andy
t.birth("king", "bob"); // 继承顺序：king > andy > bob
t.birth("king", "catherine"); // 继承顺序：king > andy > bob > catherine
t.birth("andy", "matthew"); // 继承顺序：king > andy > matthew > bob > catherine
t.birth("bob", "alex"); // 继承顺序：king > andy > matthew > bob > alex > catherine
t.birth("bob", "asha"); // 继承顺序：king > andy > matthew > bob > alex > asha > catherine
t.getInheritanceOrder(); // 返回 ["king", "andy", "matthew", "bob", "alex", "asha", "catherine"]
t.death("bob"); // 继承顺序：king > andy > matthew > bob（已经去世）> alex > asha > catherine
t.getInheritanceOrder(); // 返回 ["king", "andy", "matthew", "alex", "asha", "catherine"]

提示：

1 <= kingName.length, parentName.length, childName.length, name.length <= 15
kingName，parentName， childName 和 name 仅包含小写英文字母。
所有的参数 childName 和 kingName 互不相同。
所有 death 函数中的死亡名字 name 要么是国王，要么是已经出生了的人员名字。
每次调用 birth(parentName, childName) 时，测试用例都保证 parentName 对应的人员是活着的。
最多调用 10⁵ 次birth 和 death 。
最多调用 10 次 getInheritanceOrder 。

方法一：多叉树的前序遍历 · Go 实现

思考

题目给出的 $Successor$ 按「当前人最年长且尚未列入顺序的孩子，否则回溯到父亲」递推，若每次查询都按定义从国王一路模拟，单次查询需要反复扫描子女列表，在出生次数达到 $10^{5}$ 、家族规模随之增大时，查询会落到平方级扫描。

注意到该递推恰好对应多叉树的前序遍历：先输出本人，再按出生先后递归各子树。死亡并不改变树形，只是从最终顺序中剔除，因此只需维护子女邻接表与死亡集合。

为此用哈希表 $g$ 按插入顺序记录子女，用集合 $dead$ 标记死亡；出生、死亡均为摊还常数，查询时从国王做一次 DFS，活着的结点按前序写入答案。

根据题目描述，我们可以发现，王位继承顺序实际上是一个多叉树的前序遍历。我们可以使用一个哈希表 $g$ 存储每个人的孩子，使用一个集合 $d e a d$ 存储已经去世的人。

调用 birth(parentName, childName) 时，我们将 childName 添加到 parentName 的孩子列表中。
调用 death(name) 时，我们将 name 添加到 dead 集合中。
调用 getInheritanceOrder() 时，我们从国王开始进行深度优先搜索，如果当前节点 x 没有去世，我们将 x 添加到答案列表中，然后递归地遍历 x 的所有孩子。

时间复杂度方面，birth 和 death 的时间复杂度均为 $O (1)$ ，getInheritanceOrder 的时间复杂度为 $O (n)$ ，空间复杂度为 $O (n)$ 。其中 $n$ 是节点数量。

type ThroneInheritance struct {
	king string
	dead map[string]bool
	g map[string][]string
}


func Constructor(kingName string) ThroneInheritance {
	return ThroneInheritance{kingName, map[string]bool{}, map[string][]string{}}
}


func (this *ThroneInheritance) Birth(parentName string, childName string)  {
	this.g[parentName] = append(this.g[parentName], childName)
}


func (this *ThroneInheritance) Death(name string)  {
	this.dead[name] = true
}


func (this *ThroneInheritance) GetInheritanceOrder() (ans []string) {
	var dfs func(string)
	dfs = func(x string) {
		if !this.dead[x] {
			ans = append(ans, x)
		}
		for _, y := range this.g[x] {
			dfs(y)
		}
	}
	dfs(this.king)
	return
}


/**
 * Your ThroneInheritance object will be instantiated and called as such:
 * obj := Constructor(kingName);
 * obj.Birth(parentName,childName);
 * obj.Death(name);
 * param_3 := obj.GetInheritanceOrder();
 */

方法二：显式栈前序遍历 · Go 实现

思考

题目给出的 $Successor$ 按「当前人最年长且尚未列入顺序的孩子，否则回溯到父亲」递推。若每次查询都按定义从国王一路模拟，单次查询会反复扫描子女列表；出生次数达到 $10^{5}$ 时，这样会落到平方级。该递推恰好是多叉树的前序：先写下本人，再按出生先后走各子树。死亡不改变树形，只是从最终顺序里去掉这个名字。沿一条出生链递归时，调用深度等于家族人数，链长达到 $1000$ 就会超出 Python 的递归上限。因此查询用栈做前序：弹出一个人，若仍在世就写入答案，再把子女按出生顺序的逆序压栈，这样先出生的孩子先被弹出。

王位继承顺序是多叉树的前序遍历。用哈希表 $g$ 按出生顺序存储每个人的孩子，用集合 $d e a d$ 存储已经去世的人。

调用 birth(parentName, childName) 时，将 childName 追加到 parentName 的孩子列表末尾。
调用 death(name) 时，将 name 加入 $d e a d$ 。
调用 getInheritanceOrder() 时，栈里最初只有国王。弹出 x 后，若 x 不在 $d e a d$ 中就写入答案，再把 x 的孩子从最后一个到第一个压入栈，从而保持出生顺序。

时间复杂度方面，birth 和 death 的时间复杂度均为 $O (1)$ ，getInheritanceOrder 的时间复杂度为 $O (n)$ ，空间复杂度为 $O (n)$ 。其中 $n$ 是节点数量。

type ThroneInheritance struct {
	king string
	dead map[string]bool
	g    map[string][]string
}

func Constructor(kingName string) ThroneInheritance {
	return ThroneInheritance{kingName, map[string]bool{}, map[string][]string{}}
}

func (this *ThroneInheritance) Birth(parentName string, childName string) {
	this.g[parentName] = append(this.g[parentName], childName)
}

func (this *ThroneInheritance) Death(name string) {
	this.dead[name] = true
}

func (this *ThroneInheritance) GetInheritanceOrder() (ans []string) {
	stk := []string{this.king}
	for len(stk) > 0 {
		x := stk[len(stk)-1]
		stk = stk[:len(stk)-1]
		if !this.dead[x] {
			ans = append(ans, x)
		}
		children := this.g[x]
		for i := len(children) - 1; i >= 0; i-- {
			stk = append(stk, children[i])
		}
	}
	return
}

/**
 * Your ThroneInheritance object will be instantiated and called as such:
 * obj := Constructor(kingName);
 * obj.Birth(parentName,childName);
 * obj.Death(name);
 * param_3 := obj.GetInheritanceOrder();
 */

力扣原题 · Doocs 题解来源

1603. 设计停车系统

简单1 种解法

标签：设计、计数、模拟

题目、示例与约束

请你给一个停车场设计一个停车系统。停车场总共有三种不同大小的车位：大，中和小，每种尺寸分别有固定数目的车位。

请你实现 ParkingSystem 类：

ParkingSystem(int big, int medium, int small) 初始化 ParkingSystem 类，三个参数分别对应每种停车位的数目。
bool addCar(int carType) 检查是否有 carType 对应的停车位。 carType 有三种类型：大，中，小，分别用数字 1， 2 和 3 表示。一辆车只能停在 carType 对应尺寸的停车位中。如果没有空车位，请返回 false ，否则将该车停入车位并返回 true 。

示例 1：

输入：
["ParkingSystem", "addCar", "addCar", "addCar", "addCar"]
[[1, 1, 0], [1], [2], [3], [1]]
输出：
[null, true, true, false, false]

解释：
ParkingSystem parkingSystem = new ParkingSystem(1, 1, 0);
parkingSystem.addCar(1); // 返回 true ，因为有 1 个空的大车位
parkingSystem.addCar(2); // 返回 true ，因为有 1 个空的中车位
parkingSystem.addCar(3); // 返回 false ，因为没有空的小车位
parkingSystem.addCar(1); // 返回 false ，因为没有空的大车位，唯一一个大车位已经被占据了

提示：

0 <= big, medium, small <= 1000
carType 取值为 1， 2 或 3
最多会调用 addCar 函数 1000 次

方法一：模拟 · Go 实现

思考

车型只有大、中、小三类，且 $addCar$ 至多调用 $1000$ 次，用三个计数器记录剩余车位即可在常数时间内判定。

每次到来一辆车，只需查看对应车型是否还有空位：若无则拒绝，否则减一并接受。

用长度为 $4$ 的数组 $cnt$ 按下标 $1, 2, 3$ 存放三类余量，避免分支上的重复逻辑。

我们用一个长度为 $4$ 的数组 $cnt$ 来表示停车场中每种车位的数量，其中 $cnt [1]$ , $cnt [2]$ , $cnt [3]$ 分别表示大车位、中车位、小车位的数量。

在初始化时，我们将 $cnt [1]$ , $cnt [2]$ , $cnt [3]$ 分别初始化为大车位、中车位、小车位的数量。

每次停车时，我们检查停车场中是否有对应车位，如果没有则返回 $false$ ，否则将对应车位的数量减一，并返回 $true$ 。

时间复杂度 $O (1)$ ，空间复杂度 $O (1)$ 。

type ParkingSystem struct {
	cnt []int
}

func Constructor(big int, medium int, small int) ParkingSystem {
	return ParkingSystem{[]int{0, big, medium, small}}
}

func (this *ParkingSystem) AddCar(carType int) bool {
	if this.cnt[carType] == 0 {
		return false
	}
	this.cnt[carType]--
	return true
}

/**
 * Your ParkingSystem object will be instantiated and called as such:
 * obj := Constructor(big, medium, small);
 * param_1 := obj.AddCar(carType);
 */

力扣原题 · Doocs 题解来源

1622. 奇妙序列

困难2 种解法

标签：设计、线段树、数学、数论、费马小定理

题目、示例与约束

请你实现三个 API append，addAll 和 multAll 来实现奇妙序列。

请实现 Fancy 类：

Fancy() 初始化一个空序列对象。
void append(val) 将整数 val 添加在序列末尾。
void addAll(inc) 将所有序列中的现有数值都增加 inc 。
void multAll(m) 将序列中的所有现有数值都乘以整数 m 。
int getIndex(idx) 得到下标为 idx 处的数值（下标从 0 开始），并将结果对 10⁹ + 7 取余。如果下标大于等于序列的长度，请返回 -1 。

示例：

输入：
["Fancy", "append", "addAll", "append", "multAll", "getIndex", "addAll", "append", "multAll", "getIndex", "getIndex", "getIndex"]
[[], [2], [3], [7], [2], [0], [3], [10], [2], [0], [1], [2]]
输出：
[null, null, null, null, null, 10, null, null, null, 26, 34, 20]

解释：
Fancy fancy = new Fancy();
fancy.append(2);   // 奇妙序列：[2]
fancy.addAll(3);   // 奇妙序列：[2+3] -> [5]
fancy.append(7);   // 奇妙序列：[5, 7]
fancy.multAll(2);  // 奇妙序列：[5*2, 7*2] -> [10, 14]
fancy.getIndex(0); // 返回 10
fancy.addAll(3);   // 奇妙序列：[10+3, 14+3] -> [13, 17]
fancy.append(10);  // 奇妙序列：[13, 17, 10]
fancy.multAll(2);  // 奇妙序列：[13*2, 17*2, 10*2] -> [26, 34, 20]
fancy.getIndex(0); // 返回 26
fancy.getIndex(1); // 返回 34
fancy.getIndex(2); // 返回 20

提示：

1 <= val, inc, m <= 100
0 <= idx <= 10⁵
总共最多会有 10⁵ 次对 append，addAll，multAll 和 getIndex 的调用。

方法一：线段树 · Go 实现

思考

题目要在序列末尾不断加入新数，还要对当前所有数一起做加法或乘法，再查某一个位置。操作最多 $10^{5}$ 次，每次把整个序列扫一遍会超时。

加法和乘法都作用在「已经加入的那一段」上，查询又只问一个点，可以用线段树来做区间修改。每个结点记下这段的和，以及还没传给子结点的乘法和加法；真正往下走时再传下去。

序列最长 $10^{5}$ ，按 $[1, 10^{5}]$ 动态开点即可。append 改一个点，addAll 和 multAll 改当前前缀，getIndex 查一个点，答案对 $10^{9} + 7$ 取模。

根据题目描述，append 在序列末尾加入一个数，addAll 给当前所有数加上同一个值，multAll 给当前所有数乘上同一个值，getIndex 查询某个位置的数。这就是区间加、区间乘和单点查询，可以用线段树维护。

我们给每个结点记录以下信息：

v：这个区间里所有数的和；
mul：还没下传给子结点的乘法，初始为 $1$ ；
add：还没下传给子结点的加法，初始为 $0$ 。

这两个标记的含义是：区间里每个数都要先乘上 mul，再加上 add。如果同一段上先后做了两次修改，不必真的改到叶子，可以把标记合并成一次。设第一次是「乘 $m_{1}$ 再加 $a_{1}$ 」，第二次是「乘 $m_{2}$ 再加 $a_{2}$ 」，那么：

(x \cdot m_{1} + a_{1}) \cdot m_{2} + a_{2} = x \cdot (m_{1} m_{2}) + (a_{1} m_{2} + a_{2})

也就是新的乘法是 $m_{1} m_{2}$ ，新的加法是 $a_{1} m_{2} + a_{2}$ 。

因此，给一段乘上 $m$ 时，结点的 v、mul、add 都乘上 $m$ ；给一段加上 $i n c$ 时，v 加上「区间长度 $\times i n c$ 」，add 加上 $i n c$ 。下传给左右儿子时，按同样的规则先乘后加。代码里把加和乘写成同一次操作：只加相当于「乘 $1$ 再加 $i n c$ 」，只乘相当于「乘 $m$ 再加 $0$ 」。

下标从 $1$ 开始，序列长度不超过 $10^{5}$ ，我们按 $[1, 10^{5}]$ 动态开点（用到某个结点时再创建）。append 时先让 $n$ 加一，再在位置 $n$ 上加上 $v a l$ ；addAll 和 multAll 修改区间 $[1, n]$ ；getIndex 查询位置 $i d x + 1$ 。所有运算对 $10^{9} + 7$ 取模。

时间复杂度 $O (m \log n)$ ，空间复杂度 $O (m \log n)$ 。其中 $m$ 为操作次数， $n$ 为序列长度的上界 $10^{5}$ 。

const mod int64 = 1e9 + 7

type node struct {
	left, right *node
	l, r, mid   int
	v, add, mul int64
}

func newNode(l, r int) *node {
	return &node{l: l, r: r, mid: (l + r) >> 1, mul: 1}
}

type segmentTree struct{ root *node }

func newSegmentTree() *segmentTree {
	return &segmentTree{root: newNode(1, 100001)}
}

func (t *segmentTree) modify(l, r int, mul, add int64, o *node) {
	if l > r {
		return
	}
	if o.l >= l && o.r <= r {
		t.apply(o, mul, add)
		return
	}
	t.pushdown(o)
	if l <= o.mid {
		t.modify(l, r, mul, add, o.left)
	}
	if r > o.mid {
		t.modify(l, r, mul, add, o.right)
	}
	t.pushup(o)
}

func (t *segmentTree) query(l, r int, o *node) int64 {
	if l > r {
		return 0
	}
	if o.l >= l && o.r <= r {
		return o.v
	}
	t.pushdown(o)
	var v int64
	if l <= o.mid {
		v = (v + t.query(l, r, o.left)) % mod
	}
	if r > o.mid {
		v = (v + t.query(l, r, o.right)) % mod
	}
	return v
}

func (t *segmentTree) apply(o *node, mul, add int64) {
	o.v = (o.v*mul + int64(o.r-o.l+1)*add) % mod
	o.add = (o.add*mul + add) % mod
	o.mul = o.mul * mul % mod
}

func (t *segmentTree) pushup(o *node) {
	o.v = (o.left.v + o.right.v) % mod
}

func (t *segmentTree) pushdown(o *node) {
	if o.left == nil {
		o.left = newNode(o.l, o.mid)
	}
	if o.right == nil {
		o.right = newNode(o.mid+1, o.r)
	}
	if o.add != 0 || o.mul != 1 {
		t.apply(o.left, o.mul, o.add)
		t.apply(o.right, o.mul, o.add)
		o.add, o.mul = 0, 1
	}
}

type Fancy struct {
	n    int
	tree *segmentTree
}

func Constructor() Fancy {
	return Fancy{tree: newSegmentTree()}
}

func (f *Fancy) Append(val int) {
	f.n++
	f.tree.modify(f.n, f.n, 1, int64(val), f.tree.root)
}

func (f *Fancy) AddAll(inc int) {
	f.tree.modify(1, f.n, 1, int64(inc), f.tree.root)
}

func (f *Fancy) MultAll(m int) {
	f.tree.modify(1, f.n, int64(m), 0, f.tree.root)
}

func (f *Fancy) GetIndex(idx int) int {
	if idx >= f.n {
		return -1
	}
	return int(f.tree.query(idx+1, idx+1, f.tree.root))
}

方法二：数学 + 乘法逆元 · Go 实现

思考

方法一每次修改还要在线段树上走一层，复杂度是 $O (\log n)$ 。再看操作会发现：addAll 和 multAll 永远作用在「当前已经有的全部数」上，新 append 进来的数并不会被之前的加、乘改到。

也就是说，已经在序列里的数，之后经历的加和乘完全一样。我们不必给每个下标单独记一棵树上的标记，只要用两个全局变量记下「这些数接下来都要乘多少、再加多少」。数组里存的是还没做这些运算之前的值，查询时再乘上、加上即可。模数是质数，除法用费马小定理换成乘逆元。

观察题目操作可以发现：每一次 addAll 和 multAll 都会作用到当时已经存在的所有数上，而之后新加入的数不受之前操作的影响。因此，对当前序列里的每个数，尚未作用到它身上的加、乘可以用两个全局变量来描述：先乘上 $a$ ，再加上 $b$ 。初始时 $a = 1$ ， $b = 0$ 。

我们在数组 nums 里存放的不是当前真实值，而是「还没乘 $a$ 、加上 $b$ 之前」的值，使得任意时刻都有：

真实值 = (a \times nums [i] + b) mod (10^{9} + 7)

各操作对应如下：

append(val)：这个新数还没有经历当前的 $a$ 和 $b$ ，所以要存一个 $x$ ，使得 $a \times x + b = val$ ，即 $x = (val - b) \times a^{- 1}$ ；
addAll(inc)：所有真实值都加上 $i n c$ ，只需把 $b$ 加上 $i n c$ ；
multAll(m)：所有真实值都乘上 $m$ ，于是 $a$ 和 $b$ 都乘上 $m$ ；
getIndex(idx)：下标越界返回 $- 1$ ，否则返回 $a \times nums [i d x] + b$ 。

其中 $a^{- 1}$ 表示 $a$ 在模 $10^{9} + 7$ 下的乘法逆元。模数是质数，由费马小定理有 $a^{- 1} \equiv a^{M O D - 2} (\mod M O D)$ 。

除 append 中求逆元需要 $O (\log M O D)$ 外，其余操作的时间复杂度均为 $O (1)$ 。空间复杂度 $O (n)$ 。

const mod int = 1e9 + 7

func qpow(x, n int) int {
	res := 1
	for n > 0 {
		if n&1 == 1 {
			res = res * x % mod
		}
		x = x * x % mod
		n >>= 1
	}
	return res
}

type Fancy struct {
	nums []int
	a, b int
}

func Constructor() Fancy {
	return Fancy{a: 1}
}

func (f *Fancy) Append(val int) {
	x := (val - f.b + mod) % mod * qpow(f.a, mod-2) % mod
	f.nums = append(f.nums, x)
}

func (f *Fancy) AddAll(inc int) {
	f.b = (f.b + inc) % mod
}

func (f *Fancy) MultAll(m int) {
	f.a = f.a * m % mod
	f.b = f.b * m % mod
}

func (f *Fancy) GetIndex(idx int) int {
	if idx >= len(f.nums) {
		return -1
	}
	return (f.a*f.nums[idx] + f.b) % mod
}

力扣原题 · Doocs 题解来源

1628. 设计带解析函数的表达式树 🔒

中等1 种解法

标签：栈、树、设计、数组、数学、二叉树

题目、示例与约束

给定一个算术表达式的后缀表示法的标记（token） postfix ，构造并返回该表达式对应的二叉表达式树。

后缀表示法是一种将操作数写在运算符之前的表示法。例如，表达式 4*(5-(2+7)) 的后缀表示法表示为数组 postfix = ["4","5","7","2","+","-","*"] 。

抽象类 Node 需要用于实现二叉表达式树。我们将通过 evaluate 函数来测试返回的树是否能够解析树中的值。你不可以移除 Node 类，但你可以按需修改此类，也可以定义其他类来实现它。

二叉表达式树是一种表达算术表达式的二叉树。二叉表达式树中的每一个节点都有零个或两个子节点。叶节点（有 0 个子节点的节点）表示操作数，非叶节点（有 2 个子节点的节点）表示运算符： '+' （加）、 '-' （减）、 '*' （乘）和 '/' （除）。

我们保证任何子树对应值的绝对值不超过 10⁹ ，且所有操作都是有效的（即没有除以零的操作）

进阶： 你可以将表达式树设计得更模块化吗？例如，你的设计能够不修改现有的 evaluate 的实现就能支持更多的操作符吗？

示例 1:

输入： s = ["3","4","+","2","*","7","/"]
输出： 2
解释： 此表达式可解析为上述二叉树，其对应表达式为 ((3+4)*2)/7) = 14/7 = 2.

示例 2:

输入: s = ["4","5","7","2","+","-","*"]
输出: -16
解释: 此表达式可解析为上述二叉树，其对应表达式为 4*(5-(2+7)) = 4*(-4) = -16.

提示:

1 <= s.length < 100
s.length 是奇数。
s 包含数字和字符 '+' 、 '-' 、 '*' 以及 '/' 。
如果 s[i] 是数，则对应的整数不超过 10⁵ 。
s 保证是一个有效的表达式。
结果值和所有过程值的绝对值均不超过 10⁹ 。
保证表达式不包含除以零的操作。

方法一：Go 解法（本站整理） · Go 实现

Doocs 参考题解 · CC BY-SA 4.0

基于 Doocs 后缀表达式建树参考改写。扫描 token：数字入栈，运算符先取右子树再取左子树并合成新节点。Evaluate 后序计算，Go 整数除法向零截断，避免 Python // 在负数上向下取整的差异。n 为 token 数，建树与求值各 O(n)，存储及最坏递归栈 O(n)。用 Node interface { Evaluate() int } 表达平台抽象节点，TreeBuilder 的 Constructor 和 BuildTree 为 Go 类接口。

出处：Doocs 原题与题解，固定提交 91ef8c241a5eaabf96f9ca8d45cfb1a338bcb011；题意、参考及本 Go 改写采用 CC BY-SA 4.0。

// 题意与参考：Doocs LeetCode，CC BY-SA 4.0。
// https://github.com/doocs/leetcode/blob/91ef8c241a5eaabf96f9ca8d45cfb1a338bcb011/solution/1600-1699/1628.Design%20an%20Expression%20Tree%20With%20Evaluate%20Function/README.md
// Go 实现与测试沿用 CC BY-SA 4.0；来源性质见配套说明。
import "strconv"

type Node interface{ Evaluate() int }
type expressionNode struct {
	token       string
	left, right Node
}

func (n *expressionNode) Evaluate() int {
	if n.left == nil {
		v, _ := strconv.Atoi(n.token)
		return v
	}
	a, b := n.left.Evaluate(), n.right.Evaluate()
	switch n.token {
	case "+":
		return a + b
	case "-":
		return a - b
	case "*":
		return a * b
	default:
		return a / b
	}
}

type TreeBuilder struct{}

func Constructor() TreeBuilder { return TreeBuilder{} }
func (t *TreeBuilder) BuildTree(postfix []string) Node {
	stack := []Node{}
	for _, s := range postfix {
		n := &expressionNode{token: s}
		if s == "+" || s == "-" || s == "*" || s == "/" {
			k := len(stack)
			n.left, n.right = stack[k-2], stack[k-1]
			stack = stack[:k-2]
		}
		stack = append(stack, n)
	}
	return stack[0]
}

力扣原题 · Doocs 题解来源

1656. 设计有序流

简单1 种解法

标签：设计、数组、哈希表、数据流

题目、示例与约束

有 n 个 (id, value) 对，其中 id 是 1 到 n 之间的一个整数，value 是一个字符串。不存在 id 相同的两个 (id, value) 对。

设计一个流，以任意顺序获取 n 个 (id, value) 对，并在多次调用时 按 id 递增的顺序 返回一些值。

实现 OrderedStream 类：

OrderedStream(int n) 构造一个能接收 n 个值的流，并将当前指针 ptr 设为 1 。
String[] insert(int id, String value) 向流中存储新的 (id, value) 对。存储后：
- 如果流存储有 id = ptr 的 (id, value) 对，则找出从 id = ptr 开始的 最长 id 连续递增序列 ，并 按顺序 返回与这些 id 关联的值的列表。然后，将 ptr 更新为最后那个 id + 1 。
- 否则，返回一个空列表。

示例：

输入
["OrderedStream", "insert", "insert", "insert", "insert", "insert"]
[[5], [3, "ccccc"], [1, "aaaaa"], [2, "bbbbb"], [5, "eeeee"], [4, "ddddd"]]
输出
[null, [], ["aaaaa"], ["bbbbb", "ccccc"], [], ["ddddd", "eeeee"]]

解释
OrderedStream os= new OrderedStream(5);
os.insert(3, "ccccc"); // 插入 (3, "ccccc")，返回 []
os.insert(1, "aaaaa"); // 插入 (1, "aaaaa")，返回 ["aaaaa"]
os.insert(2, "bbbbb"); // 插入 (2, "bbbbb")，返回 ["bbbbb", "ccccc"]
os.insert(5, "eeeee"); // 插入 (5, "eeeee")，返回 []
os.insert(4, "ddddd"); // 插入 (4, "ddddd")，返回 ["ddddd", "eeeee"]

提示：

1 <= n <= 1000
1 <= id <= n
value.length == 5
value 仅由小写字母组成
每次调用 insert 都会使用一个唯一的 id
恰好调用 n 次 insert

方法一：数组模拟 · Go 实现

思考

插入带编号的值，只有从当前指针起连续已填的一段才能输出。 $n$ 次插入各用不同编号，数组下标即编号。

写入 $data [idKey]$ 后，只要 $ptr$ 处非空就弹出并右移指针，返回这段列表。

我们可以使用一个长度为 $n + 1$ 的数组 $data$ 来模拟这个流，其中 $data [i]$ 表示 $id = i$ 的值。同时，我们使用一个指针 $ptr$ 来表示当前的位置。初始时 $ptr = 1$ 。

在插入一个新的 $(idKey, value)$ 对时，我们将 $data [idKey]$ 更新为 $value$ 。然后，我们从 $ptr$ 开始，依次将 $data [ptr]$ 加入答案中，直到 $data [ptr]$ 为空。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为数据流的长度。

type OrderedStream struct {
	ptr  int
	data []string
}

func Constructor(n int) OrderedStream {
	return OrderedStream{
		ptr:  1,
		data: make([]string, n+1),
	}
}

func (this *OrderedStream) Insert(idKey int, value string) []string {
	this.data[idKey] = value
	var ans []string
	for this.ptr < len(this.data) && this.data[this.ptr] != "" {
		ans = append(ans, this.data[this.ptr])
		this.ptr++
	}
	return ans
}

/**
 * Your OrderedStream object will be instantiated and called as such:
 * obj := Constructor(n);
 * param_1 := obj.Insert(idKey,value);
 */

力扣原题 · Doocs 题解来源

LeetCode Go · 数据结构设计（3） ​

911. 在线选举 ​

919. 完全二叉树插入器 ​

933. 最近的请求次数 ​

981. 基于时间的键值存储 ​

1032. 字符流 ​

1146. 快照数组 ​

1157. 子数组中占绝大多数的元素 ​

1166. 设计文件系统 🔒 ​

1172. 餐盘栈 ​

1206. 设计跳表 ​

1244. 力扣排行榜 🔒 ​

1261. 在受污染的二叉树中查找元素 ​

1286. 字母组合迭代器 ​

1348. 推文计数 ​

1352. 最后 K 个数的乘积 ​

1357. 每隔 n 个顾客打折 ​

1381. 设计一个支持增量操作的栈 ​

1396. 设计地铁系统 ​

1429. 第一个唯一数字 🔒 ​

1472. 设计浏览器历史记录 ​

1476. 子矩形查询 ​

1483. 树节点的第 K 个祖先 ​

1500. 设计文件分享系统 🔒 ​

1570. 两个稀疏向量的点积 🔒 ​

1586. 二叉搜索树迭代器 II 🔒 ​

1600. 王位继承顺序 ​

1603. 设计停车系统 ​

1622. 奇妙序列 ​

1628. 设计带解析函数的表达式树 🔒 ​

1656. 设计有序流 ​

继续阅读

LeetCode Go · 数据结构设计（3）

911. 在线选举

919. 完全二叉树插入器

933. 最近的请求次数

981. 基于时间的键值存储

1032. 字符流

1146. 快照数组

1157. 子数组中占绝大多数的元素

1166. 设计文件系统 🔒

1172. 餐盘栈

1206. 设计跳表

1244. 力扣排行榜 🔒

1261. 在受污染的二叉树中查找元素

1286. 字母组合迭代器

1348. 推文计数

1352. 最后 K 个数的乘积

1357. 每隔 n 个顾客打折

1381. 设计一个支持增量操作的栈

1396. 设计地铁系统

1429. 第一个唯一数字 🔒

1472. 设计浏览器历史记录

1476. 子矩形查询

1483. 树节点的第 K 个祖先

1500. 设计文件分享系统 🔒

1570. 两个稀疏向量的点积 🔒

1586. 二叉搜索树迭代器 II 🔒

1600. 王位继承顺序

1603. 设计停车系统

1622. 奇妙序列

1628. 设计带解析函数的表达式树 🔒

1656. 设计有序流