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

来源与许可

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

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

146. LRU 缓存

中等1 种解法

标签：设计、哈希表、链表、双向链表

题目、示例与约束

请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。

实现 LRUCache 类：

LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该逐出最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

提示：

1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 10⁵
最多调用 2 * 10⁵ 次 get 和 put

方法一：哈希表 + 双向链表 · Go 实现

思考

$get$ / $put$ 都要 $O (1)$ ，淘汰最久未使用的键。哈希表能 $O (1)$ 查找，但不能单独维护使用顺序；数组或单向链表移动节点是 $O (n)$ 。调用次数达 $2 \times 10^{5}$ 。

哈希表存键到节点，双向链表按「最近使用在头、最久在尾」排列。访问或更新时把节点摘下再插到头部；容量满时删掉尾部前驱。查找与调整指针都是 $O (1)$ 。

我们可以用“哈希表”和“双向链表”实现一个 LRU 缓存。

哈希表：用于存储 key 和对应的节点位置。
双向链表：用于存储节点数据，按照访问时间排序。

当访问一个节点时，如果节点存在，我们将其从原来的位置删除，并重新插入到链表头部。这样就能保证链表尾部存储的就是最近最久未使用的节点，当节点数量大于缓存最大空间时就淘汰链表尾部的节点。

当插入一个节点时，如果节点存在，我们将其从原来的位置删除，并重新插入到链表头部。如果不存在，我们首先检查缓存是否已满，如果已满，则删除链表尾部的节点，将新的节点插入链表头部。

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

type Node struct {
	key, val   int
	prev, next *Node
}

type LRUCache struct {
	size, capacity int
	head, tail     *Node
	cache          map[int]*Node
}

func Constructor(capacity int) LRUCache {
	head := &Node{}
	tail := &Node{}
	head.next = tail
	tail.prev = head
	return LRUCache{
		capacity: capacity,
		head:     head,
		tail:     tail,
		cache:    make(map[int]*Node),
	}
}

func (this *LRUCache) Get(key int) int {
	if node, exists := this.cache[key]; exists {
		this.removeNode(node)
		this.addToHead(node)
		return node.val
	}
	return -1
}

func (this *LRUCache) Put(key int, value int) {
	if node, exists := this.cache[key]; exists {
		this.removeNode(node)
		node.val = value
		this.addToHead(node)
	} else {
		node := &Node{key: key, val: value}
		this.cache[key] = node
		this.addToHead(node)
		if this.size++; this.size > this.capacity {
			node = this.tail.prev
			delete(this.cache, node.key)
			this.removeNode(node)
			this.size--
		}
	}
}

func (this *LRUCache) removeNode(node *Node) {
	node.prev.next = node.next
	node.next.prev = node.prev
}

func (this *LRUCache) addToHead(node *Node) {
	node.next = this.head.next
	node.prev = this.head
	this.head.next = node
	node.next.prev = node
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */

/**
 * Your LRUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */

力扣原题 · Doocs 题解来源

155. 最小栈

中等1 种解法

标签：栈、设计

题目、示例与约束

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

MinStack() 初始化堆栈对象。
void push(int value) 将元素 value 推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

示例 1:

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

提示：

-2³¹ <= val <= 2³¹ - 1
pop、top 和 getMin 操作总是在 非空栈 上调用
push, pop, top, and getMin最多被调用 3 * 10⁴ 次

方法一：双栈 · Go 实现

思考

栈的 $getMin$ 要与 $push / pop$ 一样 $O (1)$ 。每次扫描栈底是线性的，调用可达 $3 \times 10^{4}$ 。最小值只在入栈更小元素或弹出当前最小时变化，因此再维护一个同步的最小栈：每次压入 $\min(x, $ 当前最小 $)$ ，弹出时两栈一起弹。

我们用两个栈来实现，其中 stk1 用来存储数据，stk2 用来存储当前栈中的最小值。初始时，stk2 中存储一个极大值。

当我们向栈中压入一个元素 $x$ 时，我们将 $x$ 压入 stk1，并将 min(x, stk2[-1]) 压入 stk2。
当我们从栈中弹出一个元素时，我们将 stk1 和 stk2 的栈顶元素都弹出。
当我们要获取当前栈中的栈顶元素时，我们只需要返回 stk1 的栈顶元素即可。
当我们要获取当前栈中的最小值时，我们只需要返回 stk2 的栈顶元素即可。

每个操作的时间复杂度为 $O (1)$ 。整体的空间复杂度为 $O (n)$ ，其中 $n$ 为栈中元素的个数。

type MinStack struct {
	stk1 []int
	stk2 []int
}

func Constructor() MinStack {
	return MinStack{[]int{}, []int{math.MaxInt32}}
}

func (this *MinStack) Push(val int) {
	this.stk1 = append(this.stk1, val)
	this.stk2 = append(this.stk2, min(val, this.stk2[len(this.stk2)-1]))
}

func (this *MinStack) Pop() {
	this.stk1 = this.stk1[:len(this.stk1)-1]
	this.stk2 = this.stk2[:len(this.stk2)-1]
}

func (this *MinStack) Top() int {
	return this.stk1[len(this.stk1)-1]
}

func (this *MinStack) GetMin() int {
	return this.stk2[len(this.stk2)-1]
}

/**
 * Your MinStack object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(val);
 * obj.Pop();
 * param_3 := obj.Top();
 * param_4 := obj.GetMin();
 */

力扣原题 · Doocs 题解来源

170. 两数之和 III - 数据结构设计 🔒

简单1 种解法

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

题目、示例与约束

设计一个接收整数流的数据结构，该数据结构支持检查是否存在两数之和等于特定值。

实现 TwoSum 类：

TwoSum() 使用空数组初始化 TwoSum 对象
void add(int number) 向数据结构添加一个数 number
boolean find(int value) 寻找数据结构中是否存在一对整数，使得两数之和与给定的值相等。如果存在，返回 true ；否则，返回 false 。

示例：

输入：
["TwoSum", "add", "add", "add", "find", "find"]
[[], [1], [3], [5], [4], [7]]
输出：
[null, null, null, null, true, false]

解释：
TwoSum twoSum = new TwoSum();
twoSum.add(1);   // [] --> [1]
twoSum.add(3);   // [1] --> [1,3]
twoSum.add(5);   // [1,3] --> [1,3,5]
twoSum.find(4);  // 1 + 3 = 4，返回 true
twoSum.find(7);  // 没有两个整数加起来等于 7 ，返回 false

提示：

-10⁵ <= number <= 10⁵
-2³¹ <= value <= 2³¹ - 1
最多调用 10⁴ 次 add 和 find

方法一：哈希表 · Go 实现

思考

要支持随时加数，并查询是否存在和为给定值的两数。最多 $10^{4}$ 次调用。若每次 $find$ 都排序再双指针，加数会打乱顺序。用哈希表记下每个数的出现次数： $add$ 为 $O (1)$ ； $find$ 枚举 $x$ 查 $v a l u e - x$ ，注意 $x$ 与 $v a l u e - x$ 相同时次数至少为 $2$ 。

我们用哈希表 cnt 存储数字出现的次数。

调用 add 方法时，将数字 number 的出现次数加一。

调用 find 方法时，遍历哈希表 cnt，对于每个键 x，判断 value - x 是否也是哈希表 cnt 的键，如果是，判断 x 是否等于 value - x，如果不等，说明找到了一对和为 value 的数字，返回 true；如果等，判断 x 的出现次数是否大于 1，如果大于 1，说明找到了一对和为 value 的数字，返回 true；如果小于等于 1，说明没有找到一对和为 value 的数字，继续遍历哈希表 cnt，如果遍历结束都没有找到，返回 false。

时间复杂度：

add 方法的时间复杂度为 $O (1)$ ；
find 方法的时间复杂度为 $O (n)$ 。

空间复杂度 $O (n)$ ，其中 $n$ 为哈希表 cnt 的大小。

type TwoSum struct {
	cnt map[int]int
}

func Constructor() TwoSum {
	return TwoSum{map[int]int{}}
}

func (this *TwoSum) Add(number int) {
	this.cnt[number] += 1
}

func (this *TwoSum) Find(value int) bool {
	for x, v := range this.cnt {
		y := value - x
		if _, ok := this.cnt[y]; ok && (x != y || v > 1) {
			return true
		}
	}
	return false
}

/**
 * Your TwoSum object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Add(number);
 * param_2 := obj.Find(value);
 */

力扣原题 · Doocs 题解来源

173. 二叉搜索树迭代器

中等2 种解法

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

题目、示例与约束

实现一个二叉搜索树迭代器类BSTIterator ，表示一个按中序遍历二叉搜索树（BST）的迭代器：

BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字，且该数字小于 BST 中的任何元素。
boolean hasNext() 如果向指针右侧遍历存在数字，则返回 true ；否则返回 false 。
int next()将指针向右移动，然后返回指针处的数字。

注意，指针初始化为一个不存在于 BST 中的数字，所以对 next() 的首次调用将返回 BST 中的最小元素。

你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 的中序遍历中至少存在一个下一个数字。

示例：

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

解释
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next(); // 返回 3
bSTIterator.next(); // 返回 7
bSTIterator.hasNext(); // 返回 True
bSTIterator.next(); // 返回 9
bSTIterator.hasNext(); // 返回 True
bSTIterator.next(); // 返回 15
bSTIterator.hasNext(); // 返回 True
bSTIterator.next(); // 返回 20
bSTIterator.hasNext(); // 返回 False

提示：

树中节点的数目在范围 [1, 10⁵] 内
0 <= Node.val <= 10⁶
最多调用 10⁵ 次 hasNext 和 next 操作

进阶：

你可以设计一个满足下述条件的解决方案吗？next() 和 hasNext() 操作均摊时间复杂度为 O(1) ，并使用 O(h) 内存。其中 h 是树的高度。

方法一：递归 · Go 实现

思考

中序遍历 BST 得到升序。节点可达 $10^{5}$ ，调用次数同阶。构造时一次性递归中序放入数组， $next / hasNext$ 只移动下标，均摊 $O (1)$ ，但空间是 $O (n)$ 。进阶希望空间降到树高。

初始化数据时，递归中序遍历，将二叉搜索树每个结点的值保存在列表 vals 中。用 cur 指针记录外部即将遍历的位置，初始化为 0。

调用 next() 时，返回 vals[cur]，同时 cur 指针自增。调用 hasNext() 时，判断 cur 指针是否已经达到 len(vals) 个数，若是，说明已经遍历结束，返回 false，否则返回 true。

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

func Constructor(root *TreeNode) BSTIterator {
	it := BSTIterator{vals: []int{}}
	var inorder func(*TreeNode)
	inorder = func(root *TreeNode) {
		if root != nil {
			inorder(root.Left)
			it.vals = append(it.vals, root.Val)
			inorder(root.Right)
		}
	}
	inorder(root)
	return it
}

func (this *BSTIterator) Next() int {
	res := this.vals[this.cur]
	this.cur++
	return res
}

func (this *BSTIterator) HasNext() bool {
	return this.cur < len(this.vals)
}

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

方法二：栈迭代 · Go 实现

思考

方法一把整棵树摊平。用栈模拟中序：初始化沿左链压栈， $next$ 弹出栈顶后把它的右孩子的左链压入。栈中至多 $h$ 个节点，均摊每个节点入栈出栈各一次。

初始化时，从根节点一路遍历所有左子节点，压入栈 stack 中。

调用 next()时，弹出栈顶元素 cur，获取 cur 的右子节点 node，若 node 不为空，一直循环压入左节点。最后返回 cur.val 即可。调用 hasNext() 时，判断 stack 是否为空，空则表示迭代结束。

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

func Constructor(root *TreeNode) BSTIterator {
	var stack []*TreeNode
	for ; root != nil; root = root.Left {
		stack = append(stack, root)
	}
	return BSTIterator{
		stack: stack,
	}
}

func (this *BSTIterator) Next() int {
	cur := this.stack[len(this.stack)-1]
	this.stack = this.stack[:len(this.stack)-1]
	for node := cur.Right; node != nil; node = node.Left {
		this.stack = append(this.stack, node)
	}
	return cur.Val
}

func (this *BSTIterator) HasNext() bool {
	return len(this.stack) > 0
}

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

力扣原题 · Doocs 题解来源

208. 实现 Trie (前缀树)

中等1 种解法

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

题目、示例与约束

Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。

请你实现 Trie 类：

Trie() 初始化前缀树对象。
void insert(String word) 向前缀树中插入字符串 word 。
boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

示例：

输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]

解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // 返回 True
trie.search("app");     // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app");     // 返回 True

提示：

1 <= word.length, prefix.length <= 2000
word 和 prefix 仅由小写英文字母组成
insert、search 和 startsWith 调用次数总计不超过 3 * 10⁴ 次

方法一：前缀树 · Go 实现

思考

多次查询公共前缀时，若对每个单词扫描全部已插入词，则会重复比较相同前缀。字符均为小写，可用 $26$ 叉树按字符分层。

插入时沿路径创建结点并在末尾置 $i s E n d$ ；查询前缀走同一路径，search 再检查终点是否为词尾。

前缀树每个节点包括两部分：

指向子节点的指针数组 $c h i l d r e n$ ，对于本题而言，数组长度为 $26$ ，即小写英文字母的数量。 $c h i l d r e n [0]$ 对应小写字母 $a$ ，...， $c h i l d r e n [25]$ 对应小写字母 $z$ 。
布尔字段 $i s E n d$ ，表示该节点是否为字符串的结尾。

1. 插入字符串

我们从字典树的根开始，插入字符串。对于当前字符对应的子节点，有两种情况：

子节点存在。沿着指针移动到子节点，继续处理下一个字符。
子节点不存在。创建一个新的子节点，记录在 $c h i l d r e n$ 数组的对应位置上，然后沿着指针移动到子节点，继续搜索下一个字符。

重复以上步骤，直到处理字符串的最后一个字符，然后将当前节点标记为字符串的结尾。

2. 查找前缀

我们从字典树的根开始，查找前缀。对于当前字符对应的子节点，有两种情况：

子节点存在。沿着指针移动到子节点，继续搜索下一个字符。
子节点不存在。说明字典树中不包含该前缀，返回空指针。

重复以上步骤，直到返回空指针或搜索完前缀的最后一个字符。

若搜索到了前缀的末尾，就说明字典树中存在该前缀。此外，若前缀末尾对应节点的 $i s E n d$ 为真，则说明字典树中存在该字符串。

时间复杂度方面，插入字符串的时间复杂度为 $O (m \times | Σ |)$ ，查找前缀的时间复杂度为 $O (m)$ ，其中 $m$ 为字符串的长度，而 $| Σ |$ 为字符集的大小（本题中为 $26$ ）。空间复杂度为 $O (q \times m \times | Σ |)$ ，其中 $q$ 为插入的字符串数量。

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

func Constructor() Trie {
	return Trie{}
}

func (this *Trie) Insert(word string) {
	node := this
	for _, c := range word {
		idx := c - 'a'
		if node.children[idx] == nil {
			node.children[idx] = &Trie{}
		}
		node = node.children[idx]
	}
	node.isEnd = true
}

func (this *Trie) Search(word string) bool {
	node := this.SearchPrefix(word)
	return node != nil && node.isEnd
}

func (this *Trie) StartsWith(prefix string) bool {
	node := this.SearchPrefix(prefix)
	return node != nil
}

func (this *Trie) SearchPrefix(s string) *Trie {
	node := this
	for _, c := range s {
		idx := c - 'a'
		if node.children[idx] == nil {
			return nil
		}
		node = node.children[idx]
	}
	return node
}

/**
 * Your Trie object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Insert(word);
 * param_2 := obj.Search(word);
 * param_3 := obj.StartsWith(prefix);
 */

力扣原题 · Doocs 题解来源

211. 添加与搜索单词 - 数据结构设计

中等1 种解法

标签：深度优先搜索、设计、字典树、字符串

题目、示例与约束

请你设计一个数据结构，支持添加新单词和查找字符串是否与任何先前添加的字符串匹配。

实现词典类 WordDictionary ：

WordDictionary() 初始化词典对象
void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配
bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true ；否则，返回 false 。word 中可能包含一些 '.' ，每个 . 都可以表示任何一个字母。

示例：

输入：
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
输出：
[null,null,null,null,false,true,true,true]

解释：
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // 返回 False
wordDictionary.search("bad"); // 返回 True
wordDictionary.search(".ad"); // 返回 True
wordDictionary.search("b.."); // 返回 True

提示：

1 <= word.length <= 25
addWord 中的 word 由小写英文字母组成
search 中的 word 由 '.' 或小写英文字母组成
最多调用 10⁴ 次 addWord 和 search

方法一 · Go 实现

思考

精确匹配可用哈希表，但模式中的 $.$ 可代表任一字母，按词枚举无法高效处理通配。单词由小写字母构成，适合前缀树。

添加时沿 $26$ 叉路径建结点；搜索遇到普通字符则走固定边，遇到 $.$ 则对所有非空孩子分支，终点需为词尾。

type WordDictionary struct {
	root *trie
}

func Constructor() WordDictionary {
	return WordDictionary{new(trie)}
}

func (this *WordDictionary) AddWord(word string) {
	this.root.insert(word)
}

func (this *WordDictionary) Search(word string) bool {
	n := len(word)

	var dfs func(int, *trie) bool
	dfs = func(i int, cur *trie) bool {
		if i == n {
			return cur.isEnd
		}
		c := word[i]
		if c != '.' {
			child := cur.children[c-'a']
			if child != nil && dfs(i+1, child) {
				return true
			}
		} else {
			for _, child := range cur.children {
				if child != nil && dfs(i+1, child) {
					return true
				}
			}
		}
		return false
	}

	return dfs(0, this.root)
}

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

func (t *trie) insert(word string) {
	cur := t
	for _, c := range word {
		c -= 'a'
		if cur.children[c] == nil {
			cur.children[c] = new(trie)
		}
		cur = cur.children[c]
	}
	cur.isEnd = true
}

/**
 * Your WordDictionary object will be instantiated and called as such:
 * obj := Constructor();
 * obj.AddWord(word);
 * param_2 := obj.Search(word);
 */

力扣原题 · Doocs 题解来源

225. 用队列实现栈

简单1 种解法

标签：栈、设计、队列

题目、示例与约束

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

你只能使用队列的标准操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

示例：

输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]

解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

提示：

1 <= x <= 9
最多调用100 次 push、pop、top 和 empty
每次调用 pop 和 top 都保证栈不为空

进阶：你能否仅用一个队列来实现栈。

方法一：两个队列 · Go 实现

思考

队列只能在队尾入、队头出，栈却要后入先出。若在入栈时就把新元素转到队头，则出栈与读顶都可直接取队首。

为此用 $q_{2}$ 先收下新元素，再把 $q_{1}$ 全部接到其后并交换，使 $q_{1}$ 队首始终为栈顶。

我们使用两个队列 $q_{1}$ 和 $q_{2}$ ，其中 $q_{1}$ 用于存储栈中的元素，而 $q_{2}$ 用于辅助实现栈的操作。

push 操作：将元素压入 $q_{2}$ ，然后将 $q_{1}$ 中的元素依次弹出并压入 $q_{2}$ ，最后交换 $q_{1}$ 和 $q_{2}$ 的引用。时间复杂度 $O (n)$ 。
pop 操作：直接弹出 $q_{1}$ 的队首元素。时间复杂度 $O (1)$ 。
top 操作：直接返回 $q_{1}$ 的队首元素。时间复杂度 $O (1)$ 。
empty 操作：判断 $q_{1}$ 是否为空。时间复杂度 $O (1)$ 。

空间复杂度 $O (n)$ ，其中 $n$ 是栈中元素的个数。

type MyStack struct {
	q1 []int
	q2 []int
}

func Constructor() MyStack {
	return MyStack{}
}

func (this *MyStack) Push(x int) {
	this.q2 = append(this.q2, x)
	for len(this.q1) > 0 {
		this.q2 = append(this.q2, this.q1[0])
		this.q1 = this.q1[1:]
	}
	this.q1, this.q2 = this.q2, this.q1
}

func (this *MyStack) Pop() int {
	x := this.q1[0]
	this.q1 = this.q1[1:]
	return x
}

func (this *MyStack) Top() int {
	return this.q1[0]
}

func (this *MyStack) Empty() bool {
	return len(this.q1) == 0
}

/**
 * Your MyStack object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(x);
 * param_2 := obj.Pop();
 * param_3 := obj.Top();
 * param_4 := obj.Empty();
 */

力扣原题 · Doocs 题解来源

232. 用栈实现队列

简单1 种解法

标签：栈、设计、队列

题目、示例与约束

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

示例 1：

输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]

解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

提示：

1 <= x <= 9
最多调用 100 次 push、pop、peek 和 empty
假设所有操作都是有效的（例如，一个空的队列不会调用 pop 或者 peek 操作）

进阶：

你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。

方法一：双栈 · Go 实现

思考

栈是后入先出，队列要先入先出，单个栈无法同时满足两端。用两个栈：入队只进 $s t k 1$ ，出队从 $s t k 2$ 取。

$s t k 2$ 为空时把 $s t k 1$ 全部倒过去，顺序即变为队头在顶。每个元素至多搬运一次，出队均摊常数。

我们使用两个栈，其中栈 stk1用于入队，另一个栈 stk2 用于出队。

入队时，直接将元素入栈 stk1。时间复杂度 $O (1)$ 。

出队时，先判断栈 stk2 是否为空，如果为空，则将栈 stk1 中的元素全部出栈并入栈 stk2，然后再从栈 stk2 中出栈一个元素。如果栈 stk2 不为空，则直接从栈 stk2 中出栈一个元素。均摊时间复杂度 $O (1)$ 。

获取队首元素时，先判断栈 stk2 是否为空，如果为空，则将栈 stk1 中的元素全部出栈并入栈 stk2，然后再从栈 stk2 中获取栈顶元素。如果栈 stk2 不为空，则直接从栈 stk2 中获取栈顶元素。均摊时间复杂度 $O (1)$ 。

判断队列是否为空时，只要判断两个栈是否都为空即可。时间复杂度 $O (1)$ 。

type MyQueue struct {
	stk1 []int
	stk2 []int
}

func Constructor() MyQueue {
	return MyQueue{[]int{}, []int{}}
}

func (this *MyQueue) Push(x int) {
	this.stk1 = append(this.stk1, x)
}

func (this *MyQueue) Pop() int {
	this.move()
	ans := this.stk2[len(this.stk2)-1]
	this.stk2 = this.stk2[:len(this.stk2)-1]
	return ans
}

func (this *MyQueue) Peek() int {
	this.move()
	return this.stk2[len(this.stk2)-1]
}

func (this *MyQueue) Empty() bool {
	return len(this.stk1) == 0 && len(this.stk2) == 0
}

func (this *MyQueue) move() {
	if len(this.stk2) == 0 {
		for len(this.stk1) > 0 {
			this.stk2 = append(this.stk2, this.stk1[len(this.stk1)-1])
			this.stk1 = this.stk1[:len(this.stk1)-1]
		}
	}
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(x);
 * param_2 := obj.Pop();
 * param_3 := obj.Peek();
 * param_4 := obj.Empty();
 */

力扣原题 · Doocs 题解来源

244. 最短单词距离 II 🔒

中等1 种解法

标签：设计、数组、哈希表、双指针、字符串

题目、示例与约束

请设计一个类，使该类的构造函数能够接收一个字符串数组。然后再实现一个方法，该方法能够分别接收两个单词，并返回列表中这两个单词之间的最短距离。

实现 WordDistanc 类:

WordDistance(String[] wordsDict) 用字符串数组 wordsDict 初始化对象。
int shortest(String word1, String word2) 返回数组 worddict 中 word1 和 word2 之间的最短距离。

示例 1:

输入: 
["WordDistance", "shortest", "shortest"]
[[["practice", "makes", "perfect", "coding", "makes"]], ["coding", "practice"], ["makes", "coding"]]
输出:
[null, 3, 1]

解释：
WordDistance wordDistance = new WordDistance(["practice", "makes", "perfect", "coding", "makes"]);
wordDistance.shortest("coding", "practice"); // 返回 3
wordDistance.shortest("makes", "coding");    // 返回 1

注意:

1 <= wordsDict.length <= 3 * 10⁴
1 <= wordsDict[i].length <= 10
wordsDict[i] 由小写英文字母组成
word1 和 word2 在数组 wordsDict 中
word1 != word2
shortest 操作次数不大于 5000

方法一：哈希表 + 双指针 · Go 实现

思考

查询会多次出现，每次扫全表偏慢。先把每个词的全部下标存入哈希表，查询时对两个有序下标列双指针求最小间距。

我们用哈希表 $d$ 存储每个单词在数组中出现的所有下标，然后用双指针 $i$ 和 $j$ 分别指向两个单词在数组中出现的下标列表 $a$ 和 $b$ ，每次更新下标差值的最小值，然后移动下标较小的指针，直到其中一个指针遍历完下标列表。

初始化的时间复杂度为 $O (n)$ ，其中 $n$ 为数组的长度。每次调用 shortest 方法的时间复杂度为 $O (m + n)$ ，其中 $m$ 为两个单词在数组中出现的下标列表的长度之和。

type WordDistance struct {
	d map[string][]int
}

func Constructor(wordsDict []string) WordDistance {
	d := map[string][]int{}
	for i, w := range wordsDict {
		d[w] = append(d[w], i)
	}
	return WordDistance{d}
}

func (this *WordDistance) Shortest(word1 string, word2 string) int {
	a, b := this.d[word1], this.d[word2]
	ans := 0x3f3f3f3f
	i, j := 0, 0
	for i < len(a) && j < len(b) {
		ans = min(ans, abs(a[i]-b[j]))
		if a[i] <= b[j] {
			i++
		} else {
			j++
		}
	}
	return ans
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

/**
 * Your WordDistance object will be instantiated and called as such:
 * obj := Constructor(wordsDict);
 * param_1 := obj.Shortest(word1,word2);
 */

力扣原题 · Doocs 题解来源

251. 展开二维向量 🔒

中等1 种解法

标签：设计、数组、双指针、迭代器

题目、示例与约束

请设计并实现一个能够展开二维向量的迭代器。该迭代器需要支持 next 和 hasNext 两种操作。

实现 Vector2D 类：

Vector2D(int[][] vec) 使用二维向量 vec 初始化对象
next() 从二维向量返回下一个元素并将指针移动到下一个位置。你可以假设对 next 的所有调用都是合法的。
hasNext() 当向量中还有元素返回 true，否则返回 false。

示例 1：

输入：
["Vector2D", "next", "next", "next", "hasNext", "hasNext", "next", "hasNext"]
[[[[1, 2], [3], [4]]], [], [], [], [], [], [], []]
输出：
[null, 1, 2, 3, true, true, 4, false]

解释：
Vector2D vector2D = new Vector2D([[1, 2], [3], [4]]);
vector2D.next();    // return 1
vector2D.next();    // return 2
vector2D.next();    // return 3
vector2D.hasNext(); // return True
vector2D.hasNext(); // return True
vector2D.next();    // return 4
vector2D.hasNext(); // return False

提示：

0 <= vec.length <= 200
0 <= vec[i].length <= 500
-500 <= vec[i][j] <= 500
最多调用 next 和 hasNext 10⁵ 次。

进阶：尝试在代码中仅使用 C++ 提供的迭代器或 Java 提供的迭代器。

方法一：双指针 · Go 实现

思考

预先展开成一维数组简单，但浪费空间且未体现迭代器语义。用行、列两个下标定位下一个元素即可。

$f o r w a r d$ 跳过空行，使 $(i, j)$ 落在有效元素上； $n e x t$ 取其值并右移， $h a s N e x t$ 看 $i$ 是否仍在范围内。

我们定义两个指针 $i$ 和 $j$ ，分别指向当前二维向量的行和列，初始时 $i = 0$ ， $j = 0$ 。

接下来，我们设计一个函数 $f o r w a r d ()$ ，用于将 $i$ 和 $j$ 向后移动，直到指向一个非空的元素。

每次调用 next 方法时，我们先调用 $f o r w a r d ()$ ，然后返回当前指向的元素，最后将 $j$ 向后移动一位。

每次调用 hasNext 方法时，我们先调用 $f o r w a r d ()$ ，然后判断 $i$ 是否小于二维向量的行数，如果是，则返回 true，否则返回 false。

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

type Vector2D struct {
	i, j int
	vec  [][]int
}

func Constructor(vec [][]int) Vector2D {
	return Vector2D{vec: vec}
}

func (this *Vector2D) Next() int {
	this.forward()
	ans := this.vec[this.i][this.j]
	this.j++
	return ans
}

func (this *Vector2D) HasNext() bool {
	this.forward()
	return this.i < len(this.vec)
}

func (this *Vector2D) forward() {
	for this.i < len(this.vec) && this.j >= len(this.vec[this.i]) {
		this.i++
		this.j = 0
	}
}

/**
 * Your Vector2D object will be instantiated and called as such:
 * obj := Constructor(vec);
 * param_1 := obj.Next();
 * param_2 := obj.HasNext();
 */

力扣原题 · Doocs 题解来源

271. 字符串的编码与解码 🔒

中等1 种解法

标签：设计、数组、字符串

题目、示例与约束

请你设计一个算法，可以将一个 字符串列表 编码成为一个 字符串。这个编码后的字符串是可以通过网络进行高效传送的，并且可以在接收端被解码回原来的字符串列表。

1 号机（发送方）有如下函数：

string encode(vector<string> strs) {
  // ... your code
  return encoded_string;
}

2 号机（接收方）有如下函数：

vector<string> decode(string s) {
  //... your code
  return strs;
}

1 号机（发送方）执行：

string encoded_string = encode(strs);

2 号机（接收方）执行：

vector<string> strs2 = decode(encoded_string);

此时，2 号机（接收方）的 strs2 需要和 1 号机（发送方）的 strs 相同。

请你来实现这个 encode 和 decode 方法。

不允许使用任何序列化方法解决这个问题（例如 eval）。

示例 1：

输入：dummy_input = ["Hello","World"]
输出：["Hello","World"]
解释：
1 号机：
Codec encoder = new Codec();
String msg = encoder.encode(strs);
Machine 1 ---msg---> Machine 2

2 号机：
Codec decoder = new Codec();
String[] strs = decoder.decode(msg);

示例 2：

输入：dummy_input = [""]
输出：[""]

提示：

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 包含 256 个有效 ASCII 字符中的任何可能字符。

进阶：你能编写一个通用算法来处理任何可能的字符集吗？

方法一：编码字符串长度 · Go 实现

思考

直接用分隔符拼接会与串内相同字符冲突。先写入定长的长度信息，再跟原文，即可无歧义切开。

编码时把长度格式化为 $4$ 位再拼接；解码时读 $4$ 位得到长度并截取。

编码时，将字符串的长度转成固定 $4$ 位的字符串，加上字符串本身，依次拼接到结果字符串。

解码时，先取前四位字符串，得到长度，再通过长度截取后面的字符串。依次截取，最终得到字符串列表。

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

type Codec struct {
}

// Encodes a list of strings to a single string.
func (codec *Codec) Encode(strs []string) string {
	ans := &bytes.Buffer{}
	for _, s := range strs {
		t := fmt.Sprintf("%04d", len(s))
		ans.WriteString(t)
		ans.WriteString(s)
	}
	return ans.String()
}

// Decodes a single string to a list of strings.
func (codec *Codec) Decode(strs string) []string {
	ans := []string{}
	i, n := 0, len(strs)
	for i < n {
		t := strs[i : i+4]
		i += 4
		size, _ := strconv.Atoi(t)
		ans = append(ans, strs[i:i+size])
		i += size
	}
	return ans
}

// Your Codec object will be instantiated and called as such:
// var codec Codec
// codec.Decode(codec.Encode(strs));

力扣原题 · Doocs 题解来源

281. 锯齿迭代器 🔒

中等1 种解法

标签：设计、队列、数组、迭代器

题目、示例与约束

给出两个整数向量 v1 和 v2，请你实现一个迭代器，交替返回它们的元素。

实现 ZigzagIterator 类：

ZigzagIterator(List<int> v1, List<int> v2) 用两个向量 v1 和 v2 初始化对象。
boolean hasNext() 如果迭代器还有元素返回 true，否则返回 false。
int next() 返回迭代器的当前元素并将迭代器移动到下一个元素。

示例 1:

输入：v1 = [1,2], v2 = [3,4,5,6]
输出：[1,3,2,4,5,6]
解释：通过重复调用 next 直到 hasNext 返回 false，那么 next 返回的元素的顺序应该是：[1,3,2,4,5,6]。

示例 2:

输入：v1 = [1], v2 = []
输出：[1]

示例 3:

输入：v1 = [], v2 = [1]
输出：[1]

拓展：假如给你 k 个向量呢？你的代码在这种情况下的扩展性又会如何呢?

拓展声明：
“锯齿” 顺序对于 k > 2 的情况定义可能会有些歧义。所以，假如你觉得 “锯齿” 这个表述不妥，也可以认为这是一种 “循环”。例如：

输入：v1 = [1,2,3], v2 = [4,5,6,7], v3 = [8,9]
输出：[1,4,8,2,5,9,3,6,7]

方法一 · Go 实现

思考

交替输出两个向量，某侧耗尽后应跳到另一侧。用当前向量下标 $c u r$ 与各自指针，取完后 $c u r$ 模 $2$ 前进。

$h a s N e x t$ 在当前向量用尽时循环换到下一个，若转回起点则已空。

type ZigzagIterator struct {
	cur     int
	size    int
	indexes []int
	vectors [][]int
}

func Constructor(v1, v2 []int) *ZigzagIterator {
	return &ZigzagIterator{
		cur:     0,
		size:    2,
		indexes: []int{0, 0},
		vectors: [][]int{v1, v2},
	}
}

func (this *ZigzagIterator) next() int {
	vector := this.vectors[this.cur]
	index := this.indexes[this.cur]
	res := vector[index]
	this.indexes[this.cur]++
	this.cur = (this.cur + 1) % this.size
	return res
}

func (this *ZigzagIterator) hasNext() bool {
	start := this.cur
	for this.indexes[this.cur] == len(this.vectors[this.cur]) {
		this.cur = (this.cur + 1) % this.size
		if start == this.cur {
			return false
		}
	}
	return true
}

/**
 * Your ZigzagIterator object will be instantiated and called as such:
 * obj := Constructor(param_1, param_2);
 * for obj.hasNext() {
 *	 ans = append(ans, obj.next())
 * }
 */

力扣原题 · Doocs 题解来源

284. 窥视迭代器

中等1 种解法

标签：设计、数组、迭代器

题目、示例与约束

请你在设计一个迭代器，在集成现有迭代器拥有的 hasNext 和 next 操作的基础上，还额外支持 peek 操作。

实现 PeekingIterator 类：

PeekingIterator(Iterator<int> nums) 使用指定整数迭代器 nums 初始化迭代器。
int next() 返回数组中的下一个元素，并将指针移动到下个元素处。
bool hasNext() 如果数组中存在下一个元素，返回 true ；否则，返回 false 。
int peek() 返回数组中的下一个元素，但不移动指针。

注意：每种语言可能有不同的构造函数和迭代器 Iterator，但均支持 int next() 和 boolean hasNext() 函数。

示例 1：

输入：
["PeekingIterator", "next", "peek", "next", "next", "hasNext"]
[[[1, 2, 3]], [], [], [], [], []]
输出：
[null, 1, 2, 2, 3, false]

解释：
PeekingIterator peekingIterator = new PeekingIterator([1, 2, 3]); // [1,2,3]
peekingIterator.next();    // 返回 1 ，指针移动到下一个元素 [1,2,3]
peekingIterator.peek();    // 返回 2 ，指针未发生移动 [1,2,3]
peekingIterator.next();    // 返回 2 ，指针移动到下一个元素 [1,2,3]
peekingIterator.next();    // 返回 3 ，指针移动到下一个元素 [1,2,3]
peekingIterator.hasNext(); // 返回 False

提示：

1 <= nums.length <= 1000
1 <= nums[i] <= 1000
对 next 和 peek 的调用均有效
next、hasNext 和 peek 最多调用 1000 次

进阶：你将如何拓展你的设计？使之变得通用化，从而适应所有的类型，而不只是整数型？

方法一 · Go 实现

思考

底层迭代器的 $n e x t$ 会消耗元素，peek 却不能前进。缓存一次预读即可。

$p e e k$ 在尚未缓存时调用底层 $n e x t$ 并记下； $n e x t$ 优先返回缓存； $h a s N e x t$ 看缓存或底层是否还有。

/*   Below is the interface for Iterator, which is already defined for you.
 *
 *   type Iterator struct {
 *
 *   }
 *
 *   func (this *Iterator) hasNext() bool {
 *		// Returns true if the iteration has more elements.
 *   }
 *
 *   func (this *Iterator) next() int {
 *		// Returns the next element in the iteration.
 *   }
 */

type PeekingIterator struct {
	iter          *Iterator
	hasPeeked     bool
	peekedElement int
}

func Constructor(iter *Iterator) *PeekingIterator {
	return &PeekingIterator{iter, iter.hasNext(), iter.next()}
}

func (this *PeekingIterator) hasNext() bool {
	return this.hasPeeked || this.iter.hasNext()
}

func (this *PeekingIterator) next() int {
	if !this.hasPeeked {
		return this.iter.next()
	}
	this.hasPeeked = false
	return this.peekedElement
}

func (this *PeekingIterator) peek() int {
	if !this.hasPeeked {
		this.peekedElement = this.iter.next()
		this.hasPeeked = true
	}
	return this.peekedElement
}

力扣原题 · Doocs 题解来源

288. 单词的唯一缩写 🔒

中等1 种解法

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

题目、示例与约束

单词的缩写需要遵循 <起始字母><中间字母数><结尾字母> 这样的格式。如果单词只有两个字符，那么它就是它自身的缩写。

以下是一些单词缩写的范例：

dog --> d1g 因为第一个字母 'd' 和最后一个字母 'g' 之间有 1 个字母
internationalization --> i18n 因为第一个字母 'i' 和最后一个字母 'n' 之间有 18 个字母
it --> it 单词只有两个字符，它就是它自身的缩写

实现 ValidWordAbbr 类：

ValidWordAbbr(String[] dictionary) 使用单词字典 dictionary 初始化对象
boolean isUnique(string word) 如果满足下述任意一个条件，返回 true ；否则，返回 false ：
- 字典 dictionary 中没有任何其他单词的缩写与该单词 word 的缩写相同。
- 字典 dictionary 中的所有缩写与该单词 word 的缩写相同的单词都与 word 相同。

示例：

输入
["ValidWordAbbr", "isUnique", "isUnique", "isUnique", "isUnique", "isUnique"]
[[["deer", "door", "cake", "card"]], ["dear"], ["cart"], ["cane"], ["make"], ["cake"]]
输出
[null, false, true, false, true, true]

解释
ValidWordAbbr validWordAbbr = new ValidWordAbbr(["deer", "door", "cake", "card"]);
validWordAbbr.isUnique("dear"); // 返回 false，字典中的 "deer" 与输入 "dear" 的缩写都是 "d2r"，但这两个单词不相同
validWordAbbr.isUnique("cart"); // 返回 true，字典中不存在缩写为 "c2t" 的单词
validWordAbbr.isUnique("cane"); // 返回 false，字典中的 "cake" 与输入 "cane" 的缩写都是 "c2e"，但这两个单词不相同
validWordAbbr.isUnique("make"); // 返回 true，字典中不存在缩写为 "m2e" 的单词
validWordAbbr.isUnique("cake"); // 返回 true，因为 "cake" 已经存在于字典中，并且字典中没有其他缩写为 "c2e" 的单词

提示：

1 <= dictionary.length <= 3 * 10⁴
1 <= dictionary[i].length <= 20
dictionary[i] 由小写英文字母组成
1 <= word <= 20
word 由小写英文字母组成
最多调用 5000 次 isUnique

方法一：哈希表 · Go 实现

思考

缩写由首尾字母夹中间长度构成，多次查询应对字典预处理。按缩写把原词收入集合。

查询时若该缩写未出现，或集合里只有查询词本身，则唯一。

根据题目描述，我们定义一个函数 $a b b r (s)$ ，它的功能是计算单词 $s$ 的缩写。如果单词 $s$ 的长度小于 $3$ ，那么它的缩写就是它本身；否则，它的缩写是它的首字母 + (它的长度 - 2) + 它的尾字母。

接下来，我们定义一个哈希表 $d$ ，它的键是单词的缩写，值是一个集合，集合中的元素是所有缩写为该键的单词。我们遍历给定的单词字典，对于字典中的每个单词 $s$ ，我们求出它的缩写 $a b b r (s)$ ，并将 $s$ 添加到 $d [a b b r (s)]$ 中。

在判断单词 $w o r d$ 是否满足题目要求时，我们求出它的缩写 $a b b r (w o r d)$ ，如果 $a b b r (w o r d)$ 不在哈希表 $d$ 中，那么 $w o r d$ 满足题目要求；否则，我们判断 $d [a b b r (w o r d)]$ 中是否只有一个元素，如果 $d [a b b r (w o r d)]$ 中只有一个元素且该元素就是 $w o r d$ ，那么 $w o r d$ 满足题目要求。

时间复杂度方面，初始化哈希表的时间复杂度是 $O (n)$ ，其中 $n$ 是单词字典的长度；判断单词是否满足题目要求的时间复杂度是 $O (1)$ 。空间复杂度方面，哈希表的空间复杂度是 $O (n)$ 。

type ValidWordAbbr struct {
	d map[string]map[string]bool
}

func Constructor(dictionary []string) ValidWordAbbr {
	d := make(map[string]map[string]bool)
	for _, s := range dictionary {
		abbr := abbr(s)
		if _, ok := d[abbr]; !ok {
			d[abbr] = make(map[string]bool)
		}
		d[abbr][s] = true
	}
	return ValidWordAbbr{d}
}

func (this *ValidWordAbbr) IsUnique(word string) bool {
	ws := this.d[abbr(word)]
	return ws == nil || (len(ws) == 1 && ws[word])
}

func abbr(s string) string {
	n := len(s)
	if n < 3 {
		return s
	}
	return fmt.Sprintf("%c%d%c", s[0], n-2, s[n-1])
}

/**
 * Your ValidWordAbbr object will be instantiated and called as such:
 * obj := Constructor(dictionary);
 * param_1 := obj.IsUnique(word);
 */

力扣原题 · Doocs 题解来源

295. 数据流的中位数

困难1 种解法

标签：设计、双指针、数据流、排序、堆（优先队列）

题目、示例与约束

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

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

实现 MedianFinder 类:

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

示例 1：

输入
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
输出
[null, null, null, 1.5, null, 2.0]

解释
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

提示:

-10⁵ <= num <= 10⁵
在调用 findMedian 之前，数据结构中至少有一个元素
最多 5 * 10⁴ 次调用 addNum 和 findMedian

方法一：大小根堆（优先队列） · Go 实现

思考

动态求中位数若每次排序则过慢。用大根堆存较小一半、小根堆存较大一半，堆顶即可拼出中位数。

新元素先入大根堆再倒到小根堆，并保持小根堆大小至多大 $1$ ；偶数个取两顶平均，奇数个取小根堆顶。

我们可以使用两个堆来维护所有的元素，一个小根堆 $minQ$ 和一个大根堆 $maxQ$ ，其中小根堆 $minQ$ 存储较大的一半，大根堆 $maxQ$ 存储较小的一半。

调用 addNum 方法时，我们首先将元素加入到大根堆 $maxQ$ ，然后将 $maxQ$ 的堆顶元素弹出并加入到小根堆 $minQ$ 。如果此时 $minQ$ 的大小与 $maxQ$ 的大小差值大于 $1$ ，我们就将 $minQ$ 的堆顶元素弹出并加入到 $maxQ$ 。时间复杂度为 $O (\log n)$ 。

调用 findMedian 方法时，如果 $minQ$ 的大小等于 $maxQ$ 的大小，说明元素的总数为偶数，我们就可以返回 $minQ$ 的堆顶元素与 $maxQ$ 的堆顶元素的平均值；否则，我们返回 $minQ$ 的堆顶元素。时间复杂度为 $O (1)$ 。

空间复杂度为 $O (n)$ 。其中 $n$ 为元素的个数。

type MedianFinder struct {
	minq hp
	maxq hp
}

func Constructor() MedianFinder {
	return MedianFinder{hp{}, hp{}}
}

func (this *MedianFinder) AddNum(num int) {
	minq, maxq := &this.minq, &this.maxq
	heap.Push(maxq, -num)
	heap.Push(minq, -heap.Pop(maxq).(int))
	if minq.Len()-maxq.Len() > 1 {
		heap.Push(maxq, -heap.Pop(minq).(int))
	}
}

func (this *MedianFinder) FindMedian() float64 {
	minq, maxq := this.minq, this.maxq
	if minq.Len() == maxq.Len() {
		return float64(minq.IntSlice[0]-maxq.IntSlice[0]) / 2
	}
	return float64(minq.IntSlice[0])
}

type hp struct{ sort.IntSlice }

func (h hp) Less(i, j int) bool { return h.IntSlice[i] < h.IntSlice[j] }
func (h *hp) Push(v any)        { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any {
	a := h.IntSlice
	v := a[len(a)-1]
	h.IntSlice = a[:len(a)-1]
	return v
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * obj := Constructor();
 * obj.AddNum(num);
 * param_2 := obj.FindMedian();
 */

力扣原题 · Doocs 题解来源

297. 二叉树的序列化与反序列化

困难1 种解法

标签：树、深度优先搜索、广度优先搜索、设计、字符串、二叉树

题目、示例与约束

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

示例 1：

输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

示例 4：

输入：root = [1,2]
输出：[1,2]

提示：

树中结点数在范围 [0, 10⁴] 内
-1000 <= Node.val <= 1000

方法一：层序遍历 · Go 实现

思考

任意二叉树需能还原空孩子，仅存非空值会丢失结构。层序把空结点写成 $#$ ，即可按父子位置重建。

序列化时队列扩展左右孩子；反序列化按同样顺序给队头结点挂左右子。

我们可以采用层序遍历的方式对二叉树进行序列化，即从根节点开始，依次将二叉树的节点按照从上到下、从左到右的顺序加入队列中，然后将队列中的节点依次出队。如果节点不为空，则将其值加入序列化字符串中，否则加入特殊字符 #。最后将序列化字符串返回即可。

反序列化时，我们将序列化字符串按照分隔符进行切分，得到一个字符串数组，然后依次将字符串数组中的元素加入队列中。队列中的元素即为二叉树的节点，我们从队列中依次取出元素，如果元素不为 #，则将其转换为整数后作为节点的值，然后将该节点加入队列中，否则将其置为 null。最后返回根节点即可。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为二叉树的节点个数。

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

type Codec struct {
}

func Constructor() Codec {
	return Codec{}
}

// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
	if root == nil {
		return ""
	}
	q := []*TreeNode{root}
	ans := []string{}
	for len(q) > 0 {
		node := q[0]
		q = q[1:]
		if node != nil {
			ans = append(ans, strconv.Itoa(node.Val))
			q = append(q, node.Left)
			q = append(q, node.Right)
		} else {
			ans = append(ans, "#")
		}
	}
	return strings.Join(ans, ",")
}

// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {
	if data == "" {
		return nil
	}
	vals := strings.Split(data, ",")
	v, _ := strconv.Atoi(vals[0])
	i := 1
	root := &TreeNode{Val: v}
	q := []*TreeNode{root}
	for len(q) > 0 {
		node := q[0]
		q = q[1:]
		if x, err := strconv.Atoi(vals[i]); err == nil {
			node.Left = &TreeNode{Val: x}
			q = append(q, node.Left)
		}
		i++
		if x, err := strconv.Atoi(vals[i]); err == nil {
			node.Right = &TreeNode{Val: x}
			q = append(q, node.Right)
		}
		i++
	}
	return root
}

/**
 * Your Codec object will be instantiated and called as such:
 * ser := Constructor();
 * deser := Constructor();
 * data := ser.serialize(root);
 * ans := deser.deserialize(data);
 */

力扣原题 · Doocs 题解来源

303. 区域和检索 - 数组不可变

简单1 种解法

标签：设计、数组、前缀和

题目、示例与约束

给定一个整数数组 nums，处理以下类型的多个查询:

计算索引 left 和 right （包含 left 和 right）之间的 nums 元素的和，其中 left <= right

实现 NumArray 类：

NumArray(int[] nums) 使用数组 nums 初始化对象
int sumRange(int left, int right) 返回数组 nums 中索引 left 和 right 之间的元素的总和，包含 left 和 right 两点（也就是 nums[left] + nums[left + 1] + ... + nums[right] )

示例 1：

输入：
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
输出：
[null, 1, -1, -3]

解释：
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3)
numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1)) 
numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))

提示：

1 <= nums.length <= 10⁴
-10⁵ <= nums[i] <= 10⁵
0 <= left <= right < nums.length
最多调用 10⁴ 次 sumRange 方法

方法一：前缀和 · Go 实现

思考

数组不变而区间求和多次。每次现场累加 $[l e f t, r i g h t]$ 为 $O (n)$ ，询问一多则总代价过高。

前缀和把任意区间和写成两点差： $s [i]$ 表示前 $i$ 个元素之和，则 $s u m (l e f t, r i g h t) = s [r i g h t + 1] - s [l e f t]$ 。构造时一次扫描即可，此后每次询问 $O (1)$ 。数组只读，无需支持修改。

我们创建一个长度为 $n + 1$ 的前缀和数组 $s$ ，其中 $s [i]$ 表示前 $i$ 个元素的前缀和，即 $s [i] = \sum_{j = 0}^{i - 1} n u m s [j]$ ，那么索引 $[l e f t, r i g h t]$ 之间的元素的和就可以表示为 $s [r i g h t + 1] - s [l e f t]$ 。

初始化前缀和数组 $s$ 的时间复杂度为 $O (n)$ ，查询的时间复杂度为 $O (1)$ 。空间复杂度 $O (n)$ 。

type NumArray struct {
	s []int
}

func Constructor(nums []int) NumArray {
	n := len(nums)
	s := make([]int, n+1)
	for i, v := range nums {
		s[i+1] = s[i] + v
	}
	return NumArray{s}
}

func (this *NumArray) SumRange(left int, right int) int {
	return this.s[right+1] - this.s[left]
}

/**
 * Your NumArray object will be instantiated and called as such:
 * obj := Constructor(nums);
 * param_1 := obj.SumRange(left,right);
 */

力扣原题 · Doocs 题解来源

304. 二维区域和检索 - 矩阵不可变

中等1 种解法

标签：设计、数组、矩阵、前缀和

题目、示例与约束

给定一个二维矩阵 matrix，以下类型的多个请求：

计算其子矩形范围内元素的总和，该子矩阵的 左上角 为 (row1, col1) ，右下角 为 (row2, col2) 。

实现 NumMatrix 类：

NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, col1) 、右下角 (row2, col2) 所描述的子矩阵的元素总和。

示例 1：

输入: 
["NumMatrix","sumRegion","sumRegion","sumRegion"]
[[[[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]],[2,1,4,3],[1,1,2,2],[1,2,2,4]]
输出: 
[null, 8, 11, 12]

解释:
NumMatrix numMatrix = new NumMatrix([[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (红色矩形框的元素总和)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (绿色矩形框的元素总和)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (蓝色矩形框的元素总和)

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
-10⁵ <= matrix[i][j] <= 10⁵
0 <= row1 <= row2 < m
0 <= col1 <= col2 < n
最多调用 10⁴ 次 sumRegion 方法

方法一：二维前缀和 · Go 实现

思考

矩阵只读，需多次求子矩形和。若每次对子矩形现场累加，询问次数一大则无法接受。

二维前缀和把矩形和化为四点容斥： $s [i + 1] [j + 1]$ 表示左上角到 $(i, j)$ 的和，目标矩形等于右下前缀减去上方与左方、再加回重叠角。初始化 $O (m n)$ 后每次询问 $O (1)$ 。容斥顺序与代码中加减号一一对应。

我们用 $s [i + 1] [j + 1]$ 表示第 $i$ 行第 $j$ 列左上部分所有元素之和，下标 $i$ 和 $j$ 均从 $0$ 开始。可以得到以下前缀和公式：

s [i + 1] [j + 1] = s [i + 1] [j] + s [i] [j + 1] - s [i] [j] + n u m s [i] [j]

那么分别以 $(x_{1}, y_{1})$ 和 $(x_{2}, y_{2})$ 为左上角和右下角的矩形的元素之和为：

s [x_{2} + 1] [y_{2} + 1] - s [x_{2} + 1] [y_{1}] - s [x_{1}] [y_{2} + 1] + s [x_{1}] [y_{1}]

我们在初始化方法中预处理出前缀和数组 $s$ ，在查询方法中直接返回上述公式的结果即可。

初始化的时间复杂度为 $O (m \times n)$ ，查询的时间复杂度为 $O (1)$ 。空间复杂度为 $O (m \times n)$ 。

type NumMatrix struct {
	s [][]int
}

func Constructor(matrix [][]int) NumMatrix {
	m, n := len(matrix), len(matrix[0])
	s := make([][]int, m+1)
	for i := range s {
		s[i] = make([]int, n+1)
	}
	for i, row := range matrix {
		for j, v := range row {
			s[i+1][j+1] = s[i+1][j] + s[i][j+1] - s[i][j] + v
		}
	}
	return NumMatrix{s}
}

func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
	return this.s[row2+1][col2+1] - this.s[row2+1][col1] - this.s[row1][col2+1] + this.s[row1][col1]
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * obj := Constructor(matrix);
 * param_1 := obj.SumRegion(row1,col1,row2,col2);
 */

力扣原题 · Doocs 题解来源

307. 区域和检索 - 数组可修改

中等2 种解法

标签：设计、树状数组、线段树、数组、分治

题目、示例与约束

给你一个数组 nums ，请你完成两类查询。

其中一类查询要求更新数组 nums 下标对应的值
另一类查询要求返回数组 nums 中索引 left 和索引 right 之间（包含）的nums元素的和，其中 left <= right

实现 NumArray 类：

NumArray(int[] nums) 用整数数组 nums 初始化对象
void update(int index, int val) 将 nums[index] 的值更新为 val
int sumRange(int left, int right) 返回数组 nums 中索引 left 和索引 right 之间（包含）的nums元素的和（即，nums[left] + nums[left + 1], ..., nums[right]）

示例 1：

输入：
["NumArray", "sumRange", "update", "sumRange"]
[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
输出：
[null, 9, null, 8]

解释：
NumArray numArray = new NumArray([1, 3, 5]);
numArray.sumRange(0, 2); // 返回 1 + 3 + 5 = 9
numArray.update(1, 2);   // nums = [1,2,5]
numArray.sumRange(0, 2); // 返回 1 + 2 + 5 = 8

提示：

1 <= nums.length <= 3 * 10⁴
-100 <= nums[i] <= 100
0 <= index < nums.length
-100 <= val <= 100
0 <= left <= right < nums.length
调用 update 和 sumRange 方法次数不大于 3 * 10⁴

方法一：树状数组 · Go 实现

思考

相对 303 题，本题需在单点修改后仍能快速求区间和。若每次修改后重建前缀和，或每次询问线性扫描，均无法同时把两类操作压到对数级。

树状数组用低位差分维护前缀和： $u p d a t e$ 沿 $x + = x & - x$ 向上加增量， $q u e r y$ 沿 $x - = x & - x$ 向下取前缀。区间和写成两个前缀之差；修改时先读出旧值再写入差值。构造按位插入即可。

树状数组，也称作“二叉索引树”（Binary Indexed Tree）或 Fenwick 树。它可以高效地实现如下两个操作：

单点更新 $u p d a t e (x, d e l t a)$ ：把序列 $x$ 位置的数加上一个值 $d e l t a$ ；
前缀和查询 $q u e r y (x)$ ：查询序列 $[1, . . . x]$ 区间的区间和，即位置 $x$ 的前缀和。

这两个操作的时间复杂度均为 $O (\log n)$ 。

树状数组最基本的功能就是求比某点 $x$ 小的点的个数（这里的比较是抽象的概念，可以是数的大小、坐标的大小、质量的大小等等）。

对于本题，我们在构造函数中，先创建一个树状数组，然后遍历数组中每个元素的下标 $i$ （从 $1$ 开始）和对应的值 $v$ ，调用 $u p d a t e (i, v)$ ，即可完成树状数组的初始化。时间复杂度为 $O (n \log n)$ 。

对于 $s u m R a n g e (l e f t, r i g h t)$ ，我们可以通过 $q u e r y (r i g h t + 1) - q u e r y (l e f t)$ 得到区间和。时间复杂度为 $O (\log n)$ 。

对于 $u p d a t e (i n d e x, v a l)$ ，我们可以先通过 $s u m R a n g e (i n d e x, i n d e x)$ 得到原来的值 $p r e v$ ，然后调用 $u p d a t e (i n d e x, v a l - p r e v)$ ，即可完成更新。时间复杂度为 $O (\log n)$ 。

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

type BinaryIndexedTree struct {
	n int
	c []int
}

func newBinaryIndexedTree(n int) *BinaryIndexedTree {
	c := make([]int, n+1)
	return &BinaryIndexedTree{n, c}
}

func (t *BinaryIndexedTree) update(x, delta int) {
	for ; x <= t.n; x += x & -x {
		t.c[x] += delta
	}
}

func (t *BinaryIndexedTree) query(x int) (s int) {
	for ; x > 0; x -= x & -x {
		s += t.c[x]
	}
	return s
}

type NumArray struct {
	tree *BinaryIndexedTree
}

func Constructor(nums []int) NumArray {
	tree := newBinaryIndexedTree(len(nums))
	for i, v := range nums {
		tree.update(i+1, v)
	}
	return NumArray{tree}
}

func (t *NumArray) Update(index int, val int) {
	prev := t.SumRange(index, index)
	t.tree.update(index+1, val-prev)
}

func (t *NumArray) SumRange(left int, right int) int {
	return t.tree.query(right+1) - t.tree.query(left)
}

/**
 * Your NumArray object will be instantiated and called as such:
 * obj := Constructor(nums);
 * obj.Update(index,val);
 * param_2 := obj.SumRange(left,right);
 */

方法二：线段树 · Go 实现

思考

树状数组擅长前缀和，对更一般的区间信息不够直观。线段树按中点递归划分 $[l, r]$ ，每个内部结点保存子区间和，单点修改只沿根到叶的 $O (\log n)$ 条链更新。

询问时把 $[l e f t, r i g h t]$ 拆成 $O (\log n)$ 个结点区间相加。时间与方法一同阶，实现改为显式左右儿子，便于扩展到最值等运算。

线段树将整个区间分割为多个不连续的子区间，子区间的数量不超过 $\log (w i d t h)$ 。更新某个元素的值，只需要更新 $\log (w i d t h)$ 个区间，并且这些区间都包含在一个包含该元素的大区间内。

线段树的每个节点代表一个区间；
线段树具有唯一的根节点，代表的区间是整个统计范围，如 $[1, N]$ ；
线段树的每个叶子节点代表一个长度为 $1$ 的元区间 $[x, x]$ ；
对于每个内部节点 $[l, r]$ ，它的左儿子是 $[l, m i d]$ ，右儿子是 $[m i d + 1, r]$ , 其中 $m i d = ⌊ \frac{l + r}{2} ⌋$ （即向下取整）。

对于本题，构造函数的时间复杂度为 $O (n \log n)$ ，其他操作的时间复杂度为 $O (\log n)$ 。空间复杂度为 $O (n)$ 。

type Node struct {
	l, r, v int
}

type SegmentTree struct {
	tr   []Node
	nums []int
}

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

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

func (tree *SegmentTree) modify(u, x, v int) {
	if tree.tr[u].l == x && tree.tr[u].r == x {
		tree.tr[u].v = v
		return
	}
	mid := (tree.tr[u].l + tree.tr[u].r) >> 1
	if x <= mid {
		tree.modify(u<<1, x, v)
	} else {
		tree.modify(u<<1|1, x, v)
	}
	tree.pushup(u)
}

func (tree *SegmentTree) query(u, l, r int) (v int) {
	if tree.tr[u].l >= l && tree.tr[u].r <= r {
		return tree.tr[u].v
	}
	mid := (tree.tr[u].l + tree.tr[u].r) >> 1
	if l <= mid {
		v += tree.query(u<<1, l, r)
	}
	if r > mid {
		v += tree.query(u<<1|1, l, r)
	}
	return v
}

func (tree *SegmentTree) pushup(u int) {
	tree.tr[u].v = tree.tr[u<<1].v + tree.tr[u<<1|1].v
}

type NumArray struct {
	tree *SegmentTree
}

func Constructor(nums []int) NumArray {
	return NumArray{
		tree: newSegmentTree(nums),
	}
}

func (this *NumArray) Update(index int, val int) {
	this.tree.modify(1, index+1, val)
}

func (this *NumArray) SumRange(left int, right int) int {
	return this.tree.query(1, left+1, right+1)
}

/**
 * Your NumArray object will be instantiated and called as such:
 * obj := Constructor(nums);
 * obj.Update(index,val);
 * param_2 := obj.SumRange(left,right);
 */

力扣原题 · Doocs 题解来源

308. 二维区域和检索 - 矩阵可修改 🔒

中等1 种解法

标签：设计、树状数组、线段树、数组、矩阵

题目、示例与约束

给你一个二维矩阵 matrix ，处理以下类型的多个查询:

更新 matrix 中单元格的值。
计算由 左上角 (row1, col1) 和 右下角 (row2, col2) 定义的 matrix 内矩阵元素的和。

实现 NumMatrix 类：

NumMatrix(int[][] matrix) 用整数矩阵 matrix 初始化对象。
void update(int row, int col, int val) 更新 matrix[row][col] 的值到 val 。
int sumRegion(int row1, int col1, int row2, int col2) 返回矩阵 matrix 中指定矩形区域元素的和，该区域由 左上角 (row1, col1) 和 右下角 (row2, col2) 界定。

示例 1：

输入
["NumMatrix", "sumRegion", "update", "sumRegion"]
[[[[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]], [2, 1, 4, 3], [3, 2, 2], [2, 1, 4, 3]]
输出
[null, 8, null, 10]

解释
NumMatrix numMatrix = new NumMatrix([[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]);
numMatrix.sumRegion(2, 1, 4, 3); // 返回 8 (即, 左侧红色矩形的和)
numMatrix.update(3, 2, 2);       // 矩阵从左图变为右图
numMatrix.sumRegion(2, 1, 4, 3); // 返回 10 (即，右侧红色矩形的和)

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
-1000 <= matrix[i][j] <= 1000
0 <= row < m
0 <= col < n
-1000 <= val <= 1000
0 <= row1 <= row2 < m
0 <= col1 <= col2 < n
最多调用5000 次 sumRegion 和 update 方法

方法一：树状数组 · Go 实现

思考

二维矩阵既要改单格，又要求子矩形和。对每次询问现场累加，或每次修改后重建二维前缀，都无法同时压低两类操作。

代码为每一行建一棵树状数组，行内用前缀和差得到 $[c o l 1, c o l 2]$ ，再对 $r o w 1 \dots r o w 2$ 的行求和。修改只触及对应行。行数通常不大，故实现比真正的二维树状数组更直接。

树状数组，也称作“二叉索引树”（Binary Indexed Tree）或 Fenwick 树。它可以高效地实现如下两个操作：

单点更新 update(x, delta)：把序列 x 位置的数加上一个值 delta；
前缀和查询 query(x)：查询序列 [1,...x] 区间的区间和，即位置 x 的前缀和。

这两个操作的时间复杂度均为 $O (\log n)$ 。

对于本题，可以构建二维树状数组。

type BinaryIndexedTree struct {
	n int
	c []int
}

func newBinaryIndexedTree(n int) *BinaryIndexedTree {
	c := make([]int, n+1)
	return &BinaryIndexedTree{n, c}
}

func (this *BinaryIndexedTree) lowbit(x int) int {
	return x & -x
}

func (this *BinaryIndexedTree) update(x, delta int) {
	for x <= this.n {
		this.c[x] += delta
		x += this.lowbit(x)
	}
}

func (this *BinaryIndexedTree) query(x int) int {
	s := 0
	for x > 0 {
		s += this.c[x]
		x -= this.lowbit(x)
	}
	return s
}

type NumMatrix struct {
	trees []*BinaryIndexedTree
}

func Constructor(matrix [][]int) NumMatrix {
	n := len(matrix[0])
	var trees []*BinaryIndexedTree
	for _, row := range matrix {
		tree := newBinaryIndexedTree(n)
		for j, v := range row {
			tree.update(j+1, v)
		}
		trees = append(trees, tree)
	}
	return NumMatrix{trees}
}

func (this *NumMatrix) Update(row int, col int, val int) {
	tree := this.trees[row]
	prev := tree.query(col+1) - tree.query(col)
	tree.update(col+1, val-prev)
}

func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
	s := 0
	for i := row1; i <= row2; i++ {
		tree := this.trees[i]
		s += tree.query(col2+1) - tree.query(col1)
	}
	return s
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * obj := Constructor(matrix);
 * obj.Update(row,col,val);
 * param_2 := obj.SumRegion(row1,col1,row2,col2);
 */

力扣原题 · Doocs 题解来源

341. 扁平化嵌套列表迭代器

中等1 种解法

标签：栈、树、深度优先搜索、设计、队列、迭代器

题目、示例与约束

给你一个嵌套的整数列表 nestedList 。每个元素要么是一个整数，要么是一个列表；该列表的元素也可能是整数或者是其他列表。请你实现一个迭代器将其扁平化，使之能够遍历这个列表中的所有整数。

实现扁平迭代器类 NestedIterator ：

NestedIterator(List<NestedInteger> nestedList) 用嵌套列表 nestedList 初始化迭代器。
int next() 返回嵌套列表的下一个整数。
boolean hasNext() 如果仍然存在待迭代的整数，返回 true ；否则，返回 false 。

你的代码将会用下述伪代码检测：

initialize iterator with nestedList
res = []
while iterator.hasNext()
    append iterator.next() to the end of res
return res

如果 res 与预期的扁平化列表匹配，那么你的代码将会被判为正确。

示例 1：

输入：nestedList = [[1,1],2,[1,1]]
输出：[1,1,2,1,1]
解释：通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,1,2,1,1]。

示例 2：

输入：nestedList = [1,[4,[6]]]
输出：[1,4,6]
解释：通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,4,6]。

提示：

1 <= nestedList.length <= 500
嵌套列表中的整数值在范围 [-10⁶, 10⁶] 内

方法一：递归 · Go 实现

思考

把嵌套整数摊平成迭代器。每次 next 再搜索下一叶子会把查找摊到调用上，且实现更绕。嵌套深度有限，可在构造时一次展开。

DFS 遇整数则写入数组，遇列表则递归。next/hasNext 只移动下标。空间换取每次调用 $O (1)$ 。

根据题意要求可以将 NestedInteger 数据结构视作一个 N 叉树，当元素为一个整数时，该节点是 N 叉树的叶子节点，当元素为一个整数数组时，该节点是 N 叉树的非叶子节点，数组中的每一个元素包含子树的所有节点。故直接递归遍历 N 叉树并记录所有的叶子节点即可。

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * type NestedInteger struct {
 * }
 *
 * // Return true if this NestedInteger holds a single integer, rather than a nested list.
 * func (this NestedInteger) IsInteger() bool {}
 *
 * // Return the single integer that this NestedInteger holds, if it holds a single integer
 * // The result is undefined if this NestedInteger holds a nested list
 * // So before calling this method, you should have a check
 * func (this NestedInteger) GetInteger() int {}
 *
 * // Set this NestedInteger to hold a single integer.
 * func (n *NestedInteger) SetInteger(value int) {}
 *
 * // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 * func (this *NestedInteger) Add(elem NestedInteger) {}
 *
 * // Return the nested list that this NestedInteger holds, if it holds a nested list
 * // The list length is zero if this NestedInteger holds a single integer
 * // You can access NestedInteger's List element directly if you want to modify it
 * func (this NestedInteger) GetList() []*NestedInteger {}
 */

type NestedIterator struct {
	nums []int
	i    int
}

func Constructor(nestedList []*NestedInteger) *NestedIterator {
	var dfs func([]*NestedInteger)
	nums := []int{}
	i := -1
	dfs = func(ls []*NestedInteger) {
		for _, x := range ls {
			if x.IsInteger() {
				nums = append(nums, x.GetInteger())
			} else {
				dfs(x.GetList())
			}
		}
	}
	dfs(nestedList)
	return &NestedIterator{nums, i}
}

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

func (this *NestedIterator) HasNext() bool {
	return this.i+1 < len(this.nums)
}

力扣原题 · Doocs 题解来源

346. 数据流中的移动平均值 🔒

简单2 种解法

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

题目、示例与约束

给定一个整数数据流和一个窗口大小，根据该滑动窗口的大小，计算其所有整数的移动平均值。

实现 MovingAverage 类：

MovingAverage(int size) 用窗口大小 size 初始化对象。
double next(int val) 计算并返回数据流中最后 size 个值的移动平均值。

示例：

输入：
["MovingAverage", "next", "next", "next", "next"]
[[3], [1], [10], [3], [5]]
输出：
[null, 1.0, 5.5, 4.66667, 6.0]

解释：
MovingAverage movingAverage = new MovingAverage(3);
movingAverage.next(1); // 返回 1.0 = 1 / 1
movingAverage.next(10); // 返回 5.5 = (1 + 10) / 2
movingAverage.next(3); // 返回 4.66667 = (1 + 10 + 3) / 3
movingAverage.next(5); // 返回 6.0 = (10 + 3 + 5) / 3

提示：

1 <= size <= 1000
-10⁵ <= val <= 10⁵
最多调用 next 方法 10⁴ 次

方法一：循环数组 · Go 实现

思考

数据流上固定窗口的平均值。每次重算窗口和为 $O (s i z e)$ 。维护和即可 $O (1)$ 更新。

循环数组记下窗口，下标 $c n t mod s i z e$ 覆盖最旧值：和先减旧加新。平均值为 $s / min (c n t, s i z e)$ 。

我们定义一个变量 $s$ ，用于计算当前最后 $size$ 个元素的和，用一个变量 $cnt$ 记录当前元素的总数。另外，我们用一个长度为 $size$ 的数组 $data$ 记录每个位置的元素对应的值。

调用 $next$ 函数时，我们先计算出 $val$ 要存放的下标 $i$ ，然后我们更新元素和 $s$ ，并且将下标 $i$ 处的值设置为 $val$ ，同时将元素的个数加一。最后，我们返回 $\frac{s}{min (cnt, size)}$ 的值即可。

时间复杂度 $O (1)$ ，空间复杂度 $O (n)$ ，其中 $n$ 是题目给定的整数 $size$ 。

type MovingAverage struct {
	s    int
	cnt  int
	data []int
}

func Constructor(size int) MovingAverage {
	return MovingAverage{
		data: make([]int, size),
	}
}

func (this *MovingAverage) Next(val int) float64 {
	i := this.cnt % len(this.data)
	this.s += val - this.data[i]
	this.data[i] = val
	this.cnt++
	return float64(this.s) / float64(min(this.cnt, len(this.data)))
}

/**
 * Your MovingAverage object will be instantiated and called as such:
 * obj := Constructor(size);
 * param_1 := obj.Next(val);
 */

方法二：队列 · Go 实现

思考

循环数组需手写取模。队列保存窗口：满则弹出队首并减和，再入队新值。语义相同，实现更直观。

我们可以使用一个队列 $q$ 来存储最后 $size$ 个元素，同时用一个变量 $s$ 来记录这 $size$ 个元素的和。

在调用 $next$ 函数时，我们首先判断队列 $q$ 的长度是否等于 $size$ ，如果等于 $size$ ，则将队列 $q$ 的头部元素出队，并且更新 $s$ 的值。然后将 $val$ 入队，并且更新 $s$ 的值。最后返回 $\frac{s}{len (q)}$ 的值即可。

时间复杂度 $O (1)$ ，空间复杂度 $O (n)$ ，其中 $n$ 是题目给定的整数 $size$ 。

type MovingAverage struct {
	q []int
	s int
	n int
}

func Constructor(size int) MovingAverage {
	return MovingAverage{n: size}
}

func (this *MovingAverage) Next(val int) float64 {
	if len(this.q) == this.n {
		this.s -= this.q[0]
		this.q = this.q[1:]
	}
	this.q = append(this.q, val)
	this.s += val
	return float64(this.s) / float64(len(this.q))
}

/**
 * Your MovingAverage object will be instantiated and called as such:
 * obj := Constructor(size);
 * param_1 := obj.Next(val);
 */

力扣原题 · Doocs 题解来源

348. 设计井字棋 🔒

中等1 种解法

标签：设计、数组、哈希表、矩阵、模拟

题目、示例与约束

请在 n × n 的棋盘上，实现一个判定井字棋（Tic-Tac-Toe）胜负的神器，判断每一次玩家落子后，是否有胜出的玩家。

在这个井字棋游戏中，会有 2 名玩家，他们将轮流在棋盘上放置自己的棋子。

在实现这个判定器的过程中，你可以假设以下这些规则一定成立：

1. 每一步棋都是在棋盘内的，并且只能被放置在一个空的格子里；

2. 一旦游戏中有一名玩家胜出的话，游戏将不能再继续；

3. 一个玩家如果在同一行、同一列或者同一斜对角线上都放置了自己的棋子，那么他便获得胜利。

示例:

给定棋盘边长 n = 3, 玩家 1 的棋子符号是 "X"，玩家 2 的棋子符号是 "O"。

TicTacToe toe = new TicTacToe(3);

toe.move(0, 0, 1); -> 函数返回 0 (此时，暂时没有玩家赢得这场对决)
|X| | |
| | | |    // 玩家 1 在 (0, 0) 落子。
| | | |

toe.move(0, 2, 2); -> 函数返回 0 (暂时没有玩家赢得本场比赛)
|X| |O|
| | | |    // 玩家 2 在 (0, 2) 落子。
| | | |

toe.move(2, 2, 1); -> 函数返回 0 (暂时没有玩家赢得比赛)
|X| |O|
| | | |    // 玩家 1 在 (2, 2) 落子。
| | |X|

toe.move(1, 1, 2); -> 函数返回 0 (暂没有玩家赢得比赛)
|X| |O|
| |O| |    // 玩家 2 在 (1, 1) 落子。
| | |X|

toe.move(2, 0, 1); -> 函数返回 0 (暂无玩家赢得比赛)
|X| |O|
| |O| |    // 玩家 1 在 (2, 0) 落子。
|X| |X|

toe.move(1, 0, 2); -> 函数返回 0 (没有玩家赢得比赛)
|X| |O|
|O|O| |    // 玩家 2 在 (1, 0) 落子.
|X| |X|

toe.move(2, 1, 1); -> 函数返回 1 (此时，玩家 1 赢得了该场比赛)
|X| |O|
|O|O| |    // 玩家 1 在 (2, 1) 落子。
|X|X|X|

提示：

2 <= n <= 100
玩家是 1 或 2。
0 <= row, col < n
每次调用 move 时 (row, col) 都是不同的。
最多调用 move n² 次。

进阶:
您有没有可能将每一步的 move() 操作优化到比 O(n²) 更快吗?

方法一：计数 · Go 实现

思考

每次落子后判断胜负。扫全盘为 $O (n^{2})$ 。一行、一列或一对角集齐 $n$ 子即胜，只需这些计数。

每位玩家维护各行、各列、两对角的棋子数。落子时对应计数加一，任一达到 $n$ 则获胜。单步 $O (1)$ 。

我们可以使用一个长度为 $n \times 2 + 2$ 的数组来记录每个玩家在每一行、每一列、两条对角线上的棋子数。我们需要两个这样的数组，分别记录两个玩家的棋子数。

当一个玩家在某一行、某一列、某一对角线上的棋子数等于 $n$ 时，该玩家获胜。

时间复杂度方面，每次落子的时间复杂度为 $O (1)$ 。空间复杂度为 $O (n)$ ，其中 $n$ 为棋盘的边长。

type TicTacToe struct {
	n   int
	cnt [][]int
}

func Constructor(n int) TicTacToe {
	cnt := make([][]int, 2)
	for i := range cnt {
		cnt[i] = make([]int, (n<<1)+2)
	}
	return TicTacToe{n, cnt}
}

func (this *TicTacToe) Move(row int, col int, player int) int {
	cur := this.cnt[player-1]
	cur[row]++
	cur[this.n+col]++
	if row == col {
		cur[this.n<<1]++
	}
	if row+col == this.n-1 {
		cur[this.n<<1|1]++
	}
	if cur[row] == this.n || cur[this.n+col] == this.n || cur[this.n<<1] == this.n || cur[this.n<<1|1] == this.n {
		return player
	}
	return 0
}

/**
 * Your TicTacToe object will be instantiated and called as such:
 * obj := Constructor(n);
 * param_1 := obj.Move(row,col,player);
 */

力扣原题 · Doocs 题解来源

352. 将数据流变为多个不相交区间

困难1 种解法

标签：并查集、设计、哈希表、二分查找、数据流、有序集合

题目、示例与约束

给你一个由非负整数组成的数据流输入 a₁, a₂, ..., a_n，请你将目前为止看到的数字汇总为一组不相交的区间列表。

实现 SummaryRanges 类：

SummaryRanges() 初始化一个空的数据流对象。
void addNum(int value) 将整数 value 添加到数据流中。
int[][] getIntervals() 返回当前数据流中的整数汇总为一组不相交的区间列表 [start_i, end_i]。答案应按 start_i 升序排序。

示例 1：

输入
["SummaryRanges", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals"]
[[], [1], [], [3], [], [7], [], [2], [], [6], []]
输出
[null, null, [[1, 1]], null, [[1, 1], [3, 3]], null, [[1, 1], [3, 3], [7, 7]], null, [[1, 3], [7, 7]], null, [[1, 3], [6, 7]]]

解释
SummaryRanges summaryRanges = new SummaryRanges();
summaryRanges.addNum(1);      // arr = [1]
summaryRanges.getIntervals(); // 返回 [[1, 1]]
summaryRanges.addNum(3);      // arr = [1, 3]
summaryRanges.getIntervals(); // 返回 [[1, 1], [3, 3]]
summaryRanges.addNum(7);      // arr = [1, 3, 7]
summaryRanges.getIntervals(); // 返回 [[1, 1], [3, 3], [7, 7]]
summaryRanges.addNum(2);      // arr = [1, 2, 3, 7]
summaryRanges.getIntervals(); // 返回 [[1, 3], [7, 7]]
summaryRanges.addNum(6);      // arr = [1, 2, 3, 6, 7]
summaryRanges.getIntervals(); // 返回 [[1, 3], [6, 7]]

提示：

0 <= value <= 10⁴
最多会调用 addNum 和 getIntervals 方法 3 * 10⁴ 次。
最多会调用 getIntervals 方法 10² 次。

进阶：如果存在大量合并，并且与数据流的大小相比，不相交区间的数量很小，该怎么办?

方法一：Go 实现（halfrost） · Go 实现

halfrost · 源码 · MIT 许可

本次根据原始 Go 源码整理的中文说明，非 halfrost 书籍原文。

用映射记录已经加入的整数，用切片保存去重后的值。AddNum 在插入后重新排序；GetIntervals 顺序扫描，把相邻整数合并为闭区间。设已有 U 个不同整数，单次 AddNum 的排序上界为 O(U log U)，GetIntervals 为 O(U)。这是原仓库的排序实现，没有改写为增量维护区间的实现。

import "sort"

type SummaryRanges struct {
	nums []int
	mp   map[int]int
}

func Constructor() SummaryRanges {
	return SummaryRanges{
		nums: []int{},
		mp:   map[int]int{},
	}
}

func (this *SummaryRanges) AddNum(val int) {
	if _, ok := this.mp[val]; !ok {
		this.mp[val] = 1
		this.nums = append(this.nums, val)
	}
	sort.Ints(this.nums)
}

func (this *SummaryRanges) GetIntervals() [][]int {
	n := len(this.nums)
	var ans [][]int
	if n == 0 {
		return ans
	}
	if n == 1 {
		ans = append(ans, []int{this.nums[0], this.nums[0]})
		return ans
	}
	start, end := this.nums[0], this.nums[0]
	ans = append(ans, []int{start, end})
	index := 0
	for i := 1; i < n; i++ {
		if this.nums[i] == end+1 {
			end = this.nums[i]
			ans[index][1] = end
		} else {
			start, end = this.nums[i], this.nums[i]
			ans = append(ans, []int{start, end})
			index++
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

353. 贪吃蛇 🔒

中等1 种解法

标签：设计、队列、数组、哈希表、模拟

题目、示例与约束

请你设计一个贪吃蛇游戏，该游戏将会在一个 屏幕尺寸 = 宽度 x 高度 的屏幕上运行。如果你不熟悉这个游戏，可以点击这里在线试玩。

起初时，蛇在左上角的 (0, 0) 位置，身体长度为 1 个单位。

你将会被给出一个数组形式的食物位置序列 food ，其中 food[i] = (r_i, c_i) 。当蛇吃到食物时，身子的长度会增加 1 个单位，得分也会 +1 。

食物不会同时出现，会按列表的顺序逐一显示在屏幕上。比方讲，第一个食物被蛇吃掉后，第二个食物才会出现。

当一个食物在屏幕上出现时，保证不会出现在被蛇身体占据的格子里。

如果蛇越界（与边界相撞）或者头与 移动后 的身体相撞（即，身长为 4 的蛇无法与自己相撞），游戏结束。

实现 SnakeGame 类：

SnakeGame(int width, int height, int[][] food) 初始化对象，屏幕大小为 height x width ，食物位置序列为 food
int move(String direction) 返回蛇在方向 direction 上移动后的得分。如果游戏结束，返回 -1 。

示例 1：

输入：
["SnakeGame", "move", "move", "move", "move", "move", "move"]
[[3, 2, [[1, 2], [0, 1]]], ["R"], ["D"], ["R"], ["U"], ["L"], ["U"]]
输出：
[null, 0, 0, 1, 1, 2, -1]

解释：
SnakeGame snakeGame = new SnakeGame(3, 2, [[1, 2], [0, 1]]);
snakeGame.move("R"); // 返回 0
snakeGame.move("D"); // 返回 0
snakeGame.move("R"); // 返回 1 ，蛇吃掉了第一个食物，同时第二个食物出现在 (0, 1)
snakeGame.move("U"); // 返回 1
snakeGame.move("L"); // 返回 2 ，蛇吃掉了第二个食物，没有出现更多食物
snakeGame.move("U"); // 返回 -1 ，蛇与边界相撞，游戏结束

提示：

1 <= width, height <= 10⁴
1 <= food.length <= 50
food[i].length == 2
0 <= r_i < height
0 <= c_i < width
direction.length == 1
direction is 'U', 'D', 'L', or 'R'.
最多调用 10⁴ 次 move 方法

方法一：双端队列模拟 · Go 实现

思考

模拟贪吃蛇：越界或咬身结束，吃到食物变长。身体是队列，头尾变动频繁。

双端队列存身体（头在队首），集合判碰撞。先算新头：出界则 $- 1$ ；吃到则加分且不丢尾，否则弹出尾并移出集合。再判新头是否在身上，最后入队。尾先移除才能正确处理「紧随旧尾」的格子。

我们可以使用双端队列来模拟蛇的移动。

定义一个双端队列 $q$ ，其中保存蛇的身体坐标，队头为蛇头，队尾为蛇尾。同时使用一个集合 $v i s$ 来保存蛇的身体坐标，用于快速判断蛇头是否与蛇身相撞。

定义一个变量 $s c o r e$ 来保存蛇的得分，初始值为 $0$ ；定义一个变量 $i d x$ 来保存当前食物的索引，初始值为 $0$ 。

每次移动时，首先判断蛇头是否与边界相撞，如果相撞则游戏结束，返回 $- 1$ ；否则，判断蛇头是否与食物重合，如果重合则蛇的得分加 $1$ ，同时食物索引 $i d x$ 加 $1$ ；否则，蛇的身体长度不变，需要将蛇尾从队尾弹出，并从集合 $v i s$ 中删除对应的坐标。

然后，判断蛇头是否与蛇身相撞，如果相撞则游戏结束，返回 $- 1$ ；否则，将蛇头的坐标加入集合 $v i s$ 中，并从队头加入蛇头的坐标。

最后，返回蛇的得分 $s c o r e$ 。

时间复杂度 $O (k)$ ，空间复杂度 $O (k)$ ，其中 $k$ 为移动的次数。

type SnakeGame struct {
	m     int
	n     int
	food  [][]int
	score int
	idx   int
	q     []int
	vis   map[int]bool
}

func Constructor(width int, height int, food [][]int) SnakeGame {
	return SnakeGame{height, width, food, 0, 0, []int{0}, map[int]bool{}}
}

func (this *SnakeGame) Move(direction string) int {
	f := func(i, j int) int {
		return i*this.n + j
	}
	p := this.q[0]
	i, j := p/this.n, p%this.n
	x, y := i, j
	if direction == "U" {
		x--
	} else if direction == "D" {
		x++
	} else if direction == "L" {
		y--
	} else {
		y++
	}
	if x < 0 || x >= this.m || y < 0 || y >= this.n {
		return -1
	}
	if this.idx < len(this.food) && x == this.food[this.idx][0] && y == this.food[this.idx][1] {
		this.score++
		this.idx++
	} else {
		t := this.q[len(this.q)-1]
		this.q = this.q[:len(this.q)-1]
		this.vis[t] = false
	}
	cur := f(x, y)
	if this.vis[cur] {
		return -1
	}
	this.q = append([]int{cur}, this.q...)
	this.vis[cur] = true
	return this.score
}

/**
 * Your SnakeGame object will be instantiated and called as such:
 * obj := Constructor(width, height, food);
 * param_1 := obj.Move(direction);
 */

力扣原题 · Doocs 题解来源

355. 设计推特

中等1 种解法

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

题目、示例与约束

设计一个简化版的推特(Twitter)，可以让用户实现发送推文，关注/取消关注其他用户，能够看见关注人（包括自己）的最近 10 条推文。

实现 Twitter 类：

Twitter() 初始化简易版推特对象
void postTweet(int userId, int tweetId) 根据给定的 tweetId 和 userId 创建一条新推文。每次调用此函数都会使用一个不同的 tweetId 。
List<Integer> getNewsFeed(int userId) 检索当前用户新闻推送中最近 10 条推文的 ID 。新闻推送中的每一项都必须是由用户关注的人或者是用户自己发布的推文。推文必须 按照时间顺序由最近到最远排序 。
void follow(int followerId, int followeeId) ID 为 followerId 的用户开始关注 ID 为 followeeId 的用户。
void unfollow(int followerId, int followeeId) ID 为 followerId 的用户不再关注 ID 为 followeeId 的用户。

示例：

输入
["Twitter", "postTweet", "getNewsFeed", "follow", "postTweet", "getNewsFeed", "unfollow", "getNewsFeed"]
[[], [1, 5], [1], [1, 2], [2, 6], [1], [1, 2], [1]]
输出
[null, null, [5], null, null, [6, 5], null, [5]]

解释
Twitter twitter = new Twitter();
twitter.postTweet(1, 5); // 用户 1 发送了一条新推文 (用户 id = 1, 推文 id = 5)
twitter.getNewsFeed(1);  // 用户 1 的获取推文应当返回一个列表，其中包含一个 id 为 5 的推文
twitter.follow(1, 2);    // 用户 1 关注了用户 2
twitter.postTweet(2, 6); // 用户 2 发送了一个新推文 (推文 id = 6)
twitter.getNewsFeed(1);  // 用户 1 的获取推文应当返回一个列表，其中包含两个推文，id 分别为 -> [6, 5] 。推文 id 6 应当在推文 id 5 之前，因为它是在 5 之后发送的
twitter.unfollow(1, 2);  // 用户 1 取消关注了用户 2
twitter.getNewsFeed(1);  // 用户 1 获取推文应当返回一个列表，其中包含一个 id 为 5 的推文。因为用户 1 已经不再关注用户 2

提示：

1 <= userId, followerId, followeeId <= 500
0 <= tweetId <= 10⁴
所有推特的 ID 都互不相同
postTweet、getNewsFeed、follow 和 unfollow 方法最多调用 3 * 10⁴ 次
用户不能关注自己

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

Doocs 参考题解 · CC BY-SA 4.0

本站根据题意与 Doocs 参考思路整理为 Go，非上游原文。按 CC BY-SA 4.0 共享。

为每条推文分配递增时间戳。每个用户只需保留最近十条：更早的推文不可能进入任何包含该用户的前十条信息流。取本人和关注用户的候选，按时间倒序选十条；关注集合排除重复本人。设关注用户数为 F、用户总数 U，发文和关注平均 O(1)，取信息流 O(F log(F+1))，状态空间 O(U+关注关系数)。

import "sort"

type tweet struct{ id, time int }
type Twitter struct {
	clock  int
	posts  map[int][]tweet
	follow map[int]map[int]bool
}

func Constructor() Twitter { return Twitter{posts: map[int][]tweet{}, follow: map[int]map[int]bool{}} }
func (t *Twitter) PostTweet(userId, tweetId int) {
	t.clock++
	t.posts[userId] = append(t.posts[userId], tweet{tweetId, t.clock})
	if len(t.posts[userId]) > 10 {
		t.posts[userId] = append([]tweet(nil), t.posts[userId][len(t.posts[userId])-10:]...)
	}
}
func (t *Twitter) GetNewsFeed(userId int) []int {
	all := append([]tweet(nil), t.posts[userId]...)
	for id := range t.follow[userId] {
		if id != userId {
			all = append(all, t.posts[id]...)
		}
	}
	sort.Slice(all, func(i, j int) bool { return all[i].time > all[j].time })
	ans := make([]int, min(10, len(all)))
	for i := range ans {
		ans[i] = all[i].id
	}
	return ans
}
func (t *Twitter) Follow(a, b int) {
	if t.follow[a] == nil {
		t.follow[a] = map[int]bool{}
	}
	t.follow[a][b] = true
}
func (t *Twitter) Unfollow(a, b int) { delete(t.follow[a], b) }

力扣原题 · Doocs 题解来源

359. 日志速率限制器 🔒

简单1 种解法

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

题目、示例与约束

请你设计一个日志系统，可以流式接收消息以及它的时间戳。每条 不重复 的消息最多只能每 10 秒打印一次。也就是说，如果在时间戳 t 打印某条消息，那么相同内容的消息直到时间戳变为 t + 10 之前都不会被打印。

所有消息都按时间顺序发送。多条消息可能到达同一时间戳。

实现 Logger 类：

Logger() 初始化 logger 对象
bool shouldPrintMessage(int timestamp, string message) 如果这条消息 message 在给定的时间戳 timestamp 应该被打印出来，则返回 true ，否则请返回 false 。

示例：

输入：
["Logger", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage"]
[[], [1, "foo"], [2, "bar"], [3, "foo"], [8, "bar"], [10, "foo"], [11, "foo"]]
输出：
[null, true, true, false, false, false, true]

解释：
Logger logger = new Logger();
logger.shouldPrintMessage(1, "foo");  // 返回 true ，下一次 "foo" 可以打印的时间戳是 1 + 10 = 11
logger.shouldPrintMessage(2, "bar");  // 返回 true ，下一次 "bar" 可以打印的时间戳是 2 + 10 = 12
logger.shouldPrintMessage(3, "foo");  // 3 < 11 ，返回 false
logger.shouldPrintMessage(8, "bar");  // 8 < 12 ，返回 false
logger.shouldPrintMessage(10, "foo"); // 10 < 11 ，返回 false
logger.shouldPrintMessage(11, "foo"); // 11 >= 11 ，返回 true ，下一次 "foo" 可以打印的时间戳是 11 + 10 = 21

提示：

0 <= timestamp <= 10⁹
每个 timestamp 都将按非递减顺序（时间顺序）传递
1 <= message.length <= 30
最多调用 10⁴ 次 shouldPrintMessage 方法

方法一：哈希表 · Go 实现

思考

同一消息 $10$ 秒内只打印一次，时间戳单调不减。每次扫描历史记录过慢。

哈希表记下该消息下次可打印的时间。当前时间尚未到达则拒绝；否则把下次时间设为 $t + 10$ 并允许打印。

我们用一个哈希表 $ts$ 来存储每个消息的下一个可打印时间戳。在调用 shouldPrintMessage 方法时，我们检查当前时间戳是否大于等于消息的下一个可打印时间戳，若是则更新该消息的下一个可打印时间戳为当前时间戳加 10，并返回 true，否则返回 false。

时间复杂度 $O (1)$ 。空间复杂度 $O (m)$ ，其中 $m$ 是不同消息的数量。

type Logger struct {
	ts map[string]int
}

func Constructor() Logger {
	return Logger{ts: make(map[string]int)}
}

func (this *Logger) ShouldPrintMessage(timestamp int, message string) bool {
	if t, ok := this.ts[message]; ok && timestamp < t {
		return false
	}
	this.ts[message] = timestamp + 10
	return true
}

/**
 * Your Logger object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.ShouldPrintMessage(timestamp,message);
 */

力扣原题 · Doocs 题解来源

362. 敲击计数器 🔒

中等1 种解法

标签：设计、队列、数组、二分查找、数据流

题目、示例与约束

设计一个敲击计数器，使它可以统计在过去 5 分钟内被敲击次数。（即过去 300 秒）

您的系统应该接受一个时间戳参数 timestamp (单位为秒 )，并且您可以假定对系统的调用是按时间顺序进行的(即 timestamp 是单调递增的)。几次撞击可能同时发生。

实现 HitCounter 类:

HitCounter() 初始化命中计数器系统。
void hit(int timestamp) 记录在 timestamp ( 单位为秒 )发生的一次命中。在同一个 timestamp 中可能会出现几个点击。
int getHits(int timestamp) 返回 timestamp 在过去 5 分钟内(即过去 300 秒)的命中次数。

示例 1:

输入：
["HitCounter", "hit", "hit", "hit", "getHits", "hit", "getHits", "getHits"]
[[], [1], [2], [3], [4], [300], [300], [301]]
输出：
[null, null, null, null, 3, null, 4, 3]

解释：
HitCounter counter = new HitCounter();
counter.hit(1);// 在时刻 1 敲击一次。
counter.hit(2);// 在时刻 2 敲击一次。
counter.hit(3);// 在时刻 3 敲击一次。
counter.getHits(4);// 在时刻 4 统计过去 5 分钟内的敲击次数, 函数返回 3 。
counter.hit(300);// 在时刻 300 敲击一次。
counter.getHits(300); // 在时刻 300 统计过去 5 分钟内的敲击次数，函数返回 4 。
counter.getHits(301); // 在时刻 301 统计过去 5 分钟内的敲击次数，函数返回 3 。

提示:

1 <= timestamp <= 2 * 10⁹
所有对系统的调用都是按时间顺序进行的（即 timestamp 是单调递增的）
hit and getHits 最多被调用 300 次

进阶: 如果每秒的敲击次数是一个很大的数字，你的计数器可以应对吗？

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

思考

统计最近 $300$ 秒的点击。时间戳递增。队列弹出过期击亦可，数组加二分更短。

hit 追加时间戳；getHits 二分第一个 $\geq t i m e s t a m p - 299$ 的位置，长度为右段元素个数。

由于 timestamp 是单调递增的，我们可以使用一个数组 ts 来存储所有的 timestamp，然后在 getHits 方法中使用二分查找找到第一个大于等于 timestamp - 300 + 1 的位置，然后返回 ts 的长度减去这个位置即可。

时间复杂度方面，hit 方法的时间复杂度为 $O (1)$ ，getHits 方法的时间复杂度为 $O (\log n)$ 。其中 $n$ 为 ts 的长度。

type HitCounter struct {
	ts []int
}

func Constructor() HitCounter {
	return HitCounter{}
}

func (this *HitCounter) Hit(timestamp int) {
	this.ts = append(this.ts, timestamp)
}

func (this *HitCounter) GetHits(timestamp int) int {
	return len(this.ts) - sort.SearchInts(this.ts, timestamp-300+1)
}

/**
 * Your HitCounter object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Hit(timestamp);
 * param_2 := obj.GetHits(timestamp);
 */

力扣原题 · Doocs 题解来源

379. 电话目录管理系统 🔒

中等1 种解法

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

题目、示例与约束

设计一个电话目录管理系统，一开始有 maxNumbers 个位置能够储存号码。系统应该存储号码，检查某个位置是否为空，并清空给定的位置。

实现 PhoneDirectory 类：

PhoneDirectory(int maxNumbers) 电话目录初始有 maxNumbers 个可用位置。
int get() 提供一个未分配给任何人的号码。如果没有可用号码则返回 -1。
bool check(int number) 如果位置 number 可用返回 true 否则返回 false。
void release(int number) 回收或释放位置 number。

示例 1：

输入：
["PhoneDirectory", "get", "get", "check", "get", "check", "release", "check"]
[[3], [], [], [2], [], [2], [2], [2]]
输出：
[null, 0, 1, true, 2, false, null, true]

解释：
PhoneDirectory phoneDirectory = new PhoneDirectory(3);
phoneDirectory.get();      // 它可以返回任意可用的数字。这里我们假设它返回 0。
phoneDirectory.get();      // 假设它返回 1。
phoneDirectory.check(2);   // 数字 2 可用，所以返回 true。
phoneDirectory.get();      // 返回剩下的唯一一个数字 2。
phoneDirectory.check(2);   // 数字 2 不再可用，所以返回 false。
phoneDirectory.release(2); // 将数字 2 释放回号码池。
phoneDirectory.check(2);   // 数字 2 重新可用，返回 true。

提示：

1 <= maxNumbers <= 10⁴
0 <= number < maxNumbers
get，check 和 release 最多被调用 2 * 10⁴ 次。

方法一：哈希表 · Go 实现

思考

号码池：取号、查询空闲、归还，均须均摊常数。数组扫描找空号过慢。

哈希集合存未分配号码。get 弹出任一元素，check 查是否仍在集合，release 加回。空集合返回 $- 1$ 。

我们可以使用一个哈希集合 available 来存储未被分配的电话号码，初始时，哈希表中存储的是 [0, 1, 2, ..., maxNumbers - 1]。

调用 get 方法时，我们从 available 中取出一个未被分配的电话号码，如果 available 为空，则返回 -1。时间复杂度 $O (1)$ 。

调用 check 方法时，我们只需要判断 number 是否在 available 中即可。时间复杂度 $O (1)$ 。

调用 release 方法时，我们将 number 添加到 available 中。时间复杂度 $O (1)$ 。

空间复杂度 $O (n)$ ，其中 $n$ 是 maxNumbers 的值。

type PhoneDirectory struct {
	available map[int]bool
}

func Constructor(maxNumbers int) PhoneDirectory {
	available := make(map[int]bool)
	for i := 0; i < maxNumbers; i++ {
		available[i] = true
	}
	return PhoneDirectory{available}
}

func (this *PhoneDirectory) Get() int {
	for k := range this.available {
		delete(this.available, k)
		return k
	}
	return -1
}

func (this *PhoneDirectory) Check(number int) bool {
	_, ok := this.available[number]
	return ok
}

func (this *PhoneDirectory) Release(number int) {
	this.available[number] = true
}

/**
 * Your PhoneDirectory object will be instantiated and called as such:
 * obj := Constructor(maxNumbers);
 * param_1 := obj.Get();
 * param_2 := obj.Check(number);
 * obj.Release(number);
 */

力扣原题 · Doocs 题解来源

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

中等1 种解法

标签：设计、数组、哈希表、数学、随机化

题目、示例与约束

实现RandomizedSet 类：

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

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

示例：

输入
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
输出
[null, true, false, true, 2, true, false, 2]

解释
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomizedSet.remove(2); // 返回 false ，表示集合中不存在 2 。
randomizedSet.insert(2); // 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
randomizedSet.getRandom(); // getRandom 应随机返回 1 或 2 。
randomizedSet.remove(1); // 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
randomizedSet.insert(2); // 2 已在集合中，所以返回 false 。
randomizedSet.getRandom(); // 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。

提示：

-2³¹ <= val <= 2³¹ - 1
最多调用 insert、remove 和 getRandom 函数 2 * 10⁵ 次
在调用 getRandom 方法时，数据结构中 至少存在一个 元素。

方法一：哈希表 + 动态列表 · Go 实现

思考

集合支持插入、删除与等概率随机，均须 $O (1)$ 。仅哈希表无法按下标随机；仅动态数组删除为 $O (n)$ 。

数组存元素，哈希表存下标。插入追加到末尾；删除时与末尾交换再弹出，并更新被换元素的下标。随机即在数组上 choice。

我们定义一个动态列表 $q$ ，用于存储集合中的元素，定义一个哈希表 $d$ ，用于存储每个元素在 $q$ 中的下标。

插入元素时，如果元素已经存在于哈希表 $d$ 中，直接返回 false；否则，我们将元素插入到动态列表 $q$ 的末尾，同时将元素和其在 $q$ 中的下标插入到哈希表 $d$ 中，最后返回 true。

删除元素时，如果元素不存在于哈希表 $d$ 中，直接返回 false；否则，我们从哈希表中获取元素在列表 $q$ 中的下标 $i$ ，然后将列表 $q$ 的最后一个元素 $q [- 1]$ 与 $q [i]$ 交换，然后将哈希表中 $q [- 1]$ 的下标更新为 $i$ ，最后将 $q$ 的最后一个元素删除，同时将元素从哈希表中删除，最后返回 true。

获取随机元素时，我们从动态列表 $q$ 中随机选择一个元素返回即可。

时间复杂度 $O (1)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为集合中元素的个数。

type RandomizedSet struct {
	d map[int]int
	q []int
}

func Constructor() RandomizedSet {
	return RandomizedSet{map[int]int{}, []int{}}
}

func (this *RandomizedSet) Insert(val int) bool {
	if _, ok := this.d[val]; ok {
		return false
	}
	this.d[val] = len(this.q)
	this.q = append(this.q, val)
	return true
}

func (this *RandomizedSet) Remove(val int) bool {
	if _, ok := this.d[val]; !ok {
		return false
	}
	i := this.d[val]
	this.d[this.q[len(this.q)-1]] = i
	this.q[i] = this.q[len(this.q)-1]
	this.q = this.q[:len(this.q)-1]
	delete(this.d, val)
	return true
}

func (this *RandomizedSet) GetRandom() int {
	return this.q[rand.Intn(len(this.q))]
}

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Insert(val);
 * param_2 := obj.Remove(val);
 * param_3 := obj.GetRandom();
 */

力扣原题 · Doocs 题解来源

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

146. LRU 缓存 ​

155. 最小栈 ​

170. 两数之和 III - 数据结构设计 🔒 ​

173. 二叉搜索树迭代器 ​

208. 实现 Trie (前缀树) ​

211. 添加与搜索单词 - 数据结构设计 ​

225. 用队列实现栈 ​

232. 用栈实现队列 ​

244. 最短单词距离 II 🔒 ​

251. 展开二维向量 🔒 ​

271. 字符串的编码与解码 🔒 ​

281. 锯齿迭代器 🔒 ​

284. 窥视迭代器 ​

288. 单词的唯一缩写 🔒 ​

295. 数据流的中位数 ​

297. 二叉树的序列化与反序列化 ​

303. 区域和检索 - 数组不可变 ​

304. 二维区域和检索 - 矩阵不可变 ​

307. 区域和检索 - 数组可修改 ​

308. 二维区域和检索 - 矩阵可修改 🔒 ​

341. 扁平化嵌套列表迭代器 ​

346. 数据流中的移动平均值 🔒 ​

348. 设计井字棋 🔒 ​

352. 将数据流变为多个不相交区间 ​

353. 贪吃蛇 🔒 ​

355. 设计推特 ​

359. 日志速率限制器 🔒 ​

362. 敲击计数器 🔒 ​

379. 电话目录管理系统 🔒 ​

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

继续阅读

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

146. LRU 缓存

155. 最小栈

170. 两数之和 III - 数据结构设计 🔒

173. 二叉搜索树迭代器

208. 实现 Trie (前缀树)

211. 添加与搜索单词 - 数据结构设计

225. 用队列实现栈

232. 用栈实现队列

244. 最短单词距离 II 🔒

251. 展开二维向量 🔒

271. 字符串的编码与解码 🔒

281. 锯齿迭代器 🔒

284. 窥视迭代器

288. 单词的唯一缩写 🔒

295. 数据流的中位数

297. 二叉树的序列化与反序列化

303. 区域和检索 - 数组不可变

304. 二维区域和检索 - 矩阵不可变

307. 区域和检索 - 数组可修改

308. 二维区域和检索 - 矩阵可修改 🔒

341. 扁平化嵌套列表迭代器

346. 数据流中的移动平均值 🔒

348. 设计井字棋 🔒

352. 将数据流变为多个不相交区间

353. 贪吃蛇 🔒

355. 设计推特

359. 日志速率限制器 🔒

362. 敲击计数器 🔒

379. 电话目录管理系统 🔒

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