LeetCode Go · 哈希表（7）

来源与许可

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

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

3146. 两个字符串的排列差

简单1 种解法

标签：哈希表、字符串

题目、示例与约束

给你两个字符串 s 和 t，每个字符串中的字符都不重复，且 t 是 s 的一个排列。

排列差 定义为 s 和 t 中每个字符在两个字符串中位置的绝对差值之和。

返回 s 和 t 之间的 排列差 。

示例 1：

输入：s = "abc", t = "bac"

输出：2

解释：

对于 s = "abc" 和 t = "bac"，排列差是：

"a" 在 s 中的位置与在 t 中的位置之差的绝对值。
"b" 在 s 中的位置与在 t 中的位置之差的绝对值。
"c" 在 s 中的位置与在 t 中的位置之差的绝对值。

即，s 和 t 的排列差等于 |0 - 1| + |1 - 0| + |2 - 2| = 2。

示例 2：

输入：s = "abcde", t = "edbac"

输出：12

解释： s 和 t 的排列差等于 |0 - 3| + |1 - 2| + |2 - 4| + |3 - 1| + |4 - 0| = 12。

提示：

1 <= s.length <= 26
每个字符在 s 中最多出现一次。
t 是 s 的一个排列。
s 仅由小写英文字母组成。

方法一：哈希表或数组 · Go 实现

思考

差值为同一字母在 $s$ 与 $t$ 中下标差的绝对值之和。对每个字母在另一串里线性查找是平方的。

$s$ 是排列， $t$ 亦然，字母到下标是双射，一次建表即可。

用哈希（或长 $26$ 的数组）记下 $s$ 中位置，再扫 $t$ 累加绝对差。

我们可以使用哈希表或者一个长度为 $26$ 的数组 $d$ 来存储字符串 $s$ 中每个字符的位置。

然后遍历字符串 $t$ ，计算每个字符在字符串 $t$ 中的位置与在字符串 $s$ 中的位置之差的绝对值之和即可。

时间复杂度 $O (n)$ ，其中 $n$ 为字符串 $s$ 的长度。空间复杂度 $O (| Σ |)$ ，其中 $Σ$ 为字符集，这里是小写英文字母，所以 $| Σ | \leq 26$ 。

func findPermutationDifference(s string, t string) (ans int) {
	d := [26]int{}
	for i, c := range s {
		d[c-'a'] = i
	}
	for i, c := range t {
		ans += max(d[c-'a']-i, i-d[c-'a'])
	}
	return
}

力扣原题 · Doocs 题解来源

3159. 查询数组中元素的出现位置

中等1 种解法

标签：数组、哈希表

题目、示例与约束

给你一个整数数组 nums ，一个整数数组 queries 和一个整数 x 。

对于每个查询 queries[i] ，你需要找到 nums 中第 queries[i] 个 x 的位置，并返回它的下标。如果数组中 x 的出现次数少于 queries[i] ，该查询的答案为 -1 。

请你返回一个整数数组 answer ，包含所有查询的答案。

示例 1：

输入：nums = [1,3,1,7], queries = [1,3,2,4], x = 1

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

解释：

第 1 个查询，第一个 1 出现在下标 0 处。
第 2 个查询，nums 中只有两个 1 ，所以答案为 -1 。
第 3 个查询，第二个 1 出现在下标 2 处。
第 4 个查询，nums 中只有两个 1 ，所以答案为 -1 。

示例 2：

输入：nums = [1,2,3], queries = [10], x = 5

输出：[-1]

解释：

第 1 个查询，nums 中没有 5 ，所以答案为 -1 。

提示：

1 <= nums.length, queries.length <= 10⁵
1 <= queries[i] <= 10⁵
1 <= nums[i], x <= 10⁴

方法一：模拟 · Go 实现

思考

询问第 $i$ 次出现的 $x$ 的下标。每次从左扫描到第 $i$ 次是 $O (n m)$ 。

所有出现位置可预处理成数组 $i d s$ ，询问变成一次下标访问。

先收集 $v = x$ 的下标，再对每个 $i$ 返回 $i d s [i - 1]$ 或越界时的 $- 1$ 。

根据题目描述，我们可以先遍历一遍数组 $nums$ ，找出所有值为 $x$ 的元素的下标，记录在数组 $ids$ 中。

接着遍历数组 $queries$ ，对于每个查询 $i$ ，如果 $i - 1$ 小于 $ids$ 的长度，那么答案就是 $ids [i - 1]$ ，否则答案就是 $- 1$ 。

时间复杂度 $O (n + m)$ ，空间复杂度 $O (n + m)$ 。其中 $n$ 和 $m$ 分别是数组 $nums$ 和数组 $queries$ 的长度。

func occurrencesOfElement(nums []int, queries []int, x int) (ans []int) {
	ids := []int{}
	for i, v := range nums {
		if v == x {
			ids = append(ids, i)
		}
	}
	for _, i := range queries {
		if i-1 < len(ids) {
			ans = append(ans, ids[i-1])
		} else {
			ans = append(ans, -1)
		}
	}
	return
}

力扣原题 · Doocs 题解来源

3160. 所有球里面不同颜色的数目

中等1 种解法

标签：数组、哈希表、模拟

题目、示例与约束

给你一个整数 limit 和一个大小为 n x 2 的二维数组 queries 。

总共有 limit + 1 个球，每个球的编号为 [0, limit] 中一个 互不相同 的数字。一开始，所有球都没有颜色。queries 中每次操作的格式为 [x, y] ，你需要将球 x 染上颜色 y 。每次操作之后，你需要求出所有球颜色的数目。

请你返回一个长度为 n 的数组 result ，其中 result[i] 是第 i 次操作以后颜色的数目。

注意，没有染色的球不算作一种颜色。

示例 1：

输入：limit = 4, queries = [[1,4],[2,5],[1,3],[3,4]]

输出：[1,2,2,3]

解释：

操作 0 后，球 1 颜色为 4 。
操作 1 后，球 1 颜色为 4 ，球 2 颜色为 5 。
操作 2 后，球 1 颜色为 3 ，球 2 颜色为 5 。
操作 3 后，球 1 颜色为 3 ，球 2 颜色为 5 ，球 3 颜色为 4 。

示例 2：

输入：limit = 4, queries = [[0,1],[1,2],[2,2],[3,4],[4,5]]

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

解释：

操作 0 后，球 0 颜色为 1 。
操作 1 后，球 0 颜色为 1 ，球 1 颜色为 2 。
操作 2 后，球 0 颜色为 1 ，球 1 和 2 颜色为 2 。
操作 3 后，球 0 颜色为 1 ，球 1 和 2 颜色为 2 ，球 3 颜色为 4 。
操作 4 后，球 0 颜色为 1 ，球 1 和 2 颜色为 2 ，球 3 颜色为 4 ，球 4 颜色为 5 。

提示：

1 <= limit <= 10⁹
1 <= n == queries.length <= 10⁵
queries[i].length == 2
0 <= queries[i][0] <= limit
1 <= queries[i][1] <= 10⁹

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

思考

每次给一个球涂色，查询当前不同颜色数。 $l i m i t$ 可达 $10^{9}$ ，不能开数组；若每次重扫全部球则过慢。

真正变化的只有被涂的那个球：新颜色计数加一，旧颜色计数减一并在归零时删除。不同颜色数即计数表大小。

用 $g$ 记球到颜色， $c n t$ 记颜色到个数。按询问更新后把 $l e n (c n t)$ 追加到答案。

我们使用一个哈希表 $g$ 记录每个球的颜色，使用一个哈希表 $cnt$ 记录每种颜色的球的个数。

接下来，遍历数组 $queries$ ，对于每个查询 $(x, y)$ ，我们将颜色 $y$ 的球的个数加 $1$ ，然后判断球 $x$ 是否已经染色，如果已经染色，我们将球 $x$ 的颜色的球的个数减 $1$ ，如果减到 $0$ ，我们将其从哈希表 $cnt$ 中移除。接下来，我们将球 $x$ 的颜色更新为 $y$ ，并将当前哈希表 $cnt$ 的大小加入答案数组。

遍历结束后，返回答案数组即可。

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

func queryResults(limit int, queries [][]int) (ans []int) {
	g := map[int]int{}
	cnt := map[int]int{}
	for _, q := range queries {
		x, y := q[0], q[1]
		cnt[y]++
		if v, ok := g[x]; ok {
			cnt[v]--
			if cnt[v] == 0 {
				delete(cnt, v)
			}
		}
		g[x] = y
		ans = append(ans, len(cnt))
	}
	return
}

力扣原题 · Doocs 题解来源

3162. 优质数对的总数 I

简单2 种解法

标签：数组、哈希表

题目、示例与约束

给你两个整数数组 nums1 和 nums2，长度分别为 n 和 m。同时给你一个正整数 k。

如果 nums1[i] 可以除尽 nums2[j] * k，则称数对 (i, j) 为 优质数对（0 <= i <= n - 1, 0 <= j <= m - 1）。

返回 优质数对 的总数。

示例 1：

输入：nums1 = [1,3,4], nums2 = [1,3,4], k = 1

输出：5

解释：

5个优质数对分别是 (0, 0), (1, 0), (1, 1), (2, 0), 和 (2, 2)。

示例 2：

输入：nums1 = [1,2,4,12], nums2 = [2,4], k = 3

输出：2

解释：

2个优质数对分别是 (3, 0) 和 (3, 1)。

提示：

1 <= n, m <= 50
1 <= nums1[i], nums2[j] <= 50
1 <= k <= 50

方法一：暴力枚举 · Go 实现

思考

数对满足 $n u m s 1 [i]$ 能被 $n u m s 2 [j] \cdot k$ 整除。两数组长度至多 $50$ ，双重枚举即可。

不必预处理倍数。对每对 $(x, y)$ 判断 $x mod (y \cdot k) = 0$ 。

一层生成器求和即答案，时间为 $O (m n)$ 。

我们直接枚举所有的数位 $(x, y)$ ，判断是否满足 $x mod (y \times k) = 0$ ，如果满足则答案加一。

枚举结束后，返回答案即可。

时间复杂度 $O (m \times n)$ ，其中 $m$ 和 $n$ 分别是数组 $nums1$ 和 $nums2$ 的长度。空间复杂度 $O (1)$ 。

func numberOfPairs(nums1 []int, nums2 []int, k int) (ans int) {
	for _, x := range nums1 {
		for _, y := range nums2 {
			if x%(y*k) == 0 {
				ans++
			}
		}
	}
	return
}

方法二：哈希表 + 枚举倍数 · Go 实现

思考

方法一依赖 $m n$ 很小。同一题的 II 中长度更大，需要按倍数聚合。

把 $n u m s 1$ 中能被 $k$ 整除的商计数，再对 $n u m s 2$ 的每种 $x$ 枚举其倍数 $y$ ，累加 $c n t 1 [y]$ 。

哈希去重后内层按步长 $x$ 扫描到 $m x$ ，再乘 $x$ 的出现次数。为 II 的线性倍数枚举做铺垫。

我们用一个哈希表 $cnt1$ 记录数组 $nums1$ 中每个数除以 $k$ 的商的出现次数，用一个哈希表 $cnt2$ 记录数组 $nums2$ 中每个数的出现次数。

接下来，我们枚举数组 $nums2$ 中的每个数 $x$ ，对于每个数 $x$ ，我们枚举 $x$ 的倍数 $y$ ，其中 $y$ 的范围是 $[x, mx]$ ，其中 $mx$ 是 $cnt1$ 中的最大键值，然后我们统计 $cnt1 [y]$ 的和，记为 $s$ ，最后我们将 $s \times v$ 累加到答案中，其中 $v$ 是 $cnt2 [x]$ 。

时间复杂度 $O (n + m + (M / k) \times \log m)$ ，空间复杂度 $O (n + m)$ ，其中 $n$ 和 $m$ 分别是数组 $nums1$ 和 $nums2$ 的长度，而 $M$ 是数组 $nums1$ 中的最大值。

func numberOfPairs(nums1 []int, nums2 []int, k int) (ans int) {
	cnt1 := map[int]int{}
	for _, x := range nums1 {
		if x%k == 0 {
			cnt1[x/k]++
		}
	}
	if len(cnt1) == 0 {
		return 0
	}
	cnt2 := map[int]int{}
	for _, x := range nums2 {
		cnt2[x]++
	}
	mx := 0
	for x := range cnt1 {
		mx = max(mx, x)
	}
	for x, v := range cnt2 {
		s := 0
		for y := x; y <= mx; y += x {
			s += cnt1[y]
		}
		ans += s * v
	}
	return
}

力扣原题 · Doocs 题解来源

3164. 优质数对的总数 II

中等1 种解法

标签：数组、哈希表

题目、示例与约束

给你两个整数数组 nums1 和 nums2，长度分别为 n 和 m。同时给你一个正整数 k。

如果 nums1[i] 可以被 nums2[j] * k 整除，则称数对 (i, j) 为 优质数对（0 <= i <= n - 1, 0 <= j <= m - 1）。

返回 优质数对 的总数。

示例 1：

输入：nums1 = [1,3,4], nums2 = [1,3,4], k = 1

输出：5

解释：

5个优质数对分别是 (0, 0), (1, 0), (1, 1), (2, 0), 和 (2, 2)。

示例 2：

输入：nums1 = [1,2,4,12], nums2 = [2,4], k = 3

输出：2

解释：

2个优质数对分别是 (3, 0) 和 (3, 1)。

提示：

1 <= n, m <= 10⁵
1 <= nums1[i], nums2[j] <= 10⁶
1 <= k <= 10³

方法一：哈希表 + 枚举倍数 · Go 实现

思考

条件与 I 相同但长度达到 $10^{5}$ ，双重循环不可用。

$x$ 能配 $y$ 当且仅当 $(x / k)$ 是 $y$ 的倍数（且 $k$ 整除 $x$ ）。按商计数后，枚举 $y$ 的倍数即可。

先把 $n u m s 1$ 中 $k$ 的倍数收成 $c n t 1$ ，再对 $c n t 2$ 的每个 $x$ 以步长 $x$ 扫到 $m x$ ，累加 $c n t 1 [y] \cdot v$ 。空 $c n t 1$ 直接返回 $0$ 。

我们用一个哈希表 $cnt1$ 记录数组 $nums1$ 中每个数除以 $k$ 的商的出现次数，用一个哈希表 $cnt2$ 记录数组 $nums2$ 中每个数的出现次数。

时间复杂度 $O (n + m + (M / k) \times \log m)$ ，空间复杂度 $O (n + m)$ ，其中 $n$ 和 $m$ 分别是数组 $nums1$ 和 $nums2$ 的长度，而 $M$ 是数组 $nums1$ 中的最大值。

func numberOfPairs(nums1 []int, nums2 []int, k int) (ans int64) {
	cnt1 := map[int]int{}
	for _, x := range nums1 {
		if x%k == 0 {
			cnt1[x/k]++
		}
	}
	if len(cnt1) == 0 {
		return 0
	}
	cnt2 := map[int]int{}
	for _, x := range nums2 {
		cnt2[x]++
	}
	mx := 0
	for x := range cnt1 {
		mx = max(mx, x)
	}
	for x, v := range cnt2 {
		s := 0
		for y := x; y <= mx; y += x {
			s += cnt1[y]
		}
		ans += int64(s) * int64(v)
	}
	return
}

力扣原题 · Doocs 题解来源

3167. 字符串的更好压缩 🔒

中等1 种解法

标签：哈希表、字符串、计数、排序

题目、示例与约束

给定一个字符串 compressed 表示一个字符串的压缩版本。格式是一个字符后面加上其出现频率。例如 "a3b1a1c2" 是字符串 "aaabacc" 的一个压缩版本。

我们在以下条件下寻求 更好的压缩：

每个字符在压缩版本中只应出现一次。
字符应按 字母顺序 排列。

返回 compressed 的更好压缩版本。

注意：在更好的压缩版本中，字母的顺序可能会改变，这是可以接受的。

示例 1：

输入：compressed = "a3c9b2c1"

输出："a3b2c10"

解释：

字符 "a" 和 "b" 在输入中只出现了一次，但 "c" 出现了两次，第一次长度为 9，另一次是长度为 1。

因此，在结果字符串中，它应当长度为 10。

示例 2：

输入：compressed = "c2b3a1"

输出："a1b3c2"

示例 3：

输入：compressed = "a2b4c1"

输出："a2b4c1"

提示：

1 <= compressed.length <= 6 * 10⁴
compressed 仅由小写英文字母和数字组成。
compressed 是有效的压缩，即，每个字符后面都有其出现频率。
出现频率在 [1, 10⁴] 之间并且没有前导 0。

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

思考

压缩串由「字符+十进制次数」拼接，需按字母序合并同字符次数。按段切分后若用有序列表插入，实现繁琐。

字符只有 $26$ 种，先累加次数再排序输出即可。双指针读完一段数字。

下标 $i$ 指向字符， $j$ 吞掉后续数字并加入 $c n t$ ，最后按键排序拼接 $k + v$ 。

我们可以使用哈希表来统计每个字符的频率，然后使用双指针来遍历 compressed 字符串，将每个字符的频率累加到哈希表中，最后按照字母顺序将字符和频率拼接成字符串。

时间复杂度 $O (n + | Σ | \log | Σ |)$ ，空间复杂度 $O (| Σ |)$ ，其中 $n$ 是字符串 compressed 的长度，而 $| Σ |$ 是字符集的大小，这里字符集是小写字母，所以 $| Σ | = 26$ 。

func betterCompression(compressed string) string {
	cnt := map[byte]int{}
	n := len(compressed)
	for i := 0; i < n; {
		c := compressed[i]
		j := i + 1
		x := 0
		for j < n && compressed[j] >= '0' && compressed[j] <= '9' {
			x = x*10 + int(compressed[j]-'0')
			j++
		}
		cnt[c] += x
		i = j
	}
	ans := strings.Builder{}
	for c := byte('a'); c <= byte('z'); c++ {
		if cnt[c] > 0 {
			ans.WriteByte(c)
			ans.WriteString(strconv.Itoa(cnt[c]))
		}
	}
	return ans.String()
}

力扣原题 · Doocs 题解来源

3184. 构成整天的下标对数目 I

简单1 种解法

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

题目、示例与约束

给你一个整数数组 hours，表示以小时为单位的时间，返回一个整数，表示满足 i < j 且 hours[i] + hours[j] 构成整天的下标对 i, j 的数目。

整天定义为时间持续时间是 24 小时的 整数倍 。

例如，1 天是 24 小时，2 天是 48 小时，3 天是 72 小时，以此类推。

示例 1：

输入： hours = [12,12,30,24,24]

输出： 2

解释：

构成整天的下标对分别是 (0, 1) 和 (3, 4)。

示例 2：

输入： hours = [72,48,24,3]

输出： 3

解释：

构成整天的下标对分别是 (0, 1)、(0, 2) 和 (1, 2)。

提示：

1 <= hours.length <= 100
1 <= hours[i] <= 10⁹

方法一：计数 · Go 实现

思考

两时间之和为 $24$ 的倍数。双重枚举在 I 的长度下可行，但模 $24$ 后只有 $24$ 个桶。

扫到 $x$ 时，与它配对的余数是 $(24 - x mod 24) mod 24$ ，查已出现次数即可。

先累加再把 $x mod 24$ 入表，保证下标 $i < j$ 。空间为常数 $24$ 。

我们可以用一个哈希表或者一个长度为 $24$ 的数组 $cnt$ 来记录每个小时数模 $24$ 的出现次数。

遍历数组 $hours$ ，对于每个小时数 $x$ ，我们可以得出与 $x$ 相加为 $24$ 的倍数，且模 $24$ 之后的数为 $(24 - x mod 24) mod 24$ 。累加这个数在哈希表或者数组中的出现次数即可。然后我们将 $x$ 的模 $24$ 的出现次数加一。

遍历完数组 $hours$ 后，我们就可以得到满足题意的下标对数目。

时间复杂度 $O (n)$ ，其中 $n$ 为数组 $hours$ 的长度。空间复杂度 $O (C)$ ，其中 $C = 24$ 。

func countCompleteDayPairs(hours []int) (ans int) {
	cnt := [24]int{}
	for _, x := range hours {
		ans += cnt[(24-x%24)%24]
		cnt[x%24]++
	}
	return
}

力扣原题 · Doocs 题解来源

3185. 构成整天的下标对数目 II

中等1 种解法

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

题目、示例与约束

给你一个整数数组 hours，表示以小时为单位的时间，返回一个整数，表示满足 i < j 且 hours[i] + hours[j] 构成整天的下标对 i, j 的数目。

整天定义为时间持续时间是 24 小时的 整数倍 。

例如，1 天是 24 小时，2 天是 48 小时，3 天是 72 小时，以此类推。

示例 1：

输入： hours = [12,12,30,24,24]

输出： 2

解释：

构成整天的下标对分别是 (0, 1) 和 (3, 4)。

示例 2：

输入： hours = [72,48,24,3]

输出： 3

解释：

构成整天的下标对分别是 (0, 1)、(0, 2) 和 (1, 2)。

提示：

1 <= hours.length <= 5 * 10⁵
1 <= hours[i] <= 10⁹

方法一：计数 · Go 实现

思考

条件与 I 相同而 $n$ 达到 $10^{5}$ ，双重循环不可用。已出现余数的计数仍然足够。

配对余数公式不变，哈希或长 $24$ 的数组均可。

从左扫描：答案加上 $c n t [(24 - x mod 24) mod 24]$ ，再更新 $c n t [x mod 24]$ 。

我们可以用一个哈希表或者一个长度为 $24$ 的数组 $cnt$ 来记录每个小时数模 $24$ 的出现次数。

遍历完数组 $hours$ 后，我们就可以得到满足题意的下标对数目。

时间复杂度 $O (n)$ ，其中 $n$ 为数组 $hours$ 的长度。空间复杂度 $O (C)$ ，其中 $C = 24$ 。

func countCompleteDayPairs(hours []int) (ans int64) {
	cnt := [24]int{}
	for _, x := range hours {
		ans += int64(cnt[(24-x%24)%24])
		cnt[x%24]++
	}
	return
}

力扣原题 · Doocs 题解来源

3223. 操作后字符串的最短长度

中等1 种解法

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

题目、示例与约束

给你一个字符串 s 。

你需要对 s 执行以下操作任意次：

选择一个下标 i ，满足 s[i] 左边和右边都至少有一个字符与它相同。
删除 i 左边离它最近的 s[i] 字符。
删除 i 右边离它最近的 s[i] 字符。

请你返回执行完所有操作后， s 的最短长度。

示例 1：

输入：s = "abaacbcbb"

输出：5

解释：
我们执行以下操作：

选择下标 2 ，然后删除下标 0 和 3 处的字符，得到 s = "bacbcbb" 。
选择下标 3 ，然后删除下标 0 和 5 处的字符，得到 s = "acbcb" 。

示例 2：

输入：s = "aa"

输出：2

解释：
无法对字符串进行任何操作，所以返回初始字符串的长度。

提示：

1 <= s.length <= 2 * 10⁵
s 只包含小写英文字母。

方法一：计数 · Go 实现

思考

操作是删去某字符两侧各一个相同字符。 $n \leq 2 \times 10^{5}$ ，按操作逐步改串会反复移动。同一字符的删除互不依赖其他字母，最终剩余只由该字母频数决定。

频数为奇数时两侧对称删完后剩 $1$ ，偶数为 $2$ 。对 $26$ 个计数求和即最短长度，不必模拟删除顺序。

我们可以统计字符串中每个字符出现的次数，然后遍历计数数组，如果字符出现的次数为奇数，则最后该字符剩余 $1$ 个，如果字符出现的次数为偶数，则最后该字符剩余 $2$ 个。我们可以将所有字符的剩余个数相加，即为最终字符串的长度。

时间复杂度 $O (n)$ ，其中 $n$ 为字符串 $s$ 的长度。空间复杂度 $O (| Σ |)$ ，其中 $| Σ |$ 为字符集的大小，本题中 $| Σ | = 26$ 。

func minimumLength(s string) (ans int) {
	cnt := [26]int{}
	for _, c := range s {
		cnt[c-'a']++
	}
	for _, x := range cnt {
		if x > 0 {
			if x&1 == 1 {
				ans += 1
			} else {
				ans += 2
			}
		}
	}
	return
}

力扣原题 · Doocs 题解来源

3237. Alt 和 Tab 模拟 🔒

中等1 种解法

标签：数组、哈希表、模拟

题目、示例与约束

有 n 个编号从 1 到 n 的打开的窗口，我们想要模拟使用 alt + tab 键在窗口之间导航。

给定数组 windows 包含窗口的初始顺序（第一个元素在最前面，最后一个元素在最后面）。

同时给定数组 queries 表示每一次查询中，编号为 queries[i] 的窗口被切换到最前面。

返回 windows 数组的最后状态。

示例 1：

输入：windows = [1,2,3], queries = [3,3,2]

输出：[2,3,1]

解释：

以下是每次查询后的 windows 数组：

初始顺序：[1,2,3]
第一次查询后：[3,1,2]
第二次查询后：[3,1,2]
最后一次查询后：[2,3,1]

示例 2:

输入：windows = [1,4,2,3], queries = [4,1,3]

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

解释：

以下是每次查询后的 windows 数组：

初始顺序：[1,4,2,3]
第一次查询后：[4,1,2,3]
第二次查询后：[1,4,2,3]
最后一次查询后：[3,1,4,2]

提示：

1 <= n == windows.length <= 10⁵
windows 是 [1, n] 的一个排列。
1 <= queries.length <= 10⁵
1 <= queries[i] <= n

方法一：哈希表 + 逆序遍历 · Go 实现

思考

每次查询把窗口提到最前。 $n, q \leq 10^{5}$ ，若每次把元素移到数组头部则总时间平方。最终顺序由「最后一次被提到的先后」决定，越后的查询越靠前。

逆序扫查询，用集合去重后依次写入答案，再把从未出现的原窗口按原序接在后面。每个窗口至多入队一次。

根据题目描述，越是后面的查询，越是出现在最前面的位置。因此，我们可以逆序遍历 $queries$ 数组，用一个哈希表 $s$ 记录已经出现过的窗口。对于每一个查询，如果当前窗口不在哈希表中，我们将其加入答案数组，并将其加入哈希表中。最后，我们再次遍历 $windows$ 数组，将不在哈希表中的窗口加入答案数组。

时间复杂度 $O (n + m)$ ，空间复杂度 $O (m)$ 。其中 $n$ 和 $m$ 分别为 $windows$ 和 $queries$ 数组的长度。

func simulationResult(windows []int, queries []int) (ans []int) {
	n := len(windows)
	s := make([]bool, n+1)
	for i := len(queries) - 1; i >= 0; i-- {
		q := queries[i]
		if !s[q] {
			s[q] = true
			ans = append(ans, q)
		}
	}
	for _, w := range windows {
		if !s[w] {
			ans = append(ans, w)
		}
	}
	return
}

力扣原题 · Doocs 题解来源

3238. 求出胜利玩家的数目

简单1 种解法

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

题目、示例与约束

给你一个整数 n ，表示在一个游戏中的玩家数目。同时给你一个二维整数数组 pick ，其中 pick[i] = [x_i, y_i] 表示玩家 x_i 获得了一个颜色为 y_i 的球。

如果玩家 i 获得的球中任何一种颜色球的数目 严格大于 i 个，那么我们说玩家 i 是胜利玩家。换句话说：

如果玩家 0 获得了任何的球，那么玩家 0 是胜利玩家。
如果玩家 1 获得了至少 2 个相同颜色的球，那么玩家 1 是胜利玩家。
...
如果玩家 i 获得了至少 i + 1 个相同颜色的球，那么玩家 i 是胜利玩家。

请你返回游戏中 胜利玩家 的数目。

注意，可能有多个玩家是胜利玩家。

示例 1：

输入：n = 4, pick = [[0,0],[1,0],[1,0],[2,1],[2,1],[2,0]]

输出：2

解释：

玩家 0 和玩家 1 是胜利玩家，玩家 2 和玩家 3 不是胜利玩家。

示例 2：

输入：n = 5, pick = [[1,1],[1,2],[1,3],[1,4]]

输出：0

解释：

没有胜利玩家。

示例 3：

输入：n = 5, pick = [[1,1],[2,4],[2,4],[2,4]]

输出：1

解释：

玩家 2 是胜利玩家，因为玩家 2 获得了 3 个颜色为 4 的球。

提示：

2 <= n <= 10
1 <= pick.length <= 100
pick[i].length == 2
0 <= x_i <= n - 1
0 <= y_i <= 10

方法一：计数 · Go 实现

思考

玩家 $x$ 若某颜色球数大于 $x$ 则获胜。 $n \leq 10$ 、 $pick$ 至多 $100$ ，直接计数即可。

二维表记录每人每色的个数，达到阈值就把该玩家放入集合，避免同一人重复计数。最后集合大小即获胜人数。

我们可以用一个二维数组 $cnt$ 记录每个玩家获得的每种颜色球的数量，用一个哈希表 $s$ 记录胜利玩家的编号。

遍历 $pick$ 数组，对于每个元素 $[x, y]$ ，我们将 $cnt [x] [y]$ 加一，如果 $cnt [x] [y]$ 大于 $x$ ，则将 $x$ 加入哈希表 $s$ 。

最后返回哈希表 $s$ 的大小即可。

时间复杂度 $O (m + n \times M)$ ，空间复杂度 $O (n \times M)$ 。其中 $m$ 为 $pick$ 数组的长度，而 $n$ 和 $M$ 分别为玩家数目和颜色数目。

func winningPlayerCount(n int, pick [][]int) int {
	cnt := make([][11]int, n)
	s := map[int]struct{}{}
	for _, p := range pick {
		x, y := p[0], p[1]
		cnt[x][y]++
		if cnt[x][y] > x {
			s[x] = struct{}{}
		}
	}
	return len(s)
}

力扣原题 · Doocs 题解来源

3265. 统计近似相等数对 I

中等1 种解法

标签：数组、哈希表、计数、枚举、排序

题目、示例与约束

给你一个正整数数组 nums 。

如果我们执行以下操作 至多一次 可以让两个整数 x 和 y 相等，那么我们称这个数对是 近似相等 的：

选择 x 或者 y 之一，将这个数字中的两个数位交换。

请你返回 nums 中，下标 i 和 j 满足 i < j 且 nums[i] 和 nums[j] 近似相等 的数对数目。

注意，执行操作后一个整数可以有前导 0 。

示例 1：

输入：nums = [3,12,30,17,21]

输出：2

解释：

近似相等数对包括：

3 和 30 。交换 30 中的数位 3 和 0 ，得到 3 。
12 和 21 。交换12 中的数位 1 和 2 ，得到 21 。

示例 2：

输入：nums = [1,1,1,1,1]

输出：10

解释：

数组中的任意两个元素都是近似相等的。

示例 3：

输入：nums = [123,231]

输出：0

解释：

我们无法通过交换 123 或者 231 中的两个数位得到另一个数。

提示：

2 <= nums.length <= 100
1 <= nums[i] <= 10⁶

方法一：排序 + 枚举 · Go 实现

思考

两数至多交换一次数位后相等则算一对。 $n \leq 100$ 、 $M \leq 10^{6}$ ，枚举数对再检查交换可以过，但「小数」无法通过交换变成「大数」的前导零形式，单向枚举会漏。

先排序，对每个数生成至多一次交换后的所有值，向已经出现的计数表查询。较小的数先入表，较大的数用交换去对齐较小者。

我们可以枚举每一个数，然后对于每一个数，我们可以枚举每一对不同的数位，然后交换这两个数位，得到一个新的数，记录到一个哈希表 $vis$ 中，表示这个数至多进行一次交换后的所有可能的数。然后计算前面枚举过的数中有多少个数在哈希表 $vis$ 中，累加到答案中。接下来，我们将当前枚举的数加入到哈希表 $cnt$ 中，表示当前枚举的数的个数。

这样枚举，会少统计一些数对，比如 $[100, 1]$ ，因为 $100$ 交换后的数是 $1$ ，而此前枚举过数不包含 $1$ ，因此会少统计一些数对。我们只需要在枚举之前，将数组排序，即可解决这个问题。

时间复杂度 $O (n \times (\log n + \log^{3} M))$ ，空间复杂度 $O (n + \log^{2} M)$ 。其中 $n$ 是数组 $nums$ 的长度，而 $M$ 是数组 $nums$ 中的最大值。

func countPairs(nums []int) (ans int) {
	sort.Ints(nums)
	cnt := make(map[int]int)

	for _, x := range nums {
		vis := make(map[int]struct{})
		vis[x] = struct{}{}
		s := []rune(strconv.Itoa(x))

		for j := 0; j < len(s); j++ {
			for i := 0; i < j; i++ {
				s[i], s[j] = s[j], s[i]
				y, _ := strconv.Atoi(string(s))
				vis[y] = struct{}{}
				s[i], s[j] = s[j], s[i]
			}
		}

		for y := range vis {
			ans += cnt[y]
		}
		cnt[x]++
	}

	return
}

力扣原题 · Doocs 题解来源

3267. 统计近似相等数对 II

困难1 种解法

标签：数组、哈希表、计数、枚举、排序

题目、示例与约束

注意：在这个问题中，操作次数增加为至多两次。

给你一个正整数数组 nums 。

如果我们执行以下操作 至多两次 可以让两个整数 x 和 y 相等，那么我们称这个数对是 近似相等 的：

选择 x 或者 y 之一，将这个数字中的两个数位交换。

请你返回 nums 中，下标 i 和 j 满足 i < j 且 nums[i] 和 nums[j] 近似相等 的数对数目。

注意，执行操作后得到的整数可以有前导 0 。

示例 1：

输入：nums = [1023,2310,2130,213]

输出：4

解释：

近似相等数对包括：

1023 和 2310 。交换 1023 中数位 1 和 2 ，然后交换数位 0 和 3 ，得到 2310 。
1023 和 213 。交换 1023 中数位 1 和 0 ，然后交换数位 1 和 2 ，得到 0213 ，也就是 213 。
2310 和 213 。交换 2310 中数位 2 和 0 ，然后交换数位 3 和 2 ，得到 0213 ，也就是 213 。
2310 和 2130 。交换 2310 中数位 3 和 1 ，得到 2130 。

示例 2：

输入：nums = [1,10,100]

输出：3

解释：

近似相等数对包括：

1 和 10 。交换 10 中数位 1 和 0 ，得到 01 ，也就是 1 。
1 和 100 。交换 100 中数位 1 和从左往右的第二个 0 ，得到 001 ，也就是 1 。
10 和 100 。交换 100 中数位 1 和从左往右的第一个 0 ，得到 010 ，也就是 10 。

提示：

2 <= nums.length <= 5000
1 <= nums[i] < 10⁷

方法一：排序 + 枚举 · Go 实现

思考

与 I 相比允许两次交换，且 $n \leq 5000$ 。仍先排序以免「大数换出小数」漏计；每个数的交换闭包变为两轮换位，规模为 $\log^{4} M$ 级，与 $n$ 相乘可过。

对当前数先做一次换位，再在剩余数位上做第二次，全部放入集合后查已出现计数。实现上注意第二次枚举不要回到已还原的状态即可。

我们可以枚举每一个数，然后对于每一个数，我们可以枚举每一对不同的数位，然后交换这两个数位，得到一个新的数，记录到一个哈希表 $vis$ 中，表示这个数至多进行一次交换后的所有可能的数，然后继续枚举每一对不同的数位，交换这两个数位，得到一个新的数，记录到哈希表 $vis$ 中，表示这个数至多进行两次交换后的所有可能的数。

时间复杂度 $O (n \times (\log n + \log^{5} M))$ ，空间复杂度 $O (n + \log^{4} M)$ 。其中 $n$ 是数组 $nums$ 的长度，而 $M$ 是数组 $nums$ 中的最大值。

func countPairs(nums []int) (ans int) {
	sort.Ints(nums)
	cnt := make(map[int]int)

	for _, x := range nums {
		vis := make(map[int]struct{})
		vis[x] = struct{}{}
		s := []rune(strconv.Itoa(x))

		for j := 0; j < len(s); j++ {
			for i := 0; i < j; i++ {
				s[i], s[j] = s[j], s[i]
				y, _ := strconv.Atoi(string(s))
				vis[y] = struct{}{}
				for q := i + 1; q < len(s); q++ {
					for p := i + 1; p < q; p++ {
						s[p], s[q] = s[q], s[p]
						z, _ := strconv.Atoi(string(s))
						vis[z] = struct{}{}
						s[p], s[q] = s[q], s[p]
					}
				}
				s[i], s[j] = s[j], s[i]
			}
		}

		for y := range vis {
			ans += cnt[y]
		}
		cnt[x]++
	}

	return
}

力扣原题 · Doocs 题解来源

3295. 举报垃圾信息

中等1 种解法

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

题目、示例与约束

给你一个字符串数组 message 和一个字符串数组 bannedWords。

如果数组中至少存在两个单词与 bannedWords 中的任一单词 完全相同，则该数组被视为 垃圾信息。

如果数组 message 是垃圾信息，则返回 true；否则返回 false。

示例 1：

输入： message = ["hello","world","leetcode"], bannedWords = ["world","hello"]

输出： true

解释：

数组 message 中的 "hello" 和 "world" 都出现在数组 bannedWords 中。

示例 2：

输入： message = ["hello","programming","fun"], bannedWords = ["world","programming","leetcode"]

输出： false

解释：

数组 message 中只有一个单词（"programming"）出现在数组 bannedWords 中。

提示：

1 <= message.length, bannedWords.length <= 10⁵
1 <= message[i].length, bannedWords[i].length <= 15
message[i] 和 bannedWords[i] 都只由小写英文字母组成。

方法一：哈希表 · Go 实现

思考

消息中至少两个词落在禁用表则判垃圾。 $n, m \leq 10^{5}$ ，对每个词扫描禁用表为平方。

禁用词放入哈希集合，遍历消息统计命中个数，达到 $2$ 即为真。期望线性。

我们用一个哈希表 $s$ 存储 $bannedWords$ 中的所有单词，然后遍历 $message$ 中的每个单词，如果单词在哈希表 $s$ 中出现，我们就将计数器 $c n t$ 加一，如果 $c n t$ 大于等于 $2$ ，我们就返回 $true$ ，否则返回 $false$ 。

时间复杂度 $O ((n + m) \times | w |)$ ，空间复杂度 $O (m \times | w |)$ 。其中 $n$ 是数组 $message$ 的长度，而 $m$ 和 $| w |$ 分别是数组 $bannedWords$ 的长度和数组中单词的最大长度。

func reportSpam(message []string, bannedWords []string) bool {
	s := map[string]bool{}
	for _, w := range bannedWords {
		s[w] = true
	}
	cnt := 0
	for _, w := range message {
		if s[w] {
			cnt++
			if cnt >= 2 {
				return true
			}
		}
	}
	return false
}

力扣原题 · Doocs 题解来源

3365. 重排子字符串以形成目标字符串

中等1 种解法

标签：哈希表、字符串、排序

题目、示例与约束

给你两个字符串 s 和 t（它们互为字母异位词），以及一个整数 k。

你的任务是判断是否可以将字符串 s 分割成 k 个等长的子字符串，然后重新排列这些子字符串，并以任意顺序连接它们，使得最终得到的新字符串与给定的字符串 t 相匹配。

如果可以做到，返回 true；否则，返回 false。

字母异位词 是指由另一个单词或短语的所有字母重新排列形成的单词或短语，使用所有原始字母恰好一次。

子字符串 是字符串中的一个连续非空字符序列。

示例 1：

输入： s = "abcd", t = "cdab", k = 2

输出： true

解释：

将 s 分割成 2 个长度为 2 的子字符串：["ab", "cd"]。
重新排列这些子字符串为 ["cd", "ab"]，然后连接它们得到 "cdab"，与 t 相匹配。

示例 2：

输入： s = "aabbcc", t = "bbaacc", k = 3

输出： true

解释：

将 s 分割成 3 个长度为 2 的子字符串：["aa", "bb", "cc"]。
重新排列这些子字符串为 ["bb", "aa", "cc"]，然后连接它们得到 "bbaacc"，与 t 相匹配。

示例 3：

输入： s = "aabbcc", t = "bbaacc", k = 2

输出： false

解释：

将 s 分割成 2 个长度为 3 的子字符串：["aab", "bcc"]。
这些子字符串无法重新排列形成 t = "bbaacc"，所以输出 false。

提示：

1 <= s.length == t.length <= 2 * 10⁵
1 <= k <= s.length
s.length 能被 k 整除。
s 和 t 仅由小写英文字母组成。
输入保证 s 和 t 互为字母异位词。

方法一：哈希表 · Go 实现

思考

把 $s$ 与 $t$ 都切成 $k$ 段等长块，问块的多重集是否相同。 $n \leq 2 \times 10^{5}$ ，用计数比较即可。

对 $s$ 的每块 $+ 1$ 、对 $t$ 的每块 $- 1$ ，最后计数全为 $0$ 则可以重排得到 $t$ 。

输入已保证字母总频次相同，故只需比较分块后的多重集。

我们记字符串 $s$ 的长度为 $n$ ，那么每个子字符串的长度为 $m = n / k$ 。

用一个哈希表 $cnt$ 记录每个长度为 $m$ 的子字符串在字符串 $s$ 中出现的次数与在字符串 $t$ 中出现的次数之差。

遍历字符串 $s$ ，每次取出长度为 $m$ 的子字符串，更新哈希表 $cnt$ 。

最后判断哈希表 $cnt$ 中的所有值是否都为 $0$ 。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为字符串 $s$ 的长度。

func isPossibleToRearrange(s string, t string, k int) bool {
	n := len(s)
	m := n / k
	cnt := map[string]int{}
	for i := 0; i < n; i += m {
		cnt[s[i:i+m]]++
		cnt[t[i:i+m]]--
	}
	for _, v := range cnt {
		if v != 0 {
			return false
		}
	}
	return true
}

力扣原题 · Doocs 题解来源

3371. 识别数组中的最大异常值

中等1 种解法

标签：数组、哈希表、计数、枚举

题目、示例与约束

给你一个整数数组 nums。该数组包含 n 个元素，其中恰好有 n - 2 个元素是 特殊数字 。剩下的两个元素中，一个是所有 特殊数字 的和，另一个是 异常值 。

异常值 的定义是：既不是原始特殊数字之一，也不是表示元素和的那个数。

注意，特殊数字、和以及异常值的下标必须不同，但可以共享相同的值。

返回 nums 中可能的最大异常值。

示例 1：

输入： nums = [2,3,5,10]

输出： 10

解释：

特殊数字可以是 2 和 3，因此和为 5，异常值为 10。

示例 2：

输入： nums = [-2,-1,-3,-6,4]

输出： 4

解释：

特殊数字可以是 -2、-1 和 -3，因此和为 -6，异常值为 4。

示例 3：

输入： nums = [1,1,1,1,1,5,5]

输出： 5

解释：

特殊数字可以是 1、1、1、1 和 1，因此和为 5，另一个 5 为异常值。

提示：

3 <= nums.length <= 10⁵
-1000 <= nums[i] <= 1000
输入保证 nums 中至少存在一个可能的异常值。

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

思考

数组由若干普通元素、它们的和、以及一个异常值构成。 $n \leq 10^{5}$ ，枚举异常值并 $O (1)$ 验证。

总和为 $s$ 。若 $x$ 是异常值，则 $s - x$ 必须是偶数，且 $(s - x) / 2$ 作为「和」必须在其余元素中出现。

哈希表计频率：当「和」等于 $x$ 时需至少两份。取满足条件的最大 $x$ 。

我们用一个哈希表 $cnt$ 记录数组 $nums$ 中每个元素出现的次数。

接下来，我们枚举数组 $nums$ 中的每个元素 $x$ 作为可能的异常值，对于每个 $x$ ，我们计算数组 $nums$ 中除了 $x$ 之外的所有元素的和 $t$ ，如果 $t$ 不是偶数，或者 $t$ 的一半不在 $cnt$ 中，那么 $x$ 不满足条件，我们跳过这个 $x$ 。否则，如果 $x$ 不等于 $t$ 的一半，或者 $x$ 在 $cnt$ 中出现的次数大于 $1$ ，那么 $x$ 是一个可能的异常值，我们更新答案。

枚举结束后，返回答案即可。

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

func getLargestOutlier(nums []int) int {
	s := 0
	cnt := map[int]int{}
	for _, x := range nums {
		s += x
		cnt[x]++
	}
	ans := math.MinInt32
	for x, v := range cnt {
		t := s - x
		if t%2 != 0 || cnt[t/2] == 0 {
			continue
		}
		if x != t/2 || v > 1 {
			ans = max(ans, x)
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

3375. 使数组的值全部为 K 的最少操作次数

简单1 种解法

标签：数组、哈希表

题目、示例与约束

给你一个整数数组 nums 和一个整数 k 。

如果一个数组中所有 严格大于 h 的整数值都相等，那么我们称整数 h 是 合法的 。

比方说，如果 nums = [10, 8, 10, 8] ，那么 h = 9 是一个合法整数，因为所有满足 nums[i] > 9 的数都等于 10 ，但是 5 不是合法整数。

你可以对 nums 执行以下操作：

选择一个整数 h ，它对于当前 nums 中的值是合法的。
对于每个下标 i ，如果它满足 nums[i] > h ，那么将 nums[i] 变为 h 。

你的目标是将 nums 中的所有元素都变为 k ，请你返回最少操作次数。如果无法将所有元素都变 k ，那么返回 -1 。

示例 1：

输入：nums = [5,2,5,4,5], k = 2

输出：2

解释：

依次选择合法整数 4 和 2 ，将数组全部变为 2 。

示例 2：

输入：nums = [2,1,2], k = 2

输出：-1

解释：

没法将所有值变为 2 。

示例 3：

输入：nums = [9,7,5,3], k = 1

输出：4

解释：

依次选择合法整数 7 ，5 ，3 和 1 ，将数组全部变为 1 。

提示：

1 <= nums.length <= 100
1 <= nums[i] <= 100
1 <= k <= 100

方法一：哈希表 · Go 实现

思考

每次把所有大于当前次大值 $h$ 的数改成 $h$ ，最终要变成 $k$ 。操作只会变小，故若存在小于 $k$ 的数则无解。

每次操作恰好消灭当前最大值这一档。不同的大于 $k$ 的值各需一次操作；若最小值已经是 $k$ ，则这一档不必再改。

因此用集合去重后，答案为不同值个数减去 $[mi = k]$ 。

根据题目描述，我们每次可以选择当前数组中的次大值作为合法整数 $h$ ，将所有大于 $h$ 的数都变为 $h$ ，这样可以使得操作次数最少。另外，由于操作会使得数字变小，因此，如果当前数组中存在小于 $k$ 的数，那么我们就无法将所有数都变为 $k$ ，直接返回 -1 即可。

我们遍历数组 $nums$ ，对于当前的数 $x$ ，如果 $x < k$ ，直接返回 -1；否则，我们将 $x$ 加入哈希表中，并且更新当前数组中的最小值 $mi$ 。最后，我们返回哈希表的大小减去 1（如果 $mi = k$ ，则需要减去 1）。

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

func minOperations(nums []int, k int) int {
	mi := 1 << 30
	s := map[int]bool{}
	for _, x := range nums {
		if x < k {
			return -1
		}
		s[x] = true
		mi = min(mi, x)
	}
	if mi == k {
		return len(s) - 1
	}
	return len(s)
}

力扣原题 · Doocs 题解来源

3396. 使数组元素互不相同所需的最少操作次数

简单1 种解法

标签：数组、哈希表

题目、示例与约束

给你一个整数数组 nums，你需要确保数组中的元素 互不相同 。为此，你可以执行以下操作任意次：

从数组的开头移除 3 个元素。如果数组中元素少于 3 个，则移除所有剩余元素。

注意：空数组也视作为数组元素互不相同。返回使数组元素互不相同所需的 最少操作次数 。

示例 1：

输入： nums = [1,2,3,4,2,3,3,5,7]

输出： 2

解释：

第一次操作：移除前 3 个元素，数组变为 [4, 2, 3, 3, 5, 7]。
第二次操作：再次移除前 3 个元素，数组变为 [3, 5, 7]，此时数组中的元素互不相同。

因此，答案是 2。

示例 2：

输入： nums = [4,5,6,4,4]

输出： 2

解释：

第一次操作：移除前 3 个元素，数组变为 [4, 4]。
第二次操作：移除所有剩余元素，数组变为空。

因此，答案是 2。

示例 3：

输入： nums = [6,7,8,9]

输出： 0

解释：

数组中的元素已经互不相同，因此不需要进行任何操作，答案是 0。

提示：

1 <= nums.length <= 100
1 <= nums[i] <= 100

方法一：哈希表 + 倒序遍历 · Go 实现

思考

每次删掉最前面 $3$ 个元素，直到剩余部分互不相同。 $n \leq 100$ ，倒序找「最长的无重复后缀」。

从右往左把元素放入集合，一旦遇到重复，下标 $0. . i$ 都必须删掉，操作次数为 $⌊ i / 3 ⌋ + 1$ 。

若一直无重复，则一次都不必做。

我们可以倒序遍历数组 $nums$ ，并使用哈希表 $s$ 记录已经遍历过的元素。当遍历到元素 $nums [i]$ 时，如果 $nums [i]$ 已经在哈希表 $s$ 中，那么说明我们需要移除 $nums [0. . i]$ 的所有元素，需要的操作次数为 $⌊ \frac{i}{3} ⌋ + 1$ 。否则，我们将 $nums [i]$ 加入哈希表 $s$ 中，并继续遍历下一个元素。

遍历结束后，如果没有找到重复的元素，那么数组中的元素已经互不相同，不需要进行任何操作，答案为 $0$ 。

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

func minimumOperations(nums []int) int {
	s := map[int]bool{}
	for i := len(nums) - 1; i >= 0; i-- {
		if s[nums[i]] {
			return i/3 + 1
		}
		s[nums[i]] = true
	}
	return 0
}

力扣原题 · Doocs 题解来源

3431. 对数字排序的最小解锁下标 🔒

中等1 种解法

标签：数组、哈希表

题目、示例与约束

给定一个仅包含 1、2、3 的整数的数组 nums，以及一个相同大小的 二进制 数组 locked。

当满足 nums[i] - nums[i + 1] == 1 且 locked[i] == 0时，则允许交换下标 i 和 i + 1 处的元素；如果可以通过交换相邻元素将 nums 升序排序，我们认为 nums 是 可排序的。

你可以进行若干次操作，每次操作可以将 locked[i] 设置为 0，从而解锁下标 i。

返回使 nums 满足 可排序的 所需最小操作次数。如果不可能使 nums 可排序，返回 -1。

示例 1：

输入：nums = [1,2,1,2,3,2], locked = [1,0,1,1,0,1]

输出：0

解释：

我们可以按如下交换来排序 nums。

交换下标 1 和 2
交换下标 4 和 5

所以，不需要解锁任何下标。

示例 2：

输入：nums = [1,2,1,1,3,2,2], locked = [1,0,1,1,0,1,0]

输出：2

解释：

如果我们解锁下标 2 和 5，我们可以按如下交换来排序 nums。

交换下标 1 和 2
交换下标 2 和 3
交换下标 4 和 5
交换下标 5 和 6

示例 3：

输入：nums = [1,2,1,2,3,2,1], locked = [0,0,0,0,0,0,0]

输出：-1

解释：

尽管所有下标都是解锁的，可以发现 nums 不可排序。

提示：

1 <= nums.length <= 10⁵
1 <= nums[i] <= 3
locked.length == nums.length
0 <= locked[i] <= 1

方法一：脑筋急转弯 · Go 实现

思考

数组只含 $1, 2, 3$ ，相邻交换还受 $locked$ 限制。若把所有逆序都模拟出来， $n \leq 10^{5}$ 无法承受。

能跨越的只有 $1$ 与 $2$ 、 $2$ 与 $3$ 。 $3$ 无法越过 $1$ ，故若某个 $3$ 出现在某个 $1$ 之前，无解。

需要解锁的位置，正是「最左的 $2$ 到最右的 $1$ 」以及「最左的 $3$ 到最右的 $2$ 」这两段里仍然上锁的下标。一遍扫描记下四个端点再计数即可。

根据题目描述，要使得 $nums$ 变成可排序的数组，需要满足数字 $3$ 的位置在数字 $1$ 的位置之后。如果数字 $3$ 的位置在数字 $1$ 的位置之前，那么无论怎么交换，数字 $3$ 都无法到达数字 $1$ 的位置，因此无法使得 $nums$ 变成可排序的数组。

我们分别用 $first2$ 和 $first3$ 表示数字 $2$ 和 $3$ 第一次出现的位置，用 $last1$ 和 $last2$ 表示数字 $1$ 和 $2$ 最后一次出现的位置。

那么当下标 $i$ 位于 $[first2, last1)$ 或者 $[first3, last2)]$ 时，对应的 $locked [i]$ 必须为 $0$ ，否则我们需要一次操作。因此，我们只需要遍历数组 $locked$ ，统计不满足条件的下标即可。

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

func minUnlockedIndices(nums []int, locked []int) (ans int) {
	n := len(nums)
	first2, first3 := n, n
	last1, last2 := -1, -1
	for i, x := range nums {
		if x == 1 {
			last1 = i
		} else if x == 2 {
			if i < first2 {
				first2 = i
			}
			last2 = i
		} else {
			if i < first3 {
				first3 = i
			}
		}
	}
	if first3 < last1 {
		return -1
	}
	for i, st := range locked {
		if st == 1 && ((first2 <= i && i < last1) || (first3 <= i && i < last2)) {
			ans++
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

3438. 找到字符串中合法的相邻数字

简单1 种解法

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

题目、示例与约束

给你一个只包含数字的字符串 s 。如果 s 中两个相邻的数字满足以下条件，我们称它们是 合法的 ：

前面的数字 不等于 第二个数字。
两个数字在 s 中出现的次数恰好分别等于这个数字本身。

请你从左到右遍历字符串 s ，并返回最先找到的合法相邻数字。如果这样的相邻数字不存在，请你返回一个空字符串。

示例 1：

输入：s = "2523533"

输出："23"

解释：

数字 '2' 出现 2 次，数字 '3' 出现 3 次。"23" 中每个数字在 s 中出现的次数都恰好分别等于数字本身。所以输出 "23" 。

示例 2：

输入：s = "221"

输出："21"

解释：

数字 '2' 出现 2 次，数字 '1' 出现 1 次。所以输出 "21" 。

示例 3：

输入：s = "22"

输出：""

解释：

没有合法的相邻数字。

提示：

2 <= s.length <= 100
s 只包含 '1' 到 '9' 的数字。

方法一：计数 · Go 实现

思考

合法对要求两数字不同，且各自在全串中的出现次数恰好等于该数字本身。 $| s | \leq 100$ ，先计数再扫相邻对即可。

若边扫边计数，右侧尚未出现的数字会把频次算错。

先用长为 $10$ 的数组统计全局频次，再按从左到右的相邻对检查 $x \neq y$ 且 $c n t [x] = x$ 、 $c n t [y] = y$ ，返回第一对。

我们可以用一个长度为 $10$ 的数组 $cnt$ 记录字符串 $s$ 中每个数字出现的次数。

然后我们遍历字符串 $s$ 中的相邻数字对，如果这两个数字不相等且满足这两个数字出现的次数分别等于这两个数字本身，我们就找到了一个合法的相邻数字对，返回即可。

遍历结束后，如果没有找到合法的相邻数字对，我们返回一个空字符串。

时间复杂度 $O (n)$ ，其中 $n$ 为字符串 $s$ 的长度。空间复杂度 $O (| Σ |)$ ，其中 $Σ$ 为字符串 $s$ 中出现的字符集，本题中 $Σ = {1, 2, \dots, 9}$ 。

func findValidPair(s string) string {
	cnt := [10]int{}
	for _, c := range s {
		cnt[c-'0']++
	}
	for i := 1; i < len(s); i++ {
		x, y := int(s[i-1]-'0'), int(s[i]-'0')
		if x != y && cnt[x] == x && cnt[y] == y {
			return s[i-1 : i+1]
		}
	}
	return ""
}

力扣原题 · Doocs 题解来源

3442. 奇偶频次间的最大差值 I

简单1 种解法

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

题目、示例与约束

给你一个由小写英文字母组成的字符串 s。

请你找出字符串中两个字符 a₁ 和 a₂ 的出现频次之间的最大差值 diff = freq(a₁) - freq(a₂)，这两个字符需要满足：

a₁ 在字符串中出现 奇数次 。
a₂ 在字符串中出现 偶数次 。

返回最大差值。

示例 1：

输入：s = "aaaaabbc"

输出：3

解释：

字符 'a' 出现 奇数次 ，次数为 5 ；字符 'b' 出现 偶数次 ，次数为 2 。
最大差值为 5 - 2 = 3 。

示例 2：

输入：s = "abcabcab"

输出：1

解释：

字符 'a' 出现 奇数次 ，次数为 3 ；字符 'c' 出现 偶数次 ，次数为 2 。
最大差值为 3 - 2 = 1 。

提示：

3 <= s.length <= 100
s 仅由小写英文字母组成。
s 至少由一个出现奇数次的字符和一个出现偶数次的字符组成。

方法一：计数 · Go 实现

思考

只要最大奇数频次减去最小偶数频次。字符串只含小写字母，计数一次即可。

无需枚举子串，题面针对整串的频次。

用计数器扫一遍，奇数频次取最大，偶数频次取最小，作差返回。

我们可以用一个哈希表或数组 $cnt$ 记录字符串 $s$ 中每个字符的出现次数。然后遍历 $cnt$ ，找出出现奇数次的字符的最大频次 $a$ 和出现偶数次的字符的最小频次 $b$ ，最后返回 $a - b$ 即可。

时间复杂度 $O (n)$ ，其中 $n$ 是字符串 $s$ 的长度。空间复杂度 $O (| Σ |)$ ，其中 $Σ$ 是字符集，本题中 $| Σ | = 26$ 。

func maxDifference(s string) int {
	cnt := [26]int{}
	for _, c := range s {
		cnt[c-'a']++
	}
	a, b := 0, 1<<30
	for _, v := range cnt {
		if v%2 == 1 {
			a = max(a, v)
		} else if v > 0 {
			b = min(b, v)
		}
	}
	return a - b
}

力扣原题 · Doocs 题解来源

3447. 将元素分配给有约束条件的组

中等1 种解法

标签：数组、哈希表

题目、示例与约束

给你一个整数数组 groups，其中 groups[i] 表示第 i 组的大小。另给你一个整数数组 elements。

请你根据以下规则为每个组分配一个元素：

如果 groups[i] 能被 elements[j] 整除，则下标为 j 的元素可以分配给组 i。
如果有多个元素满足条件，则分配 最小的下标 j 的元素。
如果没有元素满足条件，则分配 -1 。

返回一个整数数组 assigned，其中 assigned[i] 是分配给组 i 的元素的索引，若无合适的元素，则为 -1。

注意：一个元素可以分配给多个组。

示例 1：

输入： groups = [8,4,3,2,4], elements = [4,2]

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

解释：

elements[0] = 4 被分配给组 0、1 和 4。
elements[1] = 2 被分配给组 3。
无法为组 2 分配任何元素，分配 -1 。

示例 2：

输入： groups = [2,3,5,7], elements = [5,3,3]

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

解释：

elements[1] = 3 被分配给组 1。
elements[0] = 5 被分配给组 2。
无法为组 0 和组 3 分配任何元素，分配 -1 。

示例 3：

输入： groups = [10,21,30,41], elements = [2,1]

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

解释：

elements[0] = 2 被分配给所有偶数值的组，而 elements[1] = 1 被分配给所有奇数值的组。

提示：

1 <= groups.length <= 10⁵
1 <= elements.length <= 10⁵
1 <= groups[i] <= 10⁵
1 <= elements[i] <= 10⁵

方法一：枚举 · Go 实现

思考

每个 $groups [i]$ 要分到能整除它的、下标最小的 $elements [j]$ 。若对每个组扫描全部元素， $n, m \leq 10^{5}$ 会超时。

值域 $M \leq 10^{5}$ ，从因子去标记倍数，类似埃氏筛，每个数只被其因子更新一次。

按 $elements$ 从左到右，对尚未标记的 $x$ 遍历 $x, 2 x, \dots \leq M$ ，把 $d [y]$ 写成当前下标。组的答案即 $d [groups [i]]$ 。重复因子跳过，避免后出现的更大下标覆盖。

我们先找到数组 $groups$ 中的最大值，记为 $mx$ 。用一个数组 $d$ 记录每个元素对应的下标，初始时 $d [x] = - 1$ 表示元素 $x$ 还没有被分配。

然后我们遍历数组 $elements$ ，对于每个元素 $x$ ，如果 $x > mx$ 或者 $d [x] \neq - 1$ ，说明元素 $x$ 无法被分配或者已经被分配，直接跳过。否则，我们从 $x$ 开始，每次加上 $x$ ，将 $d [y]$ 设为 $j$ ，表示元素 $y$ 被分配给了下标 $j$ 。

最后我们遍历数组 $groups$ ，根据 $d$ 数组的记录，得到答案。

时间复杂度 $O (M \times \log m + n)$ ，空间复杂度 $O (M)$ 。其中 $n$ 和 $m$ 分别是数组 $groups$ 和 $elements$ 的长度；而 $M$ 是数组 $groups$ 中的最大值。

func assignElements(groups []int, elements []int) (ans []int) {
	mx := slices.Max(groups)
	d := make([]int, mx+1)
	for i := range d {
		d[i] = -1
	}
	for j, x := range elements {
		if x > mx || d[x] != -1 {
			continue
		}
		for y := x; y <= mx; y += x {
			if d[y] == -1 {
				d[y] = j
			}
		}
	}
	for _, x := range groups {
		ans = append(ans, d[x])
	}
	return
}

力扣原题 · Doocs 题解来源

3450. 一张长椅上的最多学生 🔒

简单1 种解法

标签：数组、哈希表

题目、示例与约束

给定一个包含学生数据的 2 维数组 students，其中 students[i] = [student_id, bench_id] 表示学生 student_id 正坐在长椅 bench_id 上。

返回单个长凳上坐着的不同学生的最大数量。如果没有学生，返回 0。

注意：一个学生在输入中可以出现在同一张长椅上多次，但每个长椅上只能计算一次。

示例 1：

输入：students = [[1,2],[2,2],[3,3],[1,3],[2,3]]

输出：3

解释：

长椅 2 上有 2 个不同学生：[1, 2]。
长椅 3 上有 3 个不同学生：[1, 2, 3]。
一张长椅上不同学生的最大数量是 3。

示例 2：

输入：students = [[1,1],[2,1],[3,1],[4,2],[5,2]]

输出：3

示例：

长椅 1 上有 3 个不同学生：[1, 2, 3]。
长椅 2 上有 2 个不同学生：[4, 5]。
一张长椅上不同学生的最大数量是 3。

示例 3：

输入：students = [[1,1],[1,1]]

输出：1

解释：

一张长椅上不同学生的最大数量是 1。

示例 4：

输入：students = []

输出：0

解释：

由于不存在学生，输出为 0。

提示：

0 <= students.length <= 100
students[i] = [student_id, bench_id]
1 <= student_id <= 100
1 <= bench_id <= 100

方法一：哈希表 · Go 实现

思考

同一长椅上同一学生可能出现多次，要的是不同学生数的最大值。数据只有 $100$ 条。

用集合去重比再排序计数更直接。

哈希表以椅号为键、学生编号集合为值，取集合大小的最大值；空输入则返回 $0$ 。

我们用一个哈希表 $d$ 来存储每个长椅上的学生，键为长椅编号，值为一个集合，集合中存储着该长椅上的学生编号。

遍历学生数组 $students$ ，将学生编号和长椅编号存入哈希表 $d$ 中。

最后，我们遍历哈希表 $d$ 的值，取出集合的大小的最大值即为一张长椅上坐着的不同学生的最大数量。

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

func maxStudentsOnBench(students [][]int) (ans int) {
	d := make(map[int]map[int]struct{})
	for _, e := range students {
		studentId, benchId := e[0], e[1]
		if _, exists := d[benchId]; !exists {
			d[benchId] = make(map[int]struct{})
		}
		d[benchId][studentId] = struct{}{}
	}
	for _, s := range d {
		ans = max(ans, len(s))
	}
	return
}

力扣原题 · Doocs 题解来源

3471. 找出最大的几近缺失整数

简单1 种解法

标签：数组、哈希表

题目、示例与约束

给你一个整数数组 nums 和一个整数 k 。

如果整数 x 恰好仅出现在 nums 中的一个大小为 k 的子数组中，则认为 x 是 nums 中的几近缺失（almost missing）整数。

返回 nums 中 最大的几近缺失 整数，如果不存在这样的整数，返回 -1 。

子数组 是数组中的一个连续元素序列。

示例 1：

输入：nums = [3,9,2,1,7], k = 3

输出：7

解释：

1 出现在两个大小为 3 的子数组中：[9, 2, 1]、[2, 1, 7]
2 出现在三个大小为 3 的子数组中：[3, 9, 2]、[9, 2, 1]、[2, 1, 7]
3 出现在一个大小为 3 的子数组中：[3, 9, 2]
7 出现在一个大小为 3 的子数组中：[2, 1, 7]
9 出现在两个大小为 3 的子数组中：[3, 9, 2]、[9, 2, 1]

返回 7 ，因为它满足题意的所有整数中最大的那个。

示例 2：

输入：nums = [3,9,7,2,1,7], k = 4

输出：3

解释：

1 出现在两个大小为 4 的子数组中：[9, 7, 2, 1]、[7, 2, 1, 7]
2 出现在三个大小为 4 的子数组中：[3, 9, 7, 2]、[9, 7, 2, 1]、[7, 2, 1, 7]
3 出现在一个大小为 4 的子数组中：[3, 9, 7, 2]
7 出现在三个大小为 4 的子数组中：[3, 9, 7, 2]、[9, 7, 2, 1]、[7, 2, 1, 7]
9 出现在两个大小为 4 的子数组中：[3, 9, 7, 2]、[9, 7, 2, 1]

返回 3 ，因为它满足题意的所有整数中最大的那个。

示例 3：

输入：nums = [0,0], k = 1

输出：-1

解释：

不存在满足题意的整数。

提示：

1 <= nums.length <= 50
0 <= nums[i] <= 50
1 <= k <= nums.length

方法一：分情况讨论 · Go 实现

思考

几近缺失整数在全部长度为 $k$ 的窗里恰好出现一次。不同 $k$ 下候选集合不同，统一枚举每个值的出现次数会漏掉窗口覆盖关系。

$k = 1$ 时每个元素自成窗口，答案是出现恰好一次的最大值； $k = n$ 时只有一个窗口，答案是全局最大。

$1 < k < n$ 时，中间元素至少落在两个窗里，只有两端 $nums [0]$ 、 $nums [n - 1]$ 可能恰好出现一次。检查它们是否在别处重复，取较大者，否则 $- 1$ 。

如果 $k = 1$ ，那么数组中每个元素都构成一个大小为 $1$ 的子数组，此时我们只需要统计数组中只出现一次的元素中的最大值即可。

如果 $k = n$ ，那么整个数组构成一个大小为 $n$ 的子数组，此时我们只需要返回数组中的最大值即可。

如果 $1 < k < n$ ，只有 $nums [0]$ 和 $nums [n - 1]$ 可能是几近缺失整数，如果它们在数组中的其他位置出现过，那么它们就不是几近缺失整数。因此我们只需要判断 $nums [0]$ 和 $nums [n - 1]$ 是否在数组中的其他位置出现过即可，取其中的最大值返回。

如果不存在几近缺失整数，返回 $- 1$ 。

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

func largestInteger(nums []int, k int) int {
    if k == 1 {
        cnt := make(map[int]int)
        for _, x := range nums {
            cnt[x]++
        }
        ans := -1
        for x, v := range cnt {
            if v == 1 {
                ans = max(ans, x)
            }
        }
        return ans
    }

    n := len(nums)
    if k == n {
        return slices.Max(nums)
    }

    f := func(k int) int {
        for i, x := range nums {
            if i != k && x == nums[k] {
                return -1
            }
        }
        return nums[k]
    }

    return max(f(0), f(n-1))
}

力扣原题 · Doocs 题解来源

3483. 不同三位偶数的数目

简单1 种解法

标签：递归、数组、哈希表、枚举

题目、示例与约束

给你一个数字数组 digits，你需要从中选择三个数字组成一个三位偶数，你的任务是求出不同三位偶数的数量。

注意：每个数字在三位偶数中都只能使用一次，并且不能有前导零。

示例 1：

输入： digits = [1,2,3,4]

输出： 12

解释： 可以形成的 12 个不同的三位偶数是 124，132，134，142，214，234，312，314，324，342，412 和 432。注意，不能形成 222，因为数字 2 只有一个。

示例 2：

输入： digits = [0,2,2]

输出： 2

解释： 可以形成的三位偶数是 202 和 220。注意，数字 2 可以使用两次，因为数组中有两个 2 。

示例 3：

输入： digits = [6,6,6]

输出： 1

解释： 只能形成 666。

示例 4：

输入： digits = [1,3,5]

输出： 0

解释： 无法形成三位偶数。

提示：

3 <= digits.length <= 10
0 <= digits[i] <= 9

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

思考

从至多 $10$ 个数字里组成互不相同下标的三位偶数，统计不同数值。 $n^{3} \leq 10^{3}$ ，三重枚举足够。

个位必须偶数，百位不能为 $0$ ，三个下标两两不同。集合去重避免同一数字多种下标组合被算多次。

最外层枚举个位偶数 $a$ ，再枚举十位 $b$ 、百位 $c$ ，加入 $100 c + 10 b + a$ 。

我们用一个哈希表 $s$ 记录所有不同的三位偶数，然后枚举所有可能的三位偶数，将其加入哈希表中。

最后返回哈希表的大小即可。

时间复杂度 $O (n^{3})$ ，空间复杂度 $O (n^{3})$ 。其中 $n$ 为数组 $digits$ 的长度。

func totalNumbers(digits []int) int {
	s := make(map[int]struct{})
	for i, a := range digits {
		if a%2 == 1 {
			continue
		}
		for j, b := range digits {
			if i == j {
				continue
			}
			for k, c := range digits {
				if c == 0 || k == i || k == j {
					continue
				}
				s[c*100+b*10+a] = struct{}{}
			}
		}
	}
	return len(s)
}

力扣原题 · Doocs 题解来源

3522. 执行指令后的得分

中等1 种解法

标签：数组、哈希表、字符串、模拟

题目、示例与约束

给你两个数组：instructions 和 values，数组的长度均为 n。

你需要根据以下规则模拟一个过程：

从下标 i = 0 的第一个指令开始，初始得分为 0。
如果 instructions[i] 是 "add"：
- 将 values[i] 加到你的得分中。
- 移动到下一个指令 (i + 1)。
如果 instructions[i] 是 "jump"：
- 移动到下标为 (i + values[i]) 的指令，但不修改你的得分。

当以下任一情况发生时，过程会终止：

越界（即 i < 0 或 i >= n），或
尝试再次执行已经执行过的指令。被重复访问的指令不会再次执行。

返回过程结束时的得分。

示例 1：

输入： instructions = ["jump","add","add","jump","add","jump"], values = [2,1,3,1,-2,-3]

输出： 1

解释：

从下标 0 开始模拟过程：

下标 0：指令是 "jump"，移动到下标 0 + 2 = 2。
下标 2：指令是 "add"，将 values[2] = 3 加到得分中，移动到下标 3。得分变为 3。
下标 3：指令是 "jump"，移动到下标 3 + 1 = 4。
下标 4：指令是 "add"，将 values[4] = -2 加到得分中，移动到下标 5。得分变为 1。
下标 5：指令是 "jump"，移动到下标 5 + (-3) = 2。
下标 2：已经访问过。过程结束。

示例 2：

输入： instructions = ["jump","add","add"], values = [3,1,1]

输出： 0

解释：

从下标 0 开始模拟过程：

下标 0：指令是 "jump"，移动到下标 0 + 3 = 3。
下标 3：越界。过程结束。

示例 3：

输入： instructions = ["jump"], values = [0]

输出： 0

解释：

从下标 0 开始模拟过程：

下标 0：指令是 "jump"，移动到下标 0 + 0 = 0。
下标 0：已经访问过。过程结束。

提示：

n == instructions.length == values.length
1 <= n <= 10⁵
instructions[i] 只能是 "add" 或 "jump"。
-10⁵ <= values[i] <= 10⁵

方法一：模拟 · Go 实现

思考

指令形成一条带跳转的路径，重复执行同一下标会陷入环。用布尔数组标记已访问下标，从 $0$ 出发按 add 或 jump 前进。

越界或回到已访问位置即停，累加的分数即为答案。每条指令至多执行一次，线性即可。

我们根据题意模拟即可。

我们定义一个长度为 $n$ 的布尔数组 $vis$ ，用于记录每一条指令是否被执行过，初始时均为 $false$ 。

然后我们从下标 $i = 0$ 开始，循环执行以下操作：

将 $vis [i]$ 置为 $true$ ；
如果 $instructions [i]$ 的第一个字符为 'a'，那么我们将答案增加 $value [i]$ ，然后 $i$ 加 $1$ ；否则，我们将 $i$ 增加 $value [i]$ 。

循环，直至 $i < 0$ 或者 $i \geq n$ ，或者 $vis [i]$ 为 $true$ 。

最后返回答案即可。

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

func calculateScore(instructions []string, values []int) (ans int64) {
	n := len(values)
	vis := make([]bool, n)
	i := 0
	for i >= 0 && i < n && !vis[i] {
		vis[i] = true
		if instructions[i][0] == 'a' {
			ans += int64(values[i])
			i += 1
		} else {
			i += values[i]
		}
	}
	return
}

力扣原题 · Doocs 题解来源

3527. 找到最常见的回答

中等1 种解法

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

题目、示例与约束

给你一个二维字符串数组 responses，其中每个 responses[i] 是一个字符串数组，表示第 i 天调查的回答结果。

请返回在对每个 responses[i] 中的回答去重后，所有天数中 最常见 的回答。如果有多个回答出现频率相同，则返回 字典序最小 的那个回答。

示例 1：

输入： responses = [["good","ok","good","ok"],["ok","bad","good","ok","ok"],["good"],["bad"]]

输出： "good"

解释：

每个列表去重后，得到 responses = [["good", "ok"], ["ok", "bad", "good"], ["good"], ["bad"]]。
"good" 出现了 3 次，"ok" 出现了 2 次，"bad" 也出现了 2 次。
返回 "good"，因为它出现的频率最高。

示例 2：

输入： responses = [["good","ok","good"],["ok","bad"],["bad","notsure"],["great","good"]]

输出： "bad"

解释：

每个列表去重后，responses = [["good", "ok"], ["ok", "bad"], ["bad", "notsure"], ["great", "good"]]。
"bad"、"good" 和 "ok" 都出现了 2 次。
返回 "bad"，因为它在这些最高频率的词中字典序最小。

提示：

1 <= responses.length <= 1000
1 <= responses[i].length <= 1000
1 <= responses[i][j].length <= 10
responses[i][j] 仅由小写英文字母组成

方法一：哈希表 · Go 实现

思考

同一天的重复回答只计一次，跨天统计出现次数，再取次数最大且字典序最小者。

对每天先用集合去重，再用哈希表累加；最后一遍扫描比较次数与字典序。总长度线性。

我们可以用一个哈希表 $cnt$ 来统计每个回答的出现次数。对于每一天的回答，我们先去重，然后将每个回答加入哈希表中，更新其出现次数。

最后，我们遍历哈希表，找到出现次数最多的回答。如果有多个回答出现次数相同，则返回字典序最小的那个回答。

时间复杂度 $O (L)$ ，空间复杂度 $O (L)$ 。其中 $L$ 是所有回答的总长度。

func findCommonResponse(responses [][]string) string {
	cnt := map[string]int{}
	for _, ws := range responses {
		s := map[string]struct{}{}
		for _, w := range ws {
			if _, ok := s[w]; !ok {
				s[w] = struct{}{}
				cnt[w]++
			}
		}
	}
	ans := responses[0][0]
	for w, v := range cnt {
		if cnt[ans] < v || (cnt[ans] == v && w < ans) {
			ans = w
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

3531. 统计被覆盖的建筑

中等1 种解法

标签：数组、哈希表、排序

题目、示例与约束

给你一个正整数 n，表示一个 n x n 的城市，同时给定一个二维数组 buildings，其中 buildings[i] = [x, y] 表示位于坐标 [x, y] 的一个唯一建筑。

如果一个建筑在四个方向（左、右、上、下）中每个方向上都至少存在一个建筑，则称该建筑 被覆盖 。

返回 被覆盖 的建筑数量。

示例 1：

输入: n = 3, buildings = [[1,2],[2,2],[3,2],[2,1],[2,3]]

输出: 1

解释:

只有建筑 [2,2] 被覆盖，因为它在每个方向上都至少存在一个建筑：
- 上方 ([1,2])
- 下方 ([3,2])
- 左方 ([2,1])
- 右方 ([2,3])
因此，被覆盖的建筑数量是 1。

示例 2：

输入: n = 3, buildings = [[1,1],[1,2],[2,1],[2,2]]

输出: 0

解释:

没有任何一个建筑在每个方向上都有至少一个建筑。

示例 3：

输入: n = 5, buildings = [[1,3],[3,2],[3,3],[3,5],[5,3]]

输出: 1

解释:

只有建筑 [3,3] 被覆盖，因为它在每个方向上至少存在一个建筑：
- 上方 ([1,3])
- 下方 ([5,3])
- 左方 ([3,2])
- 右方 ([3,5])
因此，被覆盖的建筑数量是 1。

提示：

2 <= n <= 10⁵
1 <= buildings.length <= 10⁵
buildings[i] = [x, y]
1 <= x, y <= n
buildings 中所有坐标均唯一。

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

思考

覆盖条件是同一行左右、同一列上下都有建筑。若对每个点扫描整行整列，在点数较大时偏慢。

按横坐标、纵坐标分组并排序，则 $(x, y)$ 被覆盖当且仅当 $y$ 严格夹在该列最值之间且 $x$ 严格夹在该行最值之间。一次分组加线性检查即可。

我们可以将建筑按照横坐标和纵坐标进行分组，分别记录在哈希表 $g1$ 和 $g2$ 中，其中 $g1[x]$ 表示所有横坐标为 $x$ 的纵坐标，而 $g2[y]$ 表示所有纵坐标为 $y$ 的横坐标，然后我们将其进行排序。

接下来，我们遍历所有建筑，对于当前建筑 $(x, y)$ ，我们通过哈希表获取对应的纵坐标列表 $l_{1}$ 和横坐标列表 $l_{2}$ ，并检查条件以确定建筑是否被覆盖。覆盖的条件是 $l_{2} [0] < x < l_{2} [- 1]$ 且 $l_{1} [0] < y < l_{1} [- 1]$ ，若是，我们将答案加一。

遍历结束后，返回答案即可。

时间复杂度 $O (n \times \log n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 是建筑物的数量。

func countCoveredBuildings(n int, buildings [][]int) (ans int) {
	g1 := make(map[int][]int)
	g2 := make(map[int][]int)

	for _, building := range buildings {
		x, y := building[0], building[1]
		g1[x] = append(g1[x], y)
		g2[y] = append(g2[y], x)
	}

	for _, list := range g1 {
		sort.Ints(list)
	}
	for _, list := range g2 {
		sort.Ints(list)
	}

	for _, building := range buildings {
		x, y := building[0], building[1]
		l1 := g1[x]
		l2 := g2[y]

		if l2[0] < x && x < l2[len(l2)-1] && l1[0] < y && y < l1[len(l1)-1] {
			ans++
		}
	}
	return
}

力扣原题 · Doocs 题解来源

3541. 找到频率最高的元音和辅音

简单1 种解法

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

题目、示例与约束

给你一个由小写英文字母（'a' 到 'z'）组成的字符串 s。你的任务是找出出现频率最高的元音（'a'、'e'、'i'、'o'、'u' 中的一个）和出现频率最高的辅音（除元音以外的所有字母），并返回这两个频数之和。

注意：如果有多个元音或辅音具有相同的最高频率，可以任选其中一个。如果字符串中没有元音或没有辅音，则其频率视为 0。

一个字母 x 的频率是它在字符串中出现的次数。

示例 1：

输入: s = "successes"

输出: 6

解释:

元音有：'u' 出现 1 次，'e' 出现 2 次。最大元音频率 = 2。
辅音有：'s' 出现 4 次，'c' 出现 2 次。最大辅音频率 = 4。
输出为 2 + 4 = 6。

示例 2：

输入: s = "aeiaeia"

输出: 3

解释:

元音有：'a' 出现 3 次，'e' 出现 2 次，'i' 出现 2 次。最大元音频率 = 3。
s 中没有辅音。因此，最大辅音频率 = 0。
输出为 3 + 0 = 3。

提示:

1 <= s.length <= 100
s 只包含小写英文字母

方法一：计数 · Go 实现

思考

所求为出现次数最多的元音频次与最多的辅音频次之和，与具体字母无关。一次计数后分组取最大即可。

空类的最大频次视为 $0$ ，相加即答案。

我们先用一个哈希表或者一个长度为 $26$ 的数组 $cnt$ 统计每个字母的出现频率。然后我们遍历这个表，找出元音和辅音中出现频率最高的字母，返回它们的频率之和。

我们可以用一个变量 $a$ 记录元音的最大频率，另一个变量 $b$ 记录辅音的最大频率。遍历时，如果当前字母是元音，就更新 $a$ ；否则就更新 $b$ 。

最后返回 $a + b$ 即可。

时间复杂度 $O (n)$ ，其中 $n$ 是字符串的长度。空间复杂度 $O (| Σ |)$ ，其中 $| Σ |$ 是字母表的大小，这里是 $26$ 。

func maxFreqSum(s string) int {
	cnt := [26]int{}
	for _, c := range s {
		cnt[c-'a']++
	}
	a, b := 0, 0
	for i := range cnt {
		c := byte(i + 'a')
		if c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' {
			a = max(a, cnt[i])
		} else {
			b = max(b, cnt[i])
		}
	}
	return a + b
}

力扣原题 · Doocs 题解来源

3551. 数位和排序需要的最小交换次数

中等1 种解法

标签：数组、哈希表、排序

题目、示例与约束

给你一个由 互不相同 的正整数组成的数组 nums，需要根据每个数字的数位和（即每一位数字相加求和）按升序对数组进行排序。如果两个数字的数位和相等，则较小的数字排在前面。

返回将 nums 排列为上述排序顺序所需的最小交换次数。

一次交换定义为交换数组中两个不同位置的值。

示例 1：

输入: nums = [37,100]

输出: 1

解释:

计算每个整数的数位和：[3 + 7 = 10, 1 + 0 + 0 = 1] → [10, 1]
根据数位和排序：[100, 37]。将 37 与 100 交换，得到排序后的数组。
因此，将 nums 排列为排序顺序所需的最小交换次数为 1。

示例 2：

输入: nums = [22,14,33,7]

输出: 0

解释:

计算每个整数的数位和：[2 + 2 = 4, 1 + 4 = 5, 3 + 3 = 6, 7 = 7] → [4, 5, 6, 7]
根据数位和排序：[22, 14, 33, 7]。数组已经是排序好的。
因此，将 nums 排列为排序顺序所需的最小交换次数为 0。

示例 3：

输入: nums = [18,43,34,16]

输出: 2

解释:

计算每个整数的数位和：[1 + 8 = 9, 4 + 3 = 7, 3 + 4 = 7, 1 + 6 = 7] → [9, 7, 7, 7]
根据数位和排序：[16, 34, 43, 18]。将 18 与 16 交换，再将 43 与 34 交换，得到排序后的数组。
因此，将 nums 排列为排序顺序所需的最小交换次数为 2。

提示:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹
nums 由 互不相同 的正整数组成。

方法一：排序 + 置换环 · Go 实现

思考

任意两个位置都可以交换。先求出目标序列，再逐个把错位元素换到目标位置，在样例上能够得到正确答案，但 $n$ 达到 $10^{5}$ 时，每一步重新扫描剩余元素会退化成平方时间。任意交换下，最少次数由当前排列到目标排列的循环分解决定：长度为 $ℓ$ 的循环只需 $ℓ - 1$ 次即可归位，总数等于 $n$ 减去循环个数。目标序由 $(digitSum (x), x)$ 唯一确定，因此先排序建立每个值到目标下标的映射，再沿这条映射逐环访问；哈希表与遍历顺序都来自该置换本身。

我们先计算每个元素的数位和，把元素与数位和组成二元组，并按数位和升序排序；数位和相同时，数值较小的排在前面。排序后的顺序就是目标序列。

记数组长度为 $n$ 。把原数组看作一个置换：下标 $i$ 上的数值应当放到它在目标序列中的下标。若该置换含有 $c$ 个循环，则最少交换次数为 $n - c$ 。实现时用哈希表记下每个数值的目标下标，从每个尚未访问的位置出发，不断跳到当前数值应去的下标，直到进入已访问位置，这样就找出一个循环。答案初始化为 $n$ ，每发现一个循环就减一。

时间复杂度 $O (n \times \log n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 是数组 $nums$ 的长度。

func minSwaps(nums []int) int {
	n := len(nums)
	arr := make([][2]int, n)
	for i := 0; i < n; i++ {
		arr[i][0] = f(nums[i])
		arr[i][1] = nums[i]
	}
	sort.Slice(arr, func(i, j int) bool {
		if arr[i][0] != arr[j][0] {
			return arr[i][0] < arr[j][0]
		}
		return arr[i][1] < arr[j][1]
	})
	d := make(map[int]int, n)
	for i := 0; i < n; i++ {
		d[arr[i][1]] = i
	}
	vis := make([]bool, n)
	ans := n
	for i := 0; i < n; i++ {
		if !vis[i] {
			ans--
			j := i
			for !vis[j] {
				vis[j] = true
				j = d[nums[j]]
			}
		}
	}
	return ans
}

func f(x int) int {
	s := 0
	for x != 0 {
		s += x % 10
		x /= 10
	}
	return s
}

力扣原题 · Doocs 题解来源

LeetCode Go · 哈希表（7） ​

3146. 两个字符串的排列差 ​

3159. 查询数组中元素的出现位置 ​

3160. 所有球里面不同颜色的数目 ​

3162. 优质数对的总数 I ​

3164. 优质数对的总数 II ​

3167. 字符串的更好压缩 🔒 ​

3184. 构成整天的下标对数目 I ​

3185. 构成整天的下标对数目 II ​

3223. 操作后字符串的最短长度 ​

3237. Alt 和 Tab 模拟 🔒 ​

3238. 求出胜利玩家的数目 ​

3265. 统计近似相等数对 I ​

3267. 统计近似相等数对 II ​

3295. 举报垃圾信息 ​

3365. 重排子字符串以形成目标字符串 ​

3371. 识别数组中的最大异常值 ​

3375. 使数组的值全部为 K 的最少操作次数 ​

3396. 使数组元素互不相同所需的最少操作次数 ​

3431. 对数字排序的最小解锁下标 🔒 ​

3438. 找到字符串中合法的相邻数字 ​

3442. 奇偶频次间的最大差值 I ​

3447. 将元素分配给有约束条件的组 ​

3450. 一张长椅上的最多学生 🔒 ​

3471. 找出最大的几近缺失整数 ​

3483. 不同三位偶数的数目 ​

3522. 执行指令后的得分 ​

3527. 找到最常见的回答 ​

3531. 统计被覆盖的建筑 ​

3541. 找到频率最高的元音和辅音 ​

3551. 数位和排序需要的最小交换次数 ​

继续阅读

LeetCode Go · 哈希表（7）

3146. 两个字符串的排列差

3159. 查询数组中元素的出现位置

3160. 所有球里面不同颜色的数目

3162. 优质数对的总数 I

3164. 优质数对的总数 II

3167. 字符串的更好压缩 🔒

3184. 构成整天的下标对数目 I

3185. 构成整天的下标对数目 II

3223. 操作后字符串的最短长度

3237. Alt 和 Tab 模拟 🔒

3238. 求出胜利玩家的数目

3265. 统计近似相等数对 I

3267. 统计近似相等数对 II

3295. 举报垃圾信息

3365. 重排子字符串以形成目标字符串

3371. 识别数组中的最大异常值

3375. 使数组的值全部为 K 的最少操作次数

3396. 使数组元素互不相同所需的最少操作次数

3431. 对数字排序的最小解锁下标 🔒

3438. 找到字符串中合法的相邻数字

3442. 奇偶频次间的最大差值 I

3447. 将元素分配给有约束条件的组

3450. 一张长椅上的最多学生 🔒

3471. 找出最大的几近缺失整数

3483. 不同三位偶数的数目

3522. 执行指令后的得分

3527. 找到最常见的回答

3531. 统计被覆盖的建筑

3541. 找到频率最高的元音和辅音

3551. 数位和排序需要的最小交换次数