LeetCode Go · 哈希表（2）

返回题库与筛选 · 收录范围与使用说明

来源与许可

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

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

791. 自定义字符串排序

中等2 种解法

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

题目、示例与约束

给定两个字符串 order 和 s 。order 的所有字母都是 唯一 的，并且预先按照一些自定义的顺序排序。

对 s 的字符进行置换，使其与排序的 order 相匹配。更具体地说，如果在 order 中的字符 x 出现字符 y 之前，那么在排列后的字符串中， x 也应该出现在 y 之前。

返回 满足这个性质的 s 的任意一种排列 。

 

示例 1：

输入： order = "cba", s = "abcd"

输出： "cbad"

解释： "a"，"b"，"c" 在 order 中出现，所以 "a"，"b"，"c" 的顺序应该是 "c"，"b"，和 "a"。

由于 "d" 没有在 order 中出现，它可以在返回字符串的任意位置。"dcba"，"cdba"，"cbda" 也是合法的输出。

示例 2：

输入： order = "bcafg", s = "abcd"

输出： "bcad"

解释：order 中的字符 "b"、"c" 和 "a" 决定了 s 中字符的顺序。s 中的字符 "d" 没有出现在 order 中，因此其位置是可变的。

按照 order 中的出现顺序，"b"、"c" 和 "a" 应该按 "b"、"c"、"a" 的顺序排列。"d" 可以放在任何位置，因为它不受顺序限制。输出 "bcad" 正确遵循了这一规则。其他排列如 "dbca" 或 "bcda" 也是合法的，只要 "b"、"c"、"a" 的顺序保持不变。

 

提示:

• 1 <= order.length <= 26
• 1 <= s.length <= 200
• order 和 s 由小写英文字母组成
• order 中的所有字符都 不同

方法一：自定义排序 · Go 实现

思考

$s$ 要按 $order$ 中的相对顺序重排，未出现的字符顺序任意。直接按 $order$ 下标当键排序即可。

不在 $order$ 中的键取 $0$，会聚在前面，仍满足「相对顺序」的要求。

一种比较直接的思路是，用哈希表或数组 $d$ 记录字符串 $order$ 中每个字符的位置，然后对字符串 $s$ 中每个字符按照其在 $d$ 中的位置进行排序。如果某个字符不在 $d$ 中，我们可以将其位置置为 $0$。

时间复杂度 $O(m+n\times \log n)$，空间复杂度 $O(m)$。其中 $m$ 和 $n$ 分别是字符串 $order$ 和 $s$ 的长度。

func customSortString(order string, s string) string {
	d := [26]int{}
	for i := range order {
		d[order[i]-'a'] = i
	}
	cs := []byte(s)
	sort.Slice(cs, func(i, j int) bool { return d[cs[i]-'a'] < d[cs[j]-'a'] })
	return string(cs)
}

方法二：字符计数 · Go 实现

思考

排序多了 $n\log n$。先计数，再按 $order$ 依次输出对应个数，剩余字符任意追加，线性即可。

我们还可以先统计 $s$ 中每个字符的出现次数，存储在 $cnt$ 数组中。

然后把字符串 $s$ 在 $order$ 中出现的字符按照 $order$ 中的顺序排序，添加到结果字符串中。最后把剩余的字符直接追加到结果字符串中。

时间复杂度 $O(m+n)$，空间复杂度 $O(m)$。其中 $m$ 和 $n$ 分别是字符串 $order$ 和 $s$ 的长度。

func customSortString(order string, s string) string {
	cnt := [26]int{}
	for _, c := range s {
		cnt[c-'a']++
	}
	ans := []rune{}
	for _, c := range order {
		for cnt[c-'a'] > 0 {
			ans = append(ans, c)
			cnt[c-'a']--
		}
	}
	for i, v := range cnt {
		for j := 0; j < v; j++ {
			ans = append(ans, rune('a'+i))
		}
	}
	return string(ans)
}

力扣原题 · Doocs 题解来源

804. 唯一摩尔斯密码词

简单1 种解法

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

题目、示例与约束

国际摩尔斯密码定义一种标准编码方式，将每个字母对应于一个由一系列点和短线组成的字符串， 比如:

• 'a' 对应 ".-" ，
• 'b' 对应 "-..." ，
• 'c' 对应 "-.-." ，以此类推。

为了方便，所有 26 个英文字母的摩尔斯密码表如下：

[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]

给你一个字符串数组 words ，每个单词可以写成每个字母对应摩尔斯密码的组合。

• 例如，"cab" 可以写成 "-.-..--..." ，(即 "-.-." + ".-" + "-..." 字符串的结合)。我们将这样一个连接过程称作 单词翻译 。

对 words 中所有单词进行单词翻译，返回不同 单词翻译 的数量。

 

示例 1：

输入: words = ["gin", "zen", "gig", "msg"]
输出: 2
解释: 
各单词翻译如下:
"gin" -> "--...-."
"zen" -> "--...-."
"gig" -> "--...--."
"msg" -> "--...--."

共有 2 种不同翻译, "--...-." 和 "--...--.".

示例 2：

输入：words = ["a"]
输出：1

 

提示：

• 1 <= words.length <= 100
• 1 <= words[i].length <= 12
• words[i] 由小写英文字母组成

方法一：哈希表 · Go 实现

思考

每个单词按字母表映射成摩尔斯串后，需要统计有多少种不同编码。 $words$ 至多 $100$ 个、长度不超过 $12$，直接变换即可。

用集合存放变换结果，最后取集合大小。无需比较原词，编码相同即视为同一种变换。

将 words 所有单词翻译成对应的摩尔斯密码，加入到哈希表中，最后返回哈希表的 size。

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

func uniqueMorseRepresentations(words []string) int {
	codes := []string{".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--", "-.",
		"---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.."}
	s := make(map[string]bool)
	for _, word := range words {
		t := &strings.Builder{}
		for _, c := range word {
			t.WriteString(codes[c-'a'])
		}
		s[t.String()] = true
	}
	return len(s)
}

力扣原题 · Doocs 题解来源

811. 子域名访问计数

中等1 种解法

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

题目、示例与约束

网站域名 "discuss.leetcode.com" 由多个子域名组成。顶级域名为 "com" ，二级域名为 "leetcode.com" ，最低一级为 "discuss.leetcode.com" 。当访问域名 "discuss.leetcode.com" 时，同时也会隐式访问其父域名 "leetcode.com" 以及 "com" 。

计数配对域名 是遵循 "rep d1.d2.d3" 或 "rep d1.d2" 格式的一个域名表示，其中 rep 表示访问域名的次数，d1.d2.d3 为域名本身。

• 例如，"9001 discuss.leetcode.com" 就是一个 计数配对域名 ，表示 discuss.leetcode.com 被访问了 9001 次。

给你一个 计数配对域名 组成的数组 cpdomains ，解析得到输入中每个子域名对应的 计数配对域名 ，并以数组形式返回。可以按 任意顺序 返回答案。

 

示例 1：

输入：cpdomains = ["9001 discuss.leetcode.com"]
输出：["9001 leetcode.com","9001 discuss.leetcode.com","9001 com"]
解释：例子中仅包含一个网站域名："discuss.leetcode.com"。
按照前文描述，子域名 "leetcode.com" 和 "com" 都会被访问，所以它们都被访问了 9001 次。

示例 2：

输入：cpdomains = ["900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"]
输出：["901 mail.com","50 yahoo.com","900 google.mail.com","5 wiki.org","5 org","1 intel.mail.com","951 com"]
解释：按照前文描述，会访问 "google.mail.com" 900 次，"yahoo.com" 50 次，"intel.mail.com" 1 次，"wiki.org" 5 次。
而对于父域名，会访问 "mail.com" 900 + 1 = 901 次，"com" 900 + 50 + 1 = 951 次，和 "org" 5 次。

 

提示：

• 1 <= cpdomain.length <= 100
• 1 <= cpdomain[i].length <= 100
• cpdomain[i] 会遵循 "repi d1i.d2i.d3i" 或 "repi d1i.d2i" 格式
• repi 是范围 [1, 104] 内的一个整数
• d1i、d2i 和 d3i 由小写英文字母组成

方法一：哈希表 · Go 实现

思考

一条计数记录要同时累加到自身及其所有上级域名。记录条数与串长均不超过 $100$，按点号拆分即可。

扫描每个空格或点号后的后缀，把访问次数加到该后缀上，最后把计数表格式化输出。

我们用哈希表 cnt 存储每个域名（子域名）对应的访问次数。

然后遍历数组，对于每个域名，我们将其拆分为子域名，然后更新哈希表 cnt 中对应的访问次数。

最后，我们将哈希表中的键值对转换为数组，即可得到答案。

时间复杂度 $O(L)$，空间复杂度 $O(L)$。其中 $L$ 是数组 cpdomains 中所有域名的长度之和。

func subdomainVisits(cpdomains []string) []string {
	cnt := map[string]int{}
	for _, s := range cpdomains {
		i := strings.IndexByte(s, ' ')
		v, _ := strconv.Atoi(s[:i])
		for ; i < len(s); i++ {
			if s[i] == ' ' || s[i] == '.' {
				cnt[s[i+1:]] += v
			}
		}
	}
	ans := make([]string, 0, len(cnt))
	for s, v := range cnt {
		ans = append(ans, strconv.Itoa(v)+" "+s)
	}
	return ans
}

力扣原题 · Doocs 题解来源

819. 最常见的单词

简单1 种解法

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

题目、示例与约束

给你一个字符串 paragraph 和一个表示禁用词的字符串数组 banned ，返回出现频率最高的非禁用词。题目数据 保证 至少存在一个非禁用词，且答案 唯一 。

paragraph 中的单词 不区分大小写 ，答案应以 小写 形式返回。

注意 单词不包含标点符号。

 

示例 1：

输入：paragraph = "Bob hit a ball, the hit BALL flew far after it was hit.", banned = ["hit"]
输出："ball"
解释：
"hit" 出现了 3 次，但它是禁用词。
"ball" 出现了两次（没有其他单词出现这么多次），因此它是段落中出现频率最高的非禁用词。
请注意，段落中的单词不区分大小写，
标点符号会被忽略（即使它们紧挨着单词，如 "ball,"），
并且尽管 "hit" 出现的次数更多，但它不能作为答案，因为它是禁用词。

示例 2：

输入：paragraph = "a.", banned = []
输出："a"

 

提示：

• 1 <= paragraph.length <= 1000
• paragraph 由英文字母、空格 ' '、和以下符号组成："!?',;."
• 0 <= banned.length <= 100
• 1 <= banned[i].length <= 10
• banned[i] 仅由小写英文字母组成

方法一：正则匹配/双指针 + 哈希表 · Go 实现

思考

要在段落中统计单词频率并排除禁用表，同时标点视为分隔符。段落长度 $\le 1000$，先规范化再计数即可。

将段落转小写后用正则取出连续字母作为单词，计数后按频率从高到低跳过禁用词，返回第一个合法单词。

正则匹配（或双指针）找出所有单词，用哈希表统计每个单词出现的频率，找到出现未在 banned 中出现且频率最大的单词。

func mostCommonWord(paragraph string, banned []string) string {
	s := make(map[string]bool)
	for _, w := range banned {
		s[w] = true
	}
	counter := make(map[string]int)
	var ans string
	for i, mx, n := 0, 0, len(paragraph); i < n; {
		if !unicode.IsLetter(rune(paragraph[i])) {
			i++
			continue
		}
		j := i
		var word []byte
		for j < n && unicode.IsLetter(rune(paragraph[j])) {
			word = append(word, byte(unicode.ToLower(rune(paragraph[j]))))
			j++
		}
		i = j + 1
		t := string(word)
		if s[t] {
			continue
		}
		counter[t]++
		if counter[t] > mx {
			ans = t
			mx = counter[t]
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

822. 翻转卡片游戏

中等1 种解法

标签：数组、哈希表

题目、示例与约束

在桌子上有 n 张卡片，每张卡片的正面和背面都写着一个正数（正面与背面上的数有可能不一样）。

我们可以先翻转任意张卡片，然后选择其中一张卡片。

如果选中的那张卡片背面的数字 x 与任意一张卡片的正面的数字都不同，那么这个数字是我们想要的数字。

哪个数是这些想要的数字中最小的数（找到这些数中的最小值）呢？如果没有一个数字符合要求的，输出 0 。

其中, fronts[i] 和 backs[i] 分别代表第 i 张卡片的正面和背面的数字。

如果我们通过翻转卡片来交换正面与背面上的数，那么当初在正面的数就变成背面的数，背面的数就变成正面的数。

 

示例 1：

输入：fronts = [1,2,4,4,7], backs = [1,3,4,1,3]
输出：2
解释：假设我们翻转第二张卡片，那么在正面的数变成了 [1,3,4,4,7] ， 背面的数变成了 [1,2,4,1,3]。
接着我们选择第二张卡片，因为现在该卡片的背面的数是 2，2 与任意卡片上正面的数都不同，所以 2 就是我们想要的数字。

示例 2：

输入：fronts = [1], backs = [1]
输出：0
解释：
无论如何翻转都无法得到想要的数字，所以返回 0 。

 

提示：

• n == fronts.length == backs.length
• 1 <= n <= 1000
• 1 <= fronts[i], backs[i] <= 2000

方法一：哈希表 · Go 实现

思考

翻牌后正面朝上的数若在某张牌的正反面同时出现，则该数不可能成为答案。 $n\le 1000$，先找出所有正反相同的数，它们永远不能作为最终正面。

在其余出现过的数字中取最小者；若没有合法数字则返回 $0$。

我们注意到，对于位置 $i$，若 $\mathit{\text{fronts}}[i]$ 与 $\mathit{\text{backs}}[i]$ 元素相同，则一定不满足条件。

因此，我们先找出正面与背面相同的元素，记录在哈希表 $s$ 中。

接下来，遍历正面与背面的元素，若元素 $x$ 不在哈希表 $s$ 中，则更新答案的最小值。

最后，若找到一个满足条件的元素，返回答案，否则返回 $0$。

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

func flipgame(fronts []int, backs []int) int {
	s := map[int]struct{}{}
	for i, a := range fronts {
		if a == backs[i] {
			s[a] = struct{}{}
		}
	}
	ans := 9999
	for _, v := range fronts {
		if _, ok := s[v]; !ok {
			ans = min(ans, v)
		}
	}
	for _, v := range backs {
		if _, ok := s[v]; !ok {
			ans = min(ans, v)
		}
	}
	return ans % 9999
}

力扣原题 · Doocs 题解来源

833. 字符串中的查找与替换

中等1 种解法

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

题目、示例与约束

你会得到一个字符串 s (索引从 0 开始)，你必须对它执行 k 个替换操作。替换操作以三个长度均为 k 的并行数组给出：indices, sources,  targets。

要完成第 i 个替换操作:

1. 检查 子字符串  sources[i] 是否出现在 原字符串 s 的索引 indices[i] 处。
2. 如果没有出现， 什么也不做 。
3. 如果出现，则用 targets[i] 替换 该子字符串。

例如，如果 s = "abcd" ， indices[i] = 0 , sources[i] = "ab"， targets[i] = "eee" ，那么替换的结果将是 "eeecd" 。

所有替换操作必须 同时 发生，这意味着替换操作不应该影响彼此的索引。测试用例保证元素间不会重叠 。

• 例如，一个 s = "abc" ，  indices = [0,1] ， sources = ["ab"，"bc"] 的测试用例将不会生成，因为 "ab" 和 "bc" 替换重叠。

在对 s 执行所有替换操作后返回 结果字符串 。

子字符串 是字符串中连续的字符序列。

 

示例 1：

输入：s = "abcd", indices = [0,2], sources = ["a","cd"], targets = ["eee","ffff"]
输出："eeebffff"
解释：
"a" 从 s 中的索引 0 开始，所以它被替换为 "eee"。
"cd" 从 s 中的索引 2 开始，所以它被替换为 "ffff"。

示例 2：

输入：s = "abcd", indices = [0,2], sources = ["ab","ec"], targets = ["eee","ffff"]
输出："eeecd"
解释：
"ab" 从 s 中的索引 0 开始，所以它被替换为 "eee"。
"ec" 没有从原始的 S 中的索引 2 开始，所以它没有被替换。

 

提示：

• 1 <= s.length <= 1000
• k == indices.length == sources.length == targets.length
• 1 <= k <= 100
• 0 <= indices[i] < s.length
• 1 <= sources[i].length, targets[i].length <= 50
• s 仅由小写英文字母组成
• sources[i] 和 targets[i] 仅由小写英文字母组成

方法一：模拟 · Go 实现

思考

多组替换同时生效，且只有 $\mathit{\text{source}}$ 与 $s$ 在给定下标精确匹配才替换。从左扫描时若立即改写，后续下标会错位。

先在原串下标上标记哪些位置匹配成功，再从左到右拼接：命中则写入 $\mathit{\text{target}}$ 并跳过 $\mathit{\text{source}}$ 长度，否则抄原字符。

我们遍历每个替换操作，对于当前第 $k$ 个替换操作 $(i,\text{src})$，如果 $s[i..i+|\text{src}|-1]$ 与 $\text{src}$ 相等，此时我们记录下标 $i$ 处需要替换的是 $\text{targets}$ 的第 $k$ 个字符串，否则不需要替换。

接下来，我们只需要遍历原字符串 $s$，根据记录的信息进行替换即可。

时间复杂度 $O(L)$，空间复杂度 $O(n)$。其中 $L$ 是所有字符串的长度之和，而 $n$ 是字符串 $s$ 的长度。

func findReplaceString(s string, indices []int, sources []string, targets []string) string {
	n := len(s)
	d := make([]int, n)
	for k, i := range indices {
		if strings.HasPrefix(s[i:], sources[k]) {
			d[i] = k + 1
		}
	}
	ans := &strings.Builder{}
	for i := 0; i < n; {
		if d[i] > 0 {
			ans.WriteString(targets[d[i]-1])
			i += len(sources[d[i]-1])
		} else {
			ans.WriteByte(s[i])
			i++
		}
	}
	return ans.String()
}

力扣原题 · Doocs 题解来源

859. 亲密字符串

简单1 种解法

标签：哈希表、字符串

题目、示例与约束

给你两个字符串 s 和 goal ，只要我们可以通过交换 s 中的两个字母得到与 goal 相等的结果，就返回 true ；否则返回 false 。

交换字母的定义是：取两个下标 i 和 j （下标从 0 开始）且满足 i != j ，接着交换 s[i] 和 s[j] 处的字符。

• 例如，在 "abcd" 中交换下标 0 和下标 2 的元素可以生成 "cbad" 。

 

示例 1：

输入：s = "ab", goal = "ba"
输出：true
解释：你可以交换 s[0] = 'a' 和 s[1] = 'b' 生成 "ba"，此时 s 和 goal 相等。

示例 2：

输入：s = "ab", goal = "ab"
输出：false
解释：你只能交换 s[0] = 'a' 和 s[1] = 'b' 生成 "ba"，此时 s 和 goal 不相等。

示例 3：

输入：s = "aa", goal = "aa"
输出：true
解释：你可以交换 s[0] = 'a' 和 s[1] = 'a' 生成 "aa"，此时 s 和 goal 相等。

 

提示：

• 1 <= s.length, goal.length <= 2 * 104
• s 和 goal 由小写英文字母组成

方法一：字符统计 · Go 实现

思考

恰好交换 $s$ 中两个字符后等于 $\mathit{\text{goal}}$。长度不同或字母计数不同则不可能。 $n\le 2\cdot {10}^4$，一次扫描数出不同位置即可。

不同位置恰为 $2$ 时，交换这两处即可（计数已保证字母可对齐）。完全相同则需要某个字母出现至少两次，才能做一次无效果交换。

首先，先理解亲密字符串的意思：

• 若两个字符串的长度或字符出现的频数不等，一定不是亲密字符串；
• 若两个字符串对应位置不相等的字符数量为 2，或者数量为 0 并且字符串存在两个相同字符，则是亲密字符串。

因此，我们先判断两个字符串长度，若不等，直接返回 false。

接着，统计两个字符串的字符频数，记为 cnt1 和 cnt2，若 cnt1 不等于 cnt2，直接返回 false。

然后枚举两个字符串，统计对应位置不相等的字符数量，若为 2，则返回 true；若为 0，且字符串存在两个相同字符，则返回 true。

时间复杂度 $O(n)$，空间复杂度 $O(C)$。其中 $n$ 是字符串 s 或 goal 的长度；而 $C$ 为字符集大小。

func buddyStrings(s string, goal string) bool {
	m, n := len(s), len(goal)
	if m != n {
		return false
	}
	diff := 0
	cnt1 := make([]int, 26)
	cnt2 := make([]int, 26)
	for i := 0; i < n; i++ {
		cnt1[s[i]-'a']++
		cnt2[goal[i]-'a']++
		if s[i] != goal[i] {
			diff++
		}
	}
	f := false
	for i := 0; i < 26; i++ {
		if cnt1[i] != cnt2[i] {
			return false
		}
		if cnt1[i] > 1 {
			f = true
		}
	}
	return diff == 2 || (diff == 0 && f)
}

力扣原题 · Doocs 题解来源

874. 模拟行走机器人

中等1 种解法

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

题目、示例与约束

机器人在一个无限大小的 XY 网格平面上行走，从点 (0, 0) 处开始出发，面向北方。该机器人可以接收以下三种类型的命令 commands ：

• -2 ：向左转 90 度
• -1 ：向右转 90 度
• 1 <= x <= 9 ：向前移动 x 个单位长度

在网格上有一些格子被视为障碍物 obstacles 。第 i 个障碍物位于网格点  obstacles[i] = (xi, yi) 。

机器人无法走到障碍物上，它将会停留在障碍物的前一个网格方块上，并继续执行下一个命令。

返回机器人距离原点的 最大欧式距离 的 平方 。（即，如果距离为 5 ，则返回 25 ）

 

注意：

• 北方表示 +Y 方向。
• 东方表示 +X 方向。
• 南方表示 -Y 方向。
• 西方表示 -X 方向。
• 原点 [0,0] 可能会有障碍物。

 

示例 1：

输入：commands = [4,-1,3], obstacles = []
输出：25
解释：
机器人开始位于 (0, 0)：
1. 向北移动 4 个单位，到达 (0, 4)
2. 右转
3. 向东移动 3 个单位，到达 (3, 4)
距离原点最远的是 (3, 4) ，距离为 32 + 42 = 25

示例 2：

输入：commands = [4,-1,4,-2,4], obstacles = [[2,4]]
输出：65
解释：机器人开始位于 (0, 0)：
1. 向北移动 4 个单位，到达 (0, 4)
2. 右转
3. 向东移动 1 个单位，然后被位于 (2, 4) 的障碍物阻挡，机器人停在 (1, 4)
4. 左转
5. 向北走 4 个单位，到达 (1, 8)
距离原点最远的是 (1, 8) ，距离为 12 + 82 = 65

示例 3：

输入：commands = [6,-1,-1,6], obstacles = []
输出：36
解释：机器人开始位于 (0, 0):
1. 向北移动 6 个单位，到达 (0, 6).
2. 右转
3. 右转
4. 向南移动 6 个单位，到达 (0, 0).
机器人距离原点最远的点是 (0, 6)，其距离的平方是 62 = 36 个单位。

提示：

• 1 <= commands.length <= 104
• commands[i] 的值可以取 -2、-1 或者是范围 [1, 9] 内的一个整数。
• 0 <= obstacles.length <= 104
• -3 * 104 <= xi, yi <= 3 * 104
• 答案保证小于 231

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

思考

机器人按指令转向或前进，障碍物挡住一步则停在原地。指令与障碍均 $\le {10}^4$，逐步模拟即可，但障碍查询必须 $O(1)$。

障碍放入集合，方向用循环数组。前进时每一步先看下一格是否在集合中，更新最远欧氏距离平方。

我们定义一个长度为 $5$ 的方向数组 $dirs=[0,1,0,-1,0]$，数组中的相邻两个元素表示一个方向。即 $(dirs[0],dirs[1])$ 表示向北，而 $(dirs[1],dirs[2])$ 表示向东，以此类推。

我们使用一个哈希表 $s$ 来存储所有障碍物的坐标，这样可以在 $O(1)$ 的时间内判断下一步是否会遇到障碍物。

另外，使用两个变量 $x$ 和 $y$ 来表示机器人当前所在的坐标，初始时 $x=y=0$。变量 $k$ 表示机器人当前的方向，答案变量 $ans$ 表示机器人距离原点的最大欧式距离的平方。

接下来，我们遍历数组 $commands$ 中的每个元素 $c$：

• 如果 $c=-2$，表示机器人向左转 $90$ 度，即 $k=(k+3)mod4$；
• 如果 $c=-1$，表示机器人向右转 $90$ 度，即 $k=(k+1)mod4$；
• 否则，表示机器人向前移动 $c$ 个单位长度。我们将机器人当前的方向 $k$ 与方向数组 $dirs$ 结合，即可得到机器人在 $x$ 轴和 $y$ 轴上的增量。我们将 $c$ 个单位长度的增量分别累加到 $x$ 和 $y$ 上，并判断每次移动后的新坐标 $(nx,ny)$ 是否在障碍物的坐标中，如果不在，则更新答案 $ans$，否则停止模拟，进行下一条指令的模拟。

最后返回答案 $ans$ 即可。

时间复杂度 $O(C\times n+m)$，空间复杂度 $O(m)$。其中 $C$ 表示每次可以移动的最大步数，而 $n$ 和 $m$ 分别表示数组 $commands$ 和数组 $obstacles$ 的长度。

func robotSim(commands []int, obstacles [][]int) (ans int) {
	dirs := [5]int{0, 1, 0, -1, 0}
	type pair struct{ x, y int }
	s := map[pair]bool{}
	for _, e := range obstacles {
		s[pair{e[0], e[1]}] = true
	}
	var x, y, k int
	for _, c := range commands {
		if c == -2 {
			k = (k + 3) % 4
		} else if c == -1 {
			k = (k + 1) % 4
		} else {
			for ; c > 0 && !s[pair{x + dirs[k], y + dirs[k+1]}]; c-- {
				x += dirs[k]
				y += dirs[k+1]
				ans = max(ans, x*x+y*y)
			}
		}
	}
	return
}

力扣原题 · Doocs 题解来源

884. 两句话中的不常见单词

简单1 种解法

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

题目、示例与约束

句子 是一串由空格分隔的单词。每个 单词 仅由小写字母组成。

如果某个单词在其中一个句子中恰好出现一次，在另一个句子中却 没有出现 ，那么这个单词就是 不常见的 。

给你两个 句子 s1 和 s2 ，返回所有 不常用单词 的列表。返回列表中单词可以按 任意顺序 组织。

 

示例 1：

输入：s1 = "this apple is sweet", s2 = "this apple is sour"
输出：["sweet","sour"]

示例 2：

输入：s1 = "apple apple", s2 = "banana"
输出：["banana"]

 

提示：

• 1 <= s1.length, s2.length <= 200
• s1 和 s2 由小写英文字母和空格组成
• s1 和 s2 都不含前导或尾随空格
• s1 和 s2 中的所有单词间均由单个空格分隔

方法一：哈希表 · Go 实现

思考

只在一句中出现一次、且另一句中不出现的单词。句子很短，合并计数后筛出频次为 $1$ 的词即可。

两句拆词后加到同一个计数器，值为 $1$ 的键即答案。

根据题目描述，只要单词出现一次，就符合题目要求。因此，我们用哈希表 $cnt$ 记录所有单词以及出现的次数。

然后遍历哈希表，取出所有出现次数为 $1$ 的字符串即可。

时间复杂度 $O(m+n)$，空间复杂度 $O(m+n)$。其中 $m$ 和 $n$ 分别是字符串 $s1$ 和 $s2$ 的长度。

func uncommonFromSentences(s1 string, s2 string) (ans []string) {
	cnt := map[string]int{}
	for _, s := range strings.Split(s1, " ") {
		cnt[s]++
	}
	for _, s := range strings.Split(s2, " ") {
		cnt[s]++
	}
	for s, v := range cnt {
		if v == 1 {
			ans = append(ans, s)
		}
	}
	return
}

力扣原题 · Doocs 题解来源

890. 查找和替换模式

中等1 种解法

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

题目、示例与约束

你有一个单词列表 words 和一个模式  pattern，你想知道 words 中的哪些单词与模式匹配。

如果存在字母的排列 p ，使得将模式中的每个字母 x 替换为 p(x) 之后，我们就得到了所需的单词，那么单词与模式是匹配的。

（回想一下，字母的排列是从字母到字母的双射：每个字母映射到另一个字母，没有两个字母映射到同一个字母。）

返回 words 中与给定模式匹配的单词列表。

你可以按任何顺序返回答案。

 

示例：

输入：words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
输出：["mee","aqq"]
解释：
"mee" 与模式匹配，因为存在排列 {a -> m, b -> e, ...}。
"ccc" 与模式不匹配，因为 {a -> c, b -> c, ...} 不是排列。
因为 a 和 b 映射到同一个字母。

 

提示：

• 1 <= pattern.length <= 20
• 1 <= words.length <= 50
• words[i].length == pattern.length
• pattern 和 words[i] 只包含小写英文字母。

方法一：哈希表 · Go 实现

思考

判断单词与模式是否存在双射。词数与长度都很小，对每个词做一次映射检查即可。

同步扫描两串，用两个数组记下字母首次绑定的位置编号；编号不同则不是同一映射。双向同时记录可避免多对一。

func findAndReplacePattern(words []string, pattern string) []string {
	match := func(s, t string) bool {
		m1, m2 := make([]int, 128), make([]int, 128)
		for i := 0; i < len(s); i++ {
			if m1[s[i]] != m2[t[i]] {
				return false
			}
			m1[s[i]] = i + 1
			m2[t[i]] = i + 1
		}
		return true
	}
	var ans []string
	for _, word := range words {
		if match(word, pattern) {
			ans = append(ans, word)
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

893. 特殊等价字符串组

中等1 种解法

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

题目、示例与约束

给你一个字符串数组 words。

一步操作中，你可以交换字符串 words[i] 的任意两个偶数下标对应的字符或任意两个奇数下标对应的字符。

对两个字符串 words[i] 和 words[j] 而言，如果经过任意次数的操作，words[i] == words[j] ，那么这两个字符串是 特殊等价 的。

• 例如，words[i] = "zzxy" 和 words[j] = "xyzz" 是一对 特殊等价 字符串，因为可以按 "zzxy" -> "xzzy" -> "xyzz" 的操作路径使 words[i] == words[j] 。

现在规定，words 的 一组特殊等价字符串 就是 words 的一个同时满足下述条件的非空子集：

• 该组中的每一对字符串都是 特殊等价 的
• 该组字符串已经涵盖了该类别中的所有特殊等价字符串，容量达到理论上的最大值（也就是说，如果一个字符串不在该组中，那么这个字符串就 不会 与该组内任何字符串特殊等价）

返回 words 中 特殊等价字符串组 的数量。

 

示例 1：

输入：words = ["abcd","cdab","cbad","xyzz","zzxy","zzyx"]
输出：3
解释：
其中一组为 ["abcd", "cdab", "cbad"]，因为它们是成对的特殊等价字符串，且没有其他字符串与这些字符串特殊等价。
另外两组分别是 ["xyzz", "zzxy"] 和 ["zzyx"]。特别需要注意的是，"zzxy" 不与 "zzyx" 特殊等价。

示例 2：

输入：words = ["abc","acb","bac","bca","cab","cba"]
输出：3
解释：3 组 ["abc","cba"]，["acb","bca"]，["bac","cab"]

 

提示：

• 1 <= words.length <= 1000
• 1 <= words[i].length <= 20
• 所有 words[i] 都只由小写字母组成。
• 所有 words[i] 都具有相同的长度。

方法一 · Go 实现

思考

奇数位与偶数位可分别任意重排，等价类由这两套字母的可重集合决定。词数 $\le 1000$、长度 $\le 20$，规范化后放入集合即可。

对每个词把偶位、奇位分别排序再拼接，作为签名。不同签名的个数即组数。

func numSpecialEquivGroups(words []string) int {
	s := map[string]bool{}
	for _, word := range words {
		a, b := []rune{}, []rune{}
		for i, c := range word {
			if i&1 == 1 {
				a = append(a, c)
			} else {
				b = append(b, c)
			}
		}
		sort.Slice(a, func(i, j int) bool {
			return a[i] < a[j]
		})
		sort.Slice(b, func(i, j int) bool {
			return b[i] < b[j]
		})
		s[string(a)+string(b)] = true
	}
	return len(s)
}

力扣原题 · Doocs 题解来源

916. 单词子集

中等1 种解法

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

题目、示例与约束

给你两个字符串数组 words1 和 words2。

现在，如果 b 中的每个字母都出现在 a 中，包括重复出现的字母，那么称字符串 b 是字符串 a 的 子集 。

• 例如，"wrr" 是 "warrior" 的子集，但不是 "world" 的子集。

如果对 words2 中的每一个单词 b，b 都是 a 的子集，那么我们称 words1 中的单词 a 是 通用单词 。

以数组形式返回 words1 中所有的 通用 单词。你可以按 任意顺序 返回答案。

 

示例 1：

输入：words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["e","o"]

输出：["facebook","google","leetcode"]

示例 2：

输入：words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["lc","eo"]

输出：["leetcode"]

示例 3：

输入：words1 = ["acaac","cccbb","aacbb","caacc","bcbbb"], words2 = ["c","cc","b"]

输出：["cccbb"]

 

提示：

• 1 <= words1.length, words2.length <= 104
• 1 <= words1[i].length, words2[i].length <= 10
• words1[i] 和 words2[i] 仅由小写英文字母组成
• words1 中的所有字符串 互不相同

方法一：计数 · Go 实现

思考

$a$ 要覆盖 $words2$ 中每一个词的字母需求。对每个 $a$ 逐个检查每个 $b$ 仍可，但 $b$ 之间的约束可以合并：每个字母取 $words2$ 中的最大需求，得到一份总约束 $\mathit{\text{cnt}}$，再对 $a$ 做一次计数比较即可。

遍历 words2 中的每个单词 b，统计每个字母出现的最大次数，记为 cnt。

然后遍历 words1 中的每个单词 a，统计每个字母出现的次数，记为 t。如果 cnt 中的每个字母的出现次数都不大于 t 中的出现次数，则 a 是通用单词，将其加入答案。

时间复杂度 $O(L)$，其中 $L$ 为 words1 和 words2 中所有单词的长度之和。

func wordSubsets(words1 []string, words2 []string) (ans []string) {
	cnt := [26]int{}
	for _, b := range words2 {
		t := [26]int{}
		for _, c := range b {
			t[c-'a']++
		}
		for i := range cnt {
			cnt[i] = max(cnt[i], t[i])
		}
	}
	for _, a := range words1 {
		t := [26]int{}
		for _, c := range a {
			t[c-'a']++
		}
		ok := true
		for i, v := range cnt {
			if v > t[i] {
				ok = false
				break
			}
		}
		if ok {
			ans = append(ans, a)
		}
	}
	return
}

力扣原题 · Doocs 题解来源

929. 独特的电子邮件地址

简单1 种解法

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

题目、示例与约束

每个 有效电子邮件地址 都由一个 本地名 和一个 域名 组成，以 '@' 符号分隔。除小写字母之外，电子邮件地址还可以含有一个或多个 '.' 或 '+' 。

• 例如，在 alice@leetcode.com中， alice 是 本地名 ，而 leetcode.com 是 域名 。

如果在电子邮件地址的 本地名 部分中的某些字符之间添加句点（'.'），则发往那里的邮件将会转发到本地名中没有点的同一地址。请注意，此规则 不适用于域名 。

• 例如，"alice.z@leetcode.com” 和 “alicez@leetcode.com” 会转发到同一电子邮件地址。

如果在 本地名 中添加加号（'+'），则会忽略第一个加号后面的所有内容。这允许过滤某些电子邮件。同样，此规则 不适用于域名 。

• 例如 m.y+name@email.com 将转发到 my@email.com。

可以同时使用这两个规则。

给你一个字符串数组 emails，我们会向每个 emails[i] 发送一封电子邮件。返回实际收到邮件的不同地址数目。

 

示例 1：

输入：emails = ["test.email+alex@leetcode.com","test.e.mail+bob.cathy@leetcode.com","testemail+david@lee.tcode.com"]
输出：2
解释：实际收到邮件的是 "testemail@leetcode.com" 和 "testemail@lee.tcode.com"。

示例 2：

输入：emails = ["a@leetcode.com","b@leetcode.com","c@leetcode.com"]
输出：3

提示：

• 1 <= emails.length <= 100
• 1 <= emails[i].length <= 100
• emails[i] 由小写英文字母、'+'、'.' 和 '@' 组成
• 每个 emails[i] 都包含有且仅有一个 '@' 字符
• 所有本地名和域名都不为空
• 本地名不会以 '+' 字符作为开头
• 域名以 ".com" 后缀结尾。
• 域名在 ".com" 后缀前至少包含一个字符

方法一：哈希表 · Go 实现

思考

规则只作用于 @ 左侧：忽略 .，并丢掉第一个 + 及其后内容。规范化后相同的地址应只计一次。对每个邮箱按规则改写本地名，再与域名拼回，放入集合，集合大小即为答案。

我们可以用一个哈希表 $s$ 来存储所有的电子邮件地址，然后遍历数组 $\mathit{\text{emails}}$，对于每个电子邮件地址，我们将其分为本地名和域名两部分，然后对本地名进行处理，去掉所有的点号和加号后面的字符，最后将处理后的本地名和域名拼接起来，加入哈希表 $s$ 中。

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

时间复杂度 $O(L)$，空间复杂度 $O(L)$，其中 $L$ 为所有电子邮件地址的长度之和。

func numUniqueEmails(emails []string) int {
	s := make(map[string]struct{})
	for _, email := range emails {
		parts := strings.Split(email, "@")
		local := parts[0]
		domain := parts[1]
		var t strings.Builder
		for _, c := range local {
			if c == '.' {
				continue
			}
			if c == '+' {
				break
			}
			t.WriteByte(byte(c))
		}
		s[t.String()+"@"+domain] = struct{}{}
	}
	return len(s)
}

力扣原题 · Doocs 题解来源

953. 验证外星语词典

简单1 种解法

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

题目、示例与约束

某种外星语也使用英文小写字母，但可能顺序 order 不同。字母表的顺序（order）是一些小写字母的排列。

给定一组用外星语书写的单词 words，以及其字母表的顺序 order，只有当给定的单词在这种外星语中按字典序排列时，返回 true；否则，返回 false。

 

示例 1：

输入：words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
输出：true
解释：在该语言的字母表中，'h' 位于 'l' 之前，所以单词序列是按字典序排列的。

示例 2：

输入：words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"
输出：false
解释：在该语言的字母表中，'d' 位于 'l' 之后，那么 words[0] > words[1]，因此单词序列不是按字典序排列的。

示例 3：

输入：words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"
输出：false
解释：当前三个字符 "app" 匹配时，第二个字符串相对短一些，然后根据词典编纂规则 "apple" > "app"，因为 'l' > '∅'，其中 '∅' 是空白字符，定义为比任何其他字符都小（更多信息）。

 

提示：

• 1 <= words.length <= 100
• 1 <= words[i].length <= 20
• order.length == 26
• 在 words[i] 和 order 中的所有字符都是英文小写字母。

方法一 · Go 实现

思考

按外星字母序判断单词是否非降。逐对比较相邻词当然可以，按位扫描也能一次判定：第 $i$ 位的外星序必须非降，且较短词在该位视为更小。若某一列所有相邻位都严格上升，则后续列不必再看。

func isAlienSorted(words []string, order string) bool {
	m := make([]int, 26)
	for i, c := range order {
		m[c-'a'] = i
	}
	for i := 0; i < 20; i++ {
		prev := -1
		valid := true
		for _, x := range words {
			curr := -1
			if i < len(x) {
				curr = m[x[i]-'a']
			}
			if prev > curr {
				return false
			}
			if prev == curr {
				valid = false
			}
			prev = curr
		}
		if valid {
			break
		}
	}
	return true
}

力扣原题 · Doocs 题解来源

961. 在长度 2N 的数组中找出重复 N 次的元素

简单2 种解法

标签：数组、哈希表、抽屉原理

题目、示例与约束

给你一个整数数组 nums ，该数组具有以下属性：

• nums.length == 2 * n.
• nums 包含 n + 1 个 不同的 元素，其中 n 个值在数组中出现 恰好一次。
• nums 中恰有一个元素重复 n 次

找出并返回重复了 n 次的那个元素。

 

示例 1：

输入：nums = [1,2,3,3]
输出：3

示例 2：

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

示例 3：

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

 

提示：

• 2 <= n <= 5000
• nums.length == 2 * n
• 0 <= nums[i] <= 104
• nums 由 n + 1 个 不同的 元素组成，且其中一个元素恰好重复 n 次

方法一：哈希表 · Go 实现

思考

长度为 $2n$ 的数组中恰有一个元素出现 $n$ 次，其余各一次。第一次碰到已见过的值即为答案，用集合记录即可。

由于数组 $\mathit{\text{nums}}$ 一共有 $2n$ 个元素，其中有 $n+1$ 个不同的元素，且有一个元素重复了 $n$ 次，说明数组中的其余 $n$ 个元素都是不同的。

因此，我们只需要遍历数组 $\mathit{\text{nums}}$，用哈希表 $s$ 记录遍历过的元素。当遍历到某个元素 $x$ 时，如果 $x$ 在哈希表 $s$ 中已经存在，说明 $x$ 是重复的元素，直接返回 $x$ 即可。

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

func repeatedNTimes(nums []int) int {
	s := map[int]bool{}
	for i := 0; ; i++ {
		if s[nums[i]] {
			return nums[i]
		}
		s[nums[i]] = true
	}
}

方法二：数学 · Go 实现

思考

哈希需要线性空间。出现 $n$ 次的元素在环形意义下间隔至多为 $2$，故从下标 $2$ 起与前两项比较即可；若都不同，答案必为 $nums[0]$。

根据题目描述，数组 $\mathit{\text{nums}}$ 中有一半的元素都是相同的，如果我们将数组视为环形排列，那么两个相同元素之间的最多间隔 $1$ 个其他元素。

因此，我们从下标 $2$ 开始遍历数组 $\mathit{\text{nums}}$，对于每个下标 $i$，我们比较 $\mathit{\text{nums}}[i]$ 与 $\mathit{\text{nums}}[i-1]$ 和 $\mathit{\text{nums}}[i-2]$ 的值，如果相等则返回该值。

如果没有在上述过程中找到重复的元素，那么重复的元素一定是 $\mathit{\text{nums}}[0]$，我们直接返回 $\mathit{\text{nums}}[0]$ 即可。

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

func repeatedNTimes(nums []int) int {
	for i := 2; i < len(nums); i++ {
		if nums[i] == nums[i-1] || nums[i] == nums[i-2] {
			return nums[i]
		}
	}
	return nums[0]
}

力扣原题 · Doocs 题解来源

966. 元音拼写检查器

中等1 种解法

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

题目、示例与约束

在给定单词列表 wordlist 的情况下，我们希望实现一个拼写检查器，将查询单词转换为正确的单词。

对于给定的查询单词 query，拼写检查器将会处理两类拼写错误：

• 大小写：如果查询匹配单词列表中的某个单词（不区分大小写），则返回的正确单词与单词列表中的大小写相同。
  • 例如：wordlist = ["yellow"], query = "YellOw": correct = "yellow"
  • 例如：wordlist = ["Yellow"], query = "yellow": correct = "Yellow"
  • 例如：wordlist = ["yellow"], query = "yellow": correct = "yellow"
• 元音错误：如果在将查询单词中的元音 ('a', 'e', 'i', 'o', 'u')  分别替换为任何元音后，能与单词列表中的单词匹配（不区分大小写），则返回的正确单词与单词列表中的匹配项大小写相同。
  • 例如：wordlist = ["YellOw"], query = "yollow": correct = "YellOw"
  • 例如：wordlist = ["YellOw"], query = "yeellow": correct = "" （无匹配项）
  • 例如：wordlist = ["YellOw"], query = "yllw": correct = "" （无匹配项）

此外，拼写检查器还按照以下优先级规则操作：

• 当查询完全匹配单词列表中的某个单词（区分大小写）时，应返回相同的单词。
• 当查询匹配到大小写问题的单词时，您应该返回单词列表中的第一个这样的匹配项。
• 当查询匹配到元音错误的单词时，您应该返回单词列表中的第一个这样的匹配项。
• 如果该查询在单词列表中没有匹配项，则应返回空字符串。

给出一些查询 queries，返回一个单词列表 answer，其中 answer[i] 是由查询 query = queries[i] 得到的正确单词。

 

示例 1：

输入：wordlist = ["KiTe","kite","hare","Hare"], queries = ["kite","Kite","KiTe","Hare","HARE","Hear","hear","keti","keet","keto"]
输出：["kite","KiTe","KiTe","Hare","hare","","","KiTe","","KiTe"]

示例 2:

输入：wordlist = ["yellow"], queries = ["YellOw"]
输出：["yellow"]

 

提示：

• 1 <= wordlist.length, queries.length <= 5000
• 1 <= wordlist[i].length, queries[i].length <= 7
• wordlist[i] 和 queries[i] 只包含英文字母

方法一：哈希表 · Go 实现

思考

查询按“完全匹配、忽略大小写、元音视为相同”三级规则映射到词表，同级取词表中最先出现者。预处理三张表：原词集合、小写首次出现、元音替换为 * 后的首次出现。查询依次查三张表。

我们遍历 $\mathit{\text{wordlist}}$，将单词按照大小写不敏感、元音不敏感的规则分别存入哈希表 $\mathit{\text{low}}$ 和 $\mathit{\text{pat}}$ 中，其中 $\mathit{\text{low}}$ 的键为单词的小写形式， $\mathit{\text{pat}}$ 的键为将单词的元音字母替换为 * 后的字符串，值为单词本身。用哈希表 $\mathit{\text{s}}$ 存储 $\mathit{\text{wordlist}}$ 中的单词。

遍历 $\mathit{\text{queries}}$，对于每个单词 $\mathit{\text{q}}$，如果 $\mathit{\text{q}}$ 在 $\mathit{\text{s}}$ 中，说明 $\mathit{\text{q}}$ 在 $\mathit{\text{wordlist}}$ 中，直接将 $\mathit{\text{q}}$ 加入答案数组 $\mathit{\text{ans}}$ 中。

否则，如果 $\mathit{\text{q}}$ 的小写形式在 $\mathit{\text{low}}$ 中，说明 $\mathit{\text{q}}$ 在 $\mathit{\text{wordlist}}$ 中，且大小写不敏感，将 $\mathit{\text{low}}[q.\text{lower}()]$ 加入答案数组 $\mathit{\text{ans}}$ 中。

否则，如果将 $\mathit{\text{q}}$ 的元音字母替换为 * 后的字符串在 $\mathit{\text{pat}}$ 中，说明 $\mathit{\text{q}}$ 在 $\mathit{\text{wordlist}}$ 中，且元音不敏感，将 $\mathit{\text{pat}}[f(q)]$ 加入答案数组 $\mathit{\text{ans}}$ 中。

否则，说明 $\mathit{\text{q}}$ 在 $\mathit{\text{wordlist}}$ 中，且大小写和元音都不敏感，将空字符串加入答案数组 $\mathit{\text{ans}}$ 中。

最后返回答案数组 $\mathit{\text{ans}}$ 即可。

时间复杂度 $O(n+m)$，空间复杂度 $O(n)$。其中 $n$ 和 $m$ 分别为 $\mathit{\text{wordlist}}$ 和 $\mathit{\text{queries}}$ 的长度。

func spellchecker(wordlist []string, queries []string) (ans []string) {
	s := map[string]bool{}
	low := map[string]string{}
	pat := map[string]string{}
	f := func(w string) string {
		res := []byte(w)
		for i := range res {
			if res[i] == 'a' || res[i] == 'e' || res[i] == 'i' || res[i] == 'o' || res[i] == 'u' {
				res[i] = '*'
			}
		}
		return string(res)
	}
	for _, w := range wordlist {
		s[w] = true
		t := strings.ToLower(w)
		if _, ok := low[t]; !ok {
			low[t] = w
		}
		if _, ok := pat[f(t)]; !ok {
			pat[f(t)] = w
		}
	}
	for _, q := range queries {
		if s[q] {
			ans = append(ans, q)
			continue
		}
		q = strings.ToLower(q)
		if s, ok := low[q]; ok {
			ans = append(ans, s)
			continue
		}
		q = f(q)
		if s, ok := pat[q]; ok {
			ans = append(ans, s)
			continue
		}
		ans = append(ans, "")
	}
	return
}

力扣原题 · Doocs 题解来源

1001. 网格照明

困难1 种解法

标签：数组、哈希表

题目、示例与约束

在大小为 n x n 的网格 grid 上，每个单元格都有一盏灯，最初灯都处于 关闭 状态。

给你一个由灯的位置组成的二维数组 lamps ，其中 lamps[i] = [rowi, coli] 表示 打开 位于 grid[rowi][coli] 的灯。即便同一盏灯可能在 lamps 中多次列出，不会影响这盏灯处于 打开 状态。

当一盏灯处于打开状态，它将会照亮 自身所在单元格 以及同一 行 、同一 列 和两条 对角线 上的 所有其他单元格 。

另给你一个二维数组 queries ，其中 queries[j] = [rowj, colj] 。对于第 j 个查询，如果单元格 [rowj, colj] 是被照亮的，则查询结果为 1 ，否则为 0 。在第 j 次查询之后 [按照查询的顺序] ，关闭 位于单元格 grid[rowj][colj] 上及相邻 8 个方向上（与单元格 grid[rowi][coli] 共享角或边）的任何灯。

返回一个整数数组 ans 作为答案， ans[j] 应等于第 j 次查询 queries[j] 的结果，1 表示照亮，0 表示未照亮。

 

示例 1：

输入：n = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,0]]
输出：[1,0]
解释：最初所有灯都是关闭的。在执行查询之前，打开位于 [0, 0] 和 [4, 4] 的灯。第 0 次查询检查 grid[1][1] 是否被照亮（蓝色方框）。该单元格被照亮，所以 ans[0] = 1 。然后，关闭红色方框中的所有灯。

第 1 次查询检查 grid[1][0] 是否被照亮（蓝色方框）。该单元格没有被照亮，所以 ans[1] = 0 。然后，关闭红色矩形中的所有灯。

示例 2：

输入：n = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,1]]
输出：[1,1]

示例 3：

输入：n = 5, lamps = [[0,0],[0,4]], queries = [[0,4],[0,1],[1,4]]
输出：[1,1,0]

 

提示：

• 1 <= n <= 109
• 0 <= lamps.length <= 20000
• 0 <= queries.length <= 20000
• lamps[i].length == 2
• 0 <= rowi, coli < n
• queries[j].length == 2
• 0 <= rowj, colj < n

方法一：哈希表 · Go 实现

思考

网格边长 $n$ 可达 ${10}^9$，按格子模拟照明或关灯既无法建图也无法扫描。灯与查询各自至多 $2\times {10}^4$，真正有用的只是灯所在的行、列与两条对角线。

一盏位于 $(x,y)$ 的灯照亮整行 $x$、整列 $y$ 以及 $x-y$、 $x+y$ 两条斜线。查询点被照亮当且仅当这四条线之一上仍有灯；随后只需关闭该点及其八邻域中仍存在的灯，并同步减少对应直线上的计数。

因此用集合去重灯的坐标，再用四张哈希表维护每条直线上的灯数。每次查询先看四条线的计数是否为正，再在常数个邻格上更新集合与计数，复杂度与灯数、查询数线性相关，与 $n$ 无关。

假设一盏灯的坐标为 $(x,y)$，那么它所在的行的数值为 $x$，列的数值为 $y$，正对角线的数值为 $x-y$，反对角线的数值为 $x+y$。确定某一直线的唯一数值标识后，我们就可以通过哈希表来记录某一直线所拥有的灯的数目。

我们遍历数组 $\mathit{\text{lamps}}$，将当前遍历到的灯所在的行、列和正、反对角线拥有灯的数目分别加 $1$。

注意，在处理 $\mathit{\text{lamps}}$ 时，需要进行去重，因为我们将重复的灯看作同一盏灯。

接下来，我们遍历 queries，判断当前查询点所在的行，列和正、反对角线是否有灯，如果有，则置 $1$，即该点在查询时是被照亮的。然后进行关闭操作，查找查询点所在的八近邻点及它本身是否有灯，如果有，将该点所在的行、列和正、反对角线的灯数目分别减 $1$，并且将灯从网格中去掉。

最后，返回答案数组即可。

时间复杂度 $O(m+q)$，其中 $m$ 和 $q$ 分别为数组 $\mathit{\text{lamps}}$ 和 $\mathit{\text{queries}}$ 的长度。

func gridIllumination(n int, lamps [][]int, queries [][]int) []int {
	row, col, diag1, diag2 := map[int]int{}, map[int]int{}, map[int]int{}, map[int]int{}
	type pair struct{ x, y int }
	s := map[pair]bool{}
	for _, lamp := range lamps {
		i, j := lamp[0], lamp[1]
		p := pair{i, j}
		if !s[p] {
			s[p] = true
			row[i]++
			col[j]++
			diag1[i-j]++
			diag2[i+j]++
		}
	}
	m := len(queries)
	ans := make([]int, m)
	for k, q := range queries {
		i, j := q[0], q[1]
		if row[i] > 0 || col[j] > 0 || diag1[i-j] > 0 || diag2[i+j] > 0 {
			ans[k] = 1
		}
		for x := i - 1; x <= i+1; x++ {
			for y := j - 1; y <= j+1; y++ {
				p := pair{x, y}
				if s[p] {
					s[p] = false
					row[x]--
					col[y]--
					diag1[x-y]--
					diag2[x+y]--
				}
			}
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

1002. 查找共用字符

简单1 种解法

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

题目、示例与约束

给你一个字符串数组 words ，请你找出所有在 words 的每个字符串中都出现的共用字符（包括重复字符），并以数组形式返回。你可以按 任意顺序 返回答案。

 

示例 1：

输入：words = ["bella","label","roller"]
输出：["e","l","l"]

示例 2：

输入：words = ["cool","lock","cook"]
输出：["c","o"]

 

提示：

• 1 <= words.length <= 100
• 1 <= words[i].length <= 100
• words[i] 由小写英文字母组成

方法一：计数 · Go 实现

思考

对每个字符扫描全部单词可以统计公共出现次数， $n$ 与串长均不超过 $100$，时间足够。重复扫描同一字符集会做许多无用比较。

一个字符能进入答案的次数，等于它在所有单词中出现次数的最小值，即各单词字母多重集合的交。

为此先统计第一个单词的频次，再与其余单词逐个取 $min$，最后按频次展开即可，字符集大小为 $26$，额外空间为常数。

我们用一个长度为 $26$ 的数组 $cnt$ 记录每个字符在所有字符串中出现的最小次数，最后遍历 $cnt$ 数组，将出现次数大于 $0$ 的字符加入答案即可。

时间复杂度 $O(n\sum w_i)$，空间复杂度 $O(|\mathrm{\Sigma }|)$。其中 $n$ 为字符串数组 $words$ 的长度，而 $w_i$ 为字符串数组 $words$ 中第 $i$ 个字符串的长度，另外 $|\mathrm{\Sigma }|$ 为字符集的大小，本题中 $|\mathrm{\Sigma }|=26$。

func commonChars(words []string) (ans []string) {
	cnt := make([]int, 26)
	for i := range cnt {
		cnt[i] = 20000
	}
	for _, w := range words {
		t := make([]int, 26)
		for _, c := range w {
			t[c-'a']++
		}
		for i := 0; i < 26; i++ {
			cnt[i] = min(cnt[i], t[i])
		}
	}
	for i := 0; i < 26; i++ {
		for j := 0; j < cnt[i]; j++ {
			ans = append(ans, string('a'+rune(i)))
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

1010. 总持续时间可被 60 整除的歌曲

中等1 种解法

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

题目、示例与约束

在歌曲列表中，第 i 首歌曲的持续时间为 time[i] 秒。

返回其总持续时间（以秒为单位）可被 60 整除的歌曲对的数量。形式上，我们希望下标数字 i 和 j 满足  i < j 且有 (time[i] + time[j]) % 60 == 0。

 

示例 1：

输入：time = [30,20,150,100,40]
输出：3
解释：这三对的总持续时间可被 60 整除：
(time[0] = 30, time[2] = 150): 总持续时间 180
(time[1] = 20, time[3] = 100): 总持续时间 120
(time[1] = 20, time[4] = 40): 总持续时间 60

示例 2：

输入：time = [60,60,60]
输出：3
解释：所有三对的总持续时间都是 120，可以被 60 整除。

 

提示：

• 1 <= time.length <= 6 * 104
• 1 <= time[i] <= 500

方法一：数学 + 计数 · Go 实现

思考

枚举所有无序对判断时长之和是否整除 $60$，在 $n\le 6\times {10}^4$ 时为平方级。配对只依赖对 $60$ 取模后的余数。

若 $x=amod60$，则与之匹配的余数是 $y=(60-x)mod60$。对每个已出现的 $y$ 计数，即可在读入当前歌时累加合法对数。

用长度为 $60$ 的计数表边遍历边查询再更新，避免把同一首歌与自己配对，时间和余数域均为线性。

如果一个数对 $(a,b)$ 之和能被 $60$ 整除，即 $(a+b)mod60=0$，那么 $(amod60+bmod60)mod60=0$，不妨记 $x=amod60$, $y=bmod60$，那么有 $(x+y)mod60=0$，即 $y=(60-x)mod60$。

因此，我们可以遍历歌曲列表，用一个长度为 $60$ 的数组 $cnt$ 记录每个余数 $x$ 出现的次数。对于当前的 $x$，如果数组 $cnt$ 中存在余数 $y=(60-x)mod60$，那么将 $cnt[y]$ 累加进答案中。然后，将 $x$ 在数组 $cnt$ 中的出现次数加 $1$。继续遍历，直到遍历完整个歌曲列表。

遍历结束后，即可得到满足条件的歌曲对数目。

时间复杂度 $O(n)$，空间复杂度 $O(C)$。其中 $n$ 是歌曲列表的长度；而 $C$ 是余数的可能取值，这里 $C=60$。

func numPairsDivisibleBy60(time []int) (ans int) {
	cnt := [60]int{}
	for _, x := range time {
		x %= 60
		y := (60 - x) % 60
		ans += cnt[y]
		cnt[x]++
	}
	return
}

力扣原题 · Doocs 题解来源

1072. 按列翻转得到最大值等行数

中等1 种解法

标签：数组、哈希表、矩阵

题目、示例与约束

给定 m x n 矩阵 matrix 。

你可以从中选出任意数量的列并翻转其上的 每个 单元格。（即翻转后，单元格的值从 0 变成 1，或者从 1 变为 0 。）

返回 经过一些翻转后，行内所有值都相等的最大行数 。

 

示例 1：

输入：matrix = [[0,1],[1,1]]
输出：1
解释：不进行翻转，有 1 行所有值都相等。

示例 2：

输入：matrix = [[0,1],[1,0]]
输出：2
解释：翻转第一列的值之后，这两行都由相等的值组成。

示例 3：

输入：matrix = [[0,0,0],[0,0,1],[1,1,0]]
输出：2
解释：翻转前两列的值之后，后两行由相等的值组成。

 

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 300
• matrix[i][j] == 0 或 1

方法一：哈希表 · Go 实现

思考

翻转若干列后，相同的行会变成全 $0$ 或全 $1$。两行能同时被翻成相等，当且仅当它们相同或互为取反。 $m,n\le 300$，应按模式计数而不是枚举 $2^n$ 种翻转。

把每行规范化为「首元素为 $0$」的形式：若以 $1$ 开头则整行取反。这样互反的两行落入同一键。

哈希表统计规范化元组的出现次数，最大值即为答案。

我们观察发现，如果矩阵中的两行满足以下条件之一，则它们可以通过翻转某些列的方式得到相等的行：

1. 两行的对应位置元素相等，即如果其中一行元素为 $1,0,0,1$，则另一行元素也为 $1,0,0,1$；
2. 两行的对应位置元素相反，即如果其中一行元素为 $1,0,0,1$，则另一行元素为 $0,1,1,0$。

我们称满足以上条件之一的两行元素为“等价行”，那么题目所求的答案即为矩阵中最多包含等价行的行数。

因此，我们可以遍历矩阵的每一行，将每一行转换成第一个元素为 $0$ 的“等价行”。具体做法如下：

• 如果当前行的第一个元素为 $0$，那么当前行的元素保持不变；
• 如果当前行的第一个元素为 $1$，那么我们将当前行的每个元素进行翻转，即 $0$ 变成 $1$, $1$ 变成 $0$。也就是说，我们将以 $1$ 开头的行翻转成以 $0$ 开头的“等价行”。

这样一来，我们只需要用一个哈希表来统计转换后的每一行的出现次数，其中键为转换后的行（可以将所有数字拼接成一个字符串），值为该行出现的次数。最后，哈希表中值的最大值即为矩阵中最多包含等价行的行数。

时间复杂度 $O(m\times n)$，空间复杂度 $O(m)$。其中 $m$ 和 $n$ 分别是矩阵的行数和列数。

相似题目：

• 2128. 通过翻转行或列来去除所有的 1

func maxEqualRowsAfterFlips(matrix [][]int) (ans int) {
	cnt := map[string]int{}
	for _, row := range matrix {
		s := []byte{}
		for _, x := range row {
			if row[0] == 1 {
				x ^= 1
			}
			s = append(s, byte(x)+'0')
		}
		t := string(s)
		cnt[t]++
		ans = max(ans, cnt[t])
	}
	return
}

力扣原题 · Doocs 题解来源

1122. 数组的相对排序

简单2 种解法

标签：数组、哈希表、冒泡排序、计数排序、排序、快速排序

题目、示例与约束

给你两个数组，arr1 和 arr2，arr2 中的元素各不相同，arr2 中的每个元素都出现在 arr1 中。

对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。

 

示例 1：

输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
输出：[2,2,2,1,4,3,3,9,6,7,19]

示例  2:

输入：arr1 = [28,6,22,8,44,17], arr2 = [22,28,8,6]
输出：[22,28,8,6,17,44]

 

提示：

• 1 <= arr1.length, arr2.length <= 1000
• 0 <= arr1[i], arr2[i] <= 1000
• arr2 中的元素 arr2[i]  各不相同 
• arr2 中的每个元素 arr2[i] 都出现在 arr1 中

方法一：自定义排序 · Go 实现

思考

排序关键字由 $arr2$ 中的相对次序决定，未出现的元素再按自身大小排在后面。哈希表记下 $arr2$ 的下标，自定义比较键为「在表中则用下标，否则用 $1000+x$」，一次排序即可同时处理两类元素。 $arr2$ 中的值互不相同，下标作为次序是稳定的。

我们先用哈希表 $pos$ 记录数组 $arr2$ 中每个元素的位置。然后，我们将数组 $arr1$ 中的每个元素映射成一个二元组 $(pos.get(x,1000+x),x)$，并对二元组进行排序。最后我们取出所有二元组的第二个元素并返回即可。

时间复杂度 $O(n\times \log n+m)$，空间复杂度 $O(n+m)$。其中 $n$ 和 $m$ 分别是数组 $arr1$ 和 $arr2$ 的长度。

func relativeSortArray(arr1 []int, arr2 []int) []int {
	pos := map[int]int{}
	for i, x := range arr2 {
		pos[x] = i
	}
	arr := make([][2]int, len(arr1))
	for i, x := range arr1 {
		if p, ok := pos[x]; ok {
			arr[i] = [2]int{p, x}
		} else {
			arr[i] = [2]int{len(arr2), x}
		}
	}
	sort.Slice(arr, func(i, j int) bool {
		return arr[i][0] < arr[j][0] || arr[i][0] == arr[j][0] && arr[i][1] < arr[j][1]
	})
	for i, x := range arr {
		arr1[i] = x[1]
	}
	return arr1
}

方法二：计数排序 · Go 实现

思考

方法一的比较排序为 $O(n\log n)$。值域不大时，先统计 $arr1$ 频次，再按 $arr2$ 顺序依次输出，最后按值扫描剩余元素，可在线性时间内完成。

我们可以使用计数排序的思想，首先统计数组 $arr1$ 中每个元素的出现次数，然后按照数组 $arr2$ 中的顺序，将 $arr1$ 中的元素按照出现次数放入答案数组 $ans$ 中。最后，我们遍历 $arr1$ 中的所有元素，将未在 $arr2$ 中出现的元素按照升序放入答案数组 $ans$ 的末尾。

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

func relativeSortArray(arr1 []int, arr2 []int) []int {
	cnt := make([]int, 1001)
	mi, mx := 1001, 0
	for _, x := range arr1 {
		cnt[x]++
		mi = min(mi, x)
		mx = max(mx, x)
	}
	ans := make([]int, 0, len(arr1))
	for _, x := range arr2 {
		for cnt[x] > 0 {
			ans = append(ans, x)
			cnt[x]--
		}
	}
	for x := mi; x <= mx; x++ {
		for cnt[x] > 0 {
			ans = append(ans, x)
			cnt[x]--
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

1128. 等价多米诺骨牌对的数量

简单1 种解法

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

题目、示例与约束

给你一组多米诺骨牌 dominoes 。

形式上，dominoes[i] = [a, b] 与 dominoes[j] = [c, d] 等价 当且仅当 (a == c 且 b == d) 或者 (a == d 且 b == c) 。即一张骨牌可以通过旋转 0 度或 180 度得到另一张多米诺骨牌。

在 0 <= i < j < dominoes.length 的前提下，找出满足 dominoes[i] 和 dominoes[j] 等价的骨牌对 (i, j) 的数量。

 

示例 1：

输入：dominoes = [[1,2],[2,1],[3,4],[5,6]]
输出：1

示例 2：

输入：dominoes = [[1,2],[1,2],[1,1],[1,2],[2,2]]
输出：3

 

提示：

• 1 <= dominoes.length <= 4 * 104
• dominoes[i].length == 2
• 1 <= dominoes[i][j] <= 9

方法一：计数 · Go 实现

思考

等价对把 $[a,b]$ 与 $[b,a]$ 视为同一。若对每张牌扫描此前全部牌，时间为平方级。将较小数字放十位、较大放个位，得到 $0$ 到 $99$ 的键，遍历时答案累加该键已出现次数再入表，每张牌只与已见过的等价牌配对一次。

我们可以将每个多米诺骨牌的两个数字按照大小顺序拼接成一个两位数，这样就可以将等价的多米诺骨牌拼接成相同的两位数。例如，[1, 2] 和 [2, 1] 拼接成的两位数都是 12，[3, 4] 和 [4, 3] 拼接成的两位数都是 34。

然后我们遍历所有的多米诺骨牌，用一个哈希表或者一个长度为 $100$ 的数组 $cnt$ 记录每个两位数出现的次数。对于每个多米诺骨牌，我们拼接成的两位数为 $x$，那么答案就会增加 $cnt[x]$，接着我们将 $cnt[x]$ 的值加 $1$。继续遍历下一个多米诺骨牌，就可以统计出所有等价的多米诺骨牌对的数量。

时间复杂度 $O(n)$，空间复杂度 $O(C)$。其中 $n$ 是多米诺骨牌的数量，而 $C$ 是多米诺骨牌中拼接成的两位数的最大数量，即 $100$。

func numEquivDominoPairs(dominoes [][]int) (ans int) {
	cnt := [100]int{}
	for _, e := range dominoes {
		x := e[0]*10 + e[1]
		if e[0] > e[1] {
			x = e[1]*10 + e[0]
		}
		ans += cnt[x]
		cnt[x]++
	}
	return
}

力扣原题 · Doocs 题解来源

1133. 最大唯一数 🔒

简单1 种解法

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

题目、示例与约束

给你一个整数数组 A，请找出并返回在该数组中仅出现一次的最大整数。

如果不存在这个只出现一次的整数，则返回 -1。

 

示例 1：

输入：[5,7,3,9,4,9,8,3,1]
输出：8
解释： 
数组中最大的整数是 9，但它在数组中重复出现了。而第二大的整数是 8，它只出现了一次，所以答案是 8。

示例 2：

输入：[9,9,8,8]
输出：-1
解释： 
数组中不存在仅出现一次的整数。

 

提示：

1. 1 <= A.length <= 2000
2. 0 <= A[i] <= 1000

方法一：计数 + 倒序遍历 · Go 实现

思考

只出现一次的数中取最大，没有则返回 $-1$。计数后筛选频次为 $1$ 的键并取最大即可。值域 $\le 1000$ 时也可用定长数组从大到小扫，语义相同。

注意到题目的数据范围，我们可以使用一个长度为 $1001$ 的数组来统计每个数字出现的次数，然后倒序遍历数组，找到第一个出现次数为 $1$ 的数字即可。如果没有找到，则返回 $-1$。

时间复杂度 $O(n+M)$，空间复杂度 $O(M)$。其中 $n$ 为数组长度；而 $M$ 为数组中出现的最大数字，本题中 $M\le 1000$。

func largestUniqueNumber(nums []int) int {
	cnt := [1001]int{}
	for _, x := range nums {
		cnt[x]++
	}
	for x := 1000; x >= 0; x-- {
		if cnt[x] == 1 {
			return x
		}
	}
	return -1
}

力扣原题 · Doocs 题解来源

1138. 字母板上的路径

中等1 种解法

标签：哈希表、字符串

题目、示例与约束

我们从一块字母板上的位置 (0, 0) 出发，该坐标对应的字符为 board[0][0]。

在本题里，字母板为board = ["abcde", "fghij", "klmno", "pqrst", "uvwxy", "z"]，如下所示。

我们可以按下面的指令规则行动：

• 如果方格存在，'U' 意味着将我们的位置上移一行；
• 如果方格存在，'D' 意味着将我们的位置下移一行；
• 如果方格存在，'L' 意味着将我们的位置左移一列；
• 如果方格存在，'R' 意味着将我们的位置右移一列；
• '!' 会把在我们当前位置 (r, c) 的字符 board[r][c] 添加到答案中。

（注意，字母板上只存在有字母的位置。）

返回指令序列，用最小的行动次数让答案和目标 target 相同。你可以返回任何达成目标的路径。

 

示例 1：

输入：target = "leet"
输出："DDR!UURRR!!DDD!"

示例 2：

输入：target = "code"
输出："RR!DDRR!UUL!R!"

 

提示：

• 1 <= target.length <= 100
• target 仅含有小写英文字母。

方法一：模拟 · Go 实现

思考

棋盘按字母行列排列，目标是从上一字母走到下一字母并输出路径。普通格子四向皆可，但 z 只有上方邻居，若先向下或向右可能走出棋盘。

对每步按「左、上、右、下」的次序移动：先消掉需要左移、上移的量，再右移、下移，从而在到达 z 之前先离开危险方向，最后追加 !。

从起点 $(0,0)$ 出发，模拟每一步的移动，将每一步的移动结果拼接到答案中。注意移动的方向遵循“左、上、右、下”的顺序。

时间复杂度 $O(n)$，其中 $n$ 是字符串 $target$ 的长度，需要遍历字符串 $target$ 中的每一个字符。忽略答案的空间消耗，空间复杂度 $O(1)$。

func alphabetBoardPath(target string) string {
	ans := []byte{}
	var i, j int
	for _, c := range target {
		v := int(c - 'a')
		x, y := v/5, v%5
		for j > y {
			j--
			ans = append(ans, 'L')
		}
		for i > x {
			i--
			ans = append(ans, 'U')
		}
		for j < y {
			j++
			ans = append(ans, 'R')
		}
		for i < x {
			i++
			ans = append(ans, 'D')
		}
		ans = append(ans, '!')
	}
	return string(ans)
}

力扣原题 · Doocs 题解来源

1152. 用户网站访问行为分析 🔒

中等1 种解法

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

题目、示例与约束

给定两个字符串数组 username 和 website 和一个整数数组 timestamp 。给定的数组长度相同，其中元组 [username[i], website[i], timestamp[i]] 表示用户 username[i] 在时间 timestamp[i] 访问了网站 website[i] 。

访问模式 是包含三个网站的列表(不一定是完全不同的)。

• 例如，["home"， "away"， "love"]， ["leetcode"， "love"， "leetcode"]，和 ["luffy"， "luffy"， "luffy"] 都是模式。

一种 访问模式 的 得分 是访问该模式中所有网站的用户数量，这些网站在该模式中出现的顺序相同。

• 例如，如果模式是 [“home”，“away”，“love”] ，那么分数就是用户数量 x , x 访问了 “home” ，然后访问了 “away” ，然后访问了 “love” 。
• 同样，如果模式是 ["leetcode"， "love"， "leetcode"] ，那么分数就是用户数量 x ，使得 x 访问了"leetcode"，然后访问了 "love" ，之后又访问了 "leetcode" 。
• 另外，如果模式是 [“luffy”，“luffy”，“luffy”] ，那么分数就是用户数量 x ，使得 x 就可以在不同的时间戳上访问 “luffy” 三次。

返回 得分 最大的 访问模式 。如果有多个访问模式具有相同的最大分数，则返回字典序最小的。

请注意，模式中的网站不需要连续访问，只需按照模式中出现的顺序访问即可。

 

示例 1：

输入：username = ["joe","joe","joe","james","james","james","james","mary","mary","mary"], timestamp = [1,2,3,4,5,6,7,8,9,10], website = ["home","about","career","home","cart","maps","home","home","about","career"]
输出：["home","about","career"]
解释：本例中的元组是:
["joe","home",1],["joe","about",2],["joe","career",3],["james","home",4],["james","cart",5],["james","maps",6],["james","home",7],["mary","home",8],["mary","about",9] 和 ["mary","career",10]。
模式 ("home", "about", "career") 的得分为 2（joe 和 mary）。
模式 ("home", "cart", "maps") 的得分为 1 (james).
模式 ("home", "cart", "home") 的得分为 1 (james).
模式 ("home", "maps", "home") 的得分为 1 (james).
模式 ("cart", "maps", "home") 的得分为 1 (james).
模式 ("home", "home", "home") 的得分为 0(没有用户访问过 home 3次)。

示例 2：

输入: username = ["ua","ua","ua","ub","ub","ub"], timestamp = [1,2,3,4,5,6], website = ["a","b","a","a","b","c"]
输出: ["a","b","a"]

 

提示：

• 3 <= username.length <= 50
• 1 <= username[i].length <= 10
• timestamp.length == username.length
• 1 <= timestamp[i] <= 109
• website.length == username.length
• 1 <= website[i].length <= 10
• username[i] 和 website[i] 都只含小写字符
• 它保证至少有一个用户访问了至少三个网站
• 所有元组 [username[i]， timestamp[i]， website[i] 均 不重复

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

思考

模式按时间顺序的三元组计，同一用户的相同三元组只贡献一次，再在用户间累加。先按时间排序并按用户收集访问序列，对每人枚举有序三下标得到去重三元组，用计数器统计后按次数降序、字典序升序取第一条。

我们先用哈希表 $d$ 记录每个用户访问的网站，然后遍历 $d$，对于每个用户，我们枚举其访问的所有三元组，统计去重三元组的出现次数，最后遍历所有三元组，返回出现次数最多的、字典序最小的三元组。

时间复杂度 $O(n^3)$，空间复杂度 $O(n^3)$。其中 $n$ 是 username 的长度。

func mostVisitedPattern(username []string, timestamp []int, website []string) []string {
	d := map[string][]pair{}
	for i, user := range username {
		ts := timestamp[i]
		site := website[i]
		d[user] = append(d[user], pair{ts, site})
	}
	cnt := map[string]int{}
	for _, sites := range d {
		m := len(sites)
		s := map[string]bool{}
		if m > 2 {
			sort.Slice(sites, func(i, j int) bool { return sites[i].ts < sites[j].ts })
			for i := 0; i < m-2; i++ {
				for j := i + 1; j < m-1; j++ {
					for k := j + 1; k < m; k++ {
						s[sites[i].site+","+sites[j].site+","+sites[k].site] = true
					}
				}
			}
		}
		for t := range s {
			cnt[t]++
		}
	}
	mx, t := 0, ""
	for p, v := range cnt {
		if mx < v || (mx == v && p < t) {
			mx = v
			t = p
		}
	}
	return strings.Split(t, ",")
}

type pair struct {
	ts   int
	site string
}

力扣原题 · Doocs 题解来源

1160. 拼写单词

简单1 种解法

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

题目、示例与约束

给定一个字符串数组 words 和一个字符串 chars。

如果字符串可以由 chars 中的字符组成（每个字符在 每个 words 中只能使用一次），则认为它是好的。

返回 words 中所有好的字符串的长度之和。

 

示例 1：

输入：words = ["cat","bt","hat","tree"], chars = "atach"
输出：6
解释： 
可以形成字符串 "cat" 和 "hat"，所以答案是 3 + 3 = 6。

示例 2：

输入：words = ["hello","world","leetcode"], chars = "welldonehoneyr"
输出：10
解释：
可以形成字符串 "hello" 和 "world"，所以答案是 5 + 5 = 10。

 

提示：

• 1 <= words.length <= 1000
• 1 <= words[i].length, chars.length <= 100
• words[i] 和 chars 中都仅包含小写英文字母

方法一：计数 · Go 实现

思考

单词能否由 $chars$ 拼出，取决于每种字母的用量不超过库存。对每个单词再扫描 $chars$ 会重复计数。先统计 $chars$ 的频次，再对每个词做频次比较：任一字母超出则不可用，否则把词长累加。字母表大小为常数，比较为线性。

我们可以用一个长度为 $26$ 的数组 $cnt$ 统计字符串 $chars$ 中每个字母出现的次数。

然后遍历字符串数组 $words$，对于每个字符串 $w$，我们用一个长度为 $26$ 的数组 $wc$ 统计字符串 $w$ 中每个字母出现的次数，如果对于每个字母 $c$， $wc[c]\le cnt[c]$，那么我们就可以用 $chars$ 中的字母拼写出字符串 $w$，否则我们无法拼写出字符串 $w$。如果可以拼写出字符串 $w$，那么我们就将字符串 $w$ 的长度加到答案中。

遍历结束后，即可得到答案。

时间复杂度 $O(L)$，空间复杂度 $O(C)$。其中 $L$ 为题目中所有字符串的长度之和；而 $C$ 为字符集的大小，本题中 $C=26$。

func countCharacters(words []string, chars string) (ans int) {
	cnt := [26]int{}
	for _, c := range chars {
		cnt[c-'a']++
	}
	for _, w := range words {
		wc := [26]int{}
		ok := true
		for _, c := range w {
			c -= 'a'
			wc[c]++
			if wc[c] > cnt[c] {
				ok = false
				break
			}
		}
		if ok {
			ans += len(w)
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1165. 单行键盘 🔒

简单1 种解法

标签：哈希表、字符串

题目、示例与约束

我们定制了一款特殊的键盘，所有的键都 排列在一行上 。

给定一个长度为 26 的字符串 keyboard ，来表示键盘的布局(索引从 0 到 25 )。一开始，你的手指在索引 0 处。要输入一个字符，你必须把你的手指移动到所需字符的索引处。手指从索引 i 移动到索引 j 所需要的时间是 |i - j|。

您需要输入一个字符串 word 。写一个函数来计算用一个手指输入需要多少时间。

 

示例 1：

输入：keyboard = "abcdefghijklmnopqrstuvwxyz", word = "cba"
输出：4
解释：从 0 号键移动到 2 号键来输出 'c'，又移动到 1 号键来输出 'b'，接着移动到 0 号键来输出 'a'。
总用时 = 2 + 1 + 1 = 4. 

示例 2：

输入：keyboard = "pqrstuvwxyzabcdefghijklmno", word = "leetcode"
输出：73

 

提示：

• keyboard.length == 26
• keyboard 按某种特定顺序排列，并包含每个小写英文字母一次。
• 1 <= word.length <= 104
• word[i] 为小写英文字母

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

思考

每次移动代价是键盘上两字符下标之差的绝对值。先把键盘字符映射到位置，再从下标 $0$ 起依次累加 $|\mathit{\text{pos}}[c]-i|$ 并更新手指位置。不必每次在键盘串里线性查找。

我们可以用哈希表或者一个长度为 $26$ 的数组 $pos$ 来存储每个字符在键盘上的位置，其中 $pos[c]$ 表示字符 $c$ 在键盘上的位置。

然后我们遍历字符串 $word$，用一个变量 $i$ 记录当前手指所在的位置，初始时 $i=0$。每次计算当前字符 $c$ 在键盘上的位置 $j$，并将答案增加 $|i-j|$，然后将 $i$ 更新为 $j$。继续遍历下一个字符，直到遍历完整个字符串 $word$。

遍历完字符串 $word$ 之后，即可得到答案。

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

func calculateTime(keyboard string, word string) (ans int) {
	pos := [26]int{}
	for i, c := range keyboard {
		pos[c-'a'] = i
	}
	i := 0
	for _, c := range word {
		j := pos[c-'a']
		ans += abs(i - j)
		i = j
	}
	return
}

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

力扣原题 · Doocs 题解来源

1169. 查询无效交易

中等1 种解法

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

题目、示例与约束

如果出现下述两种情况，交易 可能无效：

• 交易金额超过 $1000
• 或者，它和 另一个城市 中 同名 的另一笔交易相隔不超过 60 分钟（包含 60 分钟整）

给定字符串数组交易清单 transaction 。每个交易字符串 transactions[i] 由一些用逗号分隔的值组成，这些值分别表示交易的名称，时间（以分钟计），金额以及城市。

返回 transactions，返回可能无效的交易列表。你可以按 任何顺序 返回答案。

 

示例 1：

输入：transactions = ["alice,20,800,mtv","alice,50,100,beijing"]
输出：["alice,20,800,mtv","alice,50,100,beijing"]
解释：第一笔交易是无效的，因为第二笔交易和它间隔不超过 60 分钟、名称相同且发生在不同的城市。同样，第二笔交易也是无效的。

示例 2：

输入：transactions = ["alice,20,800,mtv","alice,50,1200,mtv"]
输出：["alice,50,1200,mtv"]

示例 3：

输入：transactions = ["alice,20,800,mtv","bob,50,1200,mtv"]
输出：["bob,50,1200,mtv"]

 

提示：

• transactions.length <= 1000
• 每笔交易 transactions[i] 按 "{name},{time},{amount},{city}" 的格式进行记录
• 每个交易名称 {name} 和城市 {city} 都由小写英文字母组成，长度在 1 到 10 之间
• 每个交易时间 {time} 由一些数字组成，表示一个 0 到 1000 之间的整数
• 每笔交易金额 {amount} 由一些数字组成，表示一个 0 到 2000 之间的整数

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

思考

一笔交易无效当且仅当金额超过 $1000$，或同名不同城且时间差不超过 $60$。按姓名分组记录 $(\mathit{\text{time}},\mathit{\text{city}},\mathit{\text{index}})$，新交易与同组已有记录比较即可标出双方。金额条件单独判定。 $n$ 不大，组内两两检查可接受。

遍历交易列表，对于每笔交易，如果金额大于 1000，或者同名且城市不同且时间间隔不超过 60 分钟，则将其加入答案。

具体地，我们使用哈希表 d 记录每个交易，其中键为交易名称，值为一个列表，列表中的每个元素为一个三元组 (time, city, index)，表示在 time 时刻在 city 城市进行了编号为 index 的交易。同时，我们使用哈希表 idx 记录答案中的交易编号。

遍历交易列表，对于每笔交易，我们首先将其加入哈希表 d 中，然后判断其金额是否大于 1000，如果是，则将其编号加入答案中。然后我们遍历哈希表 d 中的交易，如果交易名称相同且城市不同且时间间隔不超过 60 分钟，则将其编号加入答案中。

最后，我们遍历答案中的交易编号，将其对应的交易加入答案即可。

时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。其中 $n$ 为交易列表的长度。

func invalidTransactions(transactions []string) (ans []string) {
	d := map[string][]tuple{}
	idx := map[int]bool{}
	for i, x := range transactions {
		e := strings.Split(x, ",")
		name := e[0]
		time, _ := strconv.Atoi(e[1])
		amount, _ := strconv.Atoi(e[2])
		city := e[3]
		d[name] = append(d[name], tuple{time, city, i})
		if amount > 1000 {
			idx[i] = true
		}
		for _, item := range d[name] {
			if city != item.city && abs(time-item.t) <= 60 {
				idx[i], idx[item.i] = true, true
			}
		}
	}
	for i := range idx {
		ans = append(ans, transactions[i])
	}
	return
}

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

type tuple struct {
	t    int
	city string
	i    int
}

力扣原题 · Doocs 题解来源

1181. 前后拼接 🔒

中等1 种解法

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

题目、示例与约束

给你一个「短语」列表 phrases，请你帮忙按规则生成拼接后的「新短语」列表。

「短语」（phrase）是仅由小写英文字母和空格组成的字符串。「短语」的开头和结尾都不会出现空格，「短语」中的空格不会连续出现。

「前后拼接」（Before and After puzzles）是合并两个「短语」形成「新短语」的方法。我们规定拼接时，第一个短语的最后一个单词 和 第二个短语的第一个单词 必须相同。

返回每两个「短语」 phrases[i] 和 phrases[j]（i != j）进行「前后拼接」得到的「新短语」。

注意，两个「短语」拼接时的顺序也很重要，我们需要同时考虑这两个「短语」。另外，同一个「短语」可以多次参与拼接，但「新短语」不能再参与拼接。

请你按字典序排列并返回「新短语」列表，列表中的字符串应该是 不重复的 。

 

示例 1：

输入：phrases = ["writing code","code rocks"]

输出：["writing code rocks"]

示例 2：

输入：phrases = ["mission statement", "a quick bite to eat",   "a chip off the old block",   "chocolate bar",   "mission impossible",   "a man on a mission",   "block party",   "eat my words",   "bar of soap"]

输出：["a chip off the old block party",   "a man on a mission impossible",   "a man on a mission statement",   "a quick bite to eat my words", "chocolate bar of soap"]

示例 3：

输入：phrases = ["a","b","a"]

输出：["a"]

示例 4：

输入：phrases = ["ab ba","ba ab","ab ba"]

输出：["ab ba ab","ba ab ba"]

 

提示：

• 1 <= phrases.length <= 100
• 1 <= phrases[i].length <= 100

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

思考

两条不同短语可拼接，当且仅当前者末词等于后者首词，重叠词只保留一次。短语数量不大，预处理首尾词后枚举有序对 $(i,j)$，命中则拼接并放入集合去重，最后按字典序输出。

我们先遍历列表 phrases，将每个短语的首尾单词存储数组 $ps$ 中，其中 $ps[i][0]$ 和 $ps[i][1]$ 分别表示第 $i$ 个短语的首尾单词。

接下来，我们枚举所有 $(i,j)$，其中 $i,j\in [0,n)$ 且 $i\ne j$。如果 $ps[i][1]=ps[j][0]$，那么我们就可以将第 $i$ 个短语和第 $j$ 个短语进行拼接，得到的新短语为 $phrases[i]+phrases[j][len(ps[j][0]):]$，将新短语加入哈希表 $s$ 中。

最后，我们将哈希表 $s$ 转化为数组并排序，即可得到答案。

时间复杂度 $O(n^2\times m\times (\log n+\log m))$，空间复杂度 $O(n^2\times m)$。其中 $n$ 和 $m$ 分别表示数组 $phrases$ 的长度和每个短语的平均长度。

func beforeAndAfterPuzzles(phrases []string) []string {
	n := len(phrases)
	ps := make([][2]string, n)
	for i, p := range phrases {
		ws := strings.Split(p, " ")
		ps[i] = [2]string{ws[0], ws[len(ws)-1]}
	}
	s := map[string]bool{}
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			if i != j && ps[i][1] == ps[j][0] {
				s[phrases[i]+phrases[j][len(ps[j][0]):]] = true
			}
		}
	}
	ans := make([]string, 0, len(s))
	for k := range s {
		ans = append(ans, k)
	}
	sort.Strings(ans)
	return ans
}

力扣原题 · Doocs 题解来源

1189. “气球” 的最大数量

简单1 种解法

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

题目、示例与约束

给你一个字符串 text，你需要使用 text 中的字母来拼凑尽可能多的单词 "balloon"（气球）。

字符串 text 中的每个字母最多只能被使用一次。请你返回最多可以拼凑出多少个单词 "balloon"。

 

示例 1：

输入：text = "nlaebolko"
输出：1

示例 2：

输入：text = "loonbalxballpoon"
输出：2

示例 3：

输入：text = "leetcode"
输出：0

 

提示：

• 1 <= text.length <= 104
• text 全部由小写英文字母组成

 

注意：本题与 2287. 重排字符形成目标字符串 相同。

方法一：计数 · Go 实现

思考

balloon 各字母需求为 $b,a,l\times 2,o\times 2,n$。统计 text 频次后把 $l$、 $o$ 折半，再在 $b,a,l,o,n$ 上取最小，即最多能拼出的单词数。不必反复从串中删除。

我们统计字符串 text 中每个字母出现的次数，然后将其中字母 'o' 和 'l' 的出现次数分别除以 2，这是因为单词 balloon 中字母 'o' 和 'l' 都出现了 2 次。

接着，我们遍历单词 balon 中的每个字母，统计每个字母在字符串 text 中出现的次数的最小值，这个最小值就是单词 balloon 在字符串 text 中出现的最大次数。

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

func maxNumberOfBalloons(text string) int {
	cnt := [26]int{}
	for _, c := range text {
		cnt[c-'a']++
	}
	cnt['l'-'a'] >>= 1
	cnt['o'-'a'] >>= 1
	ans := 1 << 30
	for _, c := range "balon" {
		if x := cnt[c-'a']; ans > x {
			ans = x
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源