本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 提问。
大家好，我是小彭。
昨天是 「特斯拉 2023 春季公开笔试 - 产品研发创新中心专场」，你参加了吗？这场笔试整体来看没有难到特别离谱的题，但需要一些思维。
竞赛题解一览
T1 · 亲密字符串（Easy）
- 题解：模拟 $O(n + C)$
T2 · 数青蛙（Medium）
- 题解：模拟 $O(n + C)$
T3 · 复原 IP 地址（Medium）
- 题解：回溯 $O(3^4·n)$
T4 · 课程表 III（Hard）
- 题解：贪心 + 大顶堆 $O(nlgn + n)$
T1 · 亲密字符串（Easy）
题目地址
https://leetcode.cn/problems/buddy-strings/
题目描述
给你两个字符串 s 和 goal ，只要我们可以通过交换 s 中的两个字母得到与 goal 相等的结果，就返回 true ；否则返回 false 。
交换字母的定义是：取两个下标 i 和 j （下标从 0 开始）且满足 i != j ，接着交换 s[i] 和 s[j] 处的字符。
- 例如，在
"abcd"中交换下标0和下标2的元素可以生成"cbad"。
题解（模拟）
简单模拟题。
- 如果
s和goal的长度不同或者词频不同，则必然不符； - 如果
s和goal不相符的位置数量超过 2，则必然不符； - 如果
s和goal不相符的位置数量为 2，则必然相符（因为词频相同，所以可以不用判断这两个位置上的字符是否对立）； - 如果
s和goal不相符的位置数量为 1，则必然不符； - 如果
s和goal不相符的位置数量为 0，则需要判断是否至少存在一个字符的词频大于 1。
class Solution {
fun buddyStrings(s: String, goal: String): Boolean {
// 长度不同
if (s.length != goal.length) return false
// 计数
var diff = 0
val cnts1 = IntArray(26)
val cnts2 = IntArray(26)
for (index in s.indices) {
cnts1[s[index] - 'a']++
cnts2[goal[index] - 'a']++
// 字符不匹配
if (s[index] != goal[index]) diff++
}
// 检查
var flag = false
for (index in cnts1.indices) {
// 词频不同
if (cnts1[index] != cnts2[index]) return false
// 词频大于等于 2
if (cnts1[index] >= 2) flag = true
}
return diff == 2 || (diff == 0 && flag)
}
}复杂度分析：
- 时间复杂度：$O(n + C)$ 其中 $n$ 是 $nums$ 数组的长度，$C$ 是字符集大小，$C$ 为常数 $26$；
- 空间复杂度：$O(C)$ 计数数组空间。
相似题目：
T2 · 数青蛙（Medium）
题目地址
https://leetcode.cn/problems/minimum-number-of-frogs-croaking/
题目描述
给你一个字符串 croakOfFrogs，它表示不同青蛙发出的蛙鸣声（字符串 "croak" ）的组合。由于同一时间可以有多只青蛙呱呱作响，所以 croakOfFrogs 中会混合多个 “croak” 。
请你返回模拟字符串中所有蛙鸣所需不同青蛙的最少数目。
要想发出蛙鸣 "croak"，青蛙必须 依序 输出 ‘c’, ’r’, ’o’, ’a’, ’k’ 这 5 个字母。如果没有输出全部五个字母，那么它就不会发出声音。如果字符串 croakOfFrogs 不是由若干有效的 "croak" 字符混合而成，请返回 -1 。
题解（模拟）
中等模拟题，这道题卡了很久，浪费很多时间在思考栈、队列、单调队列等方向上。
我们发现：合法的青蛙叫声应该是按照 c → r → o → a → k 的顺序出现的，因此，叫声的每个阶段必然是（非严格）递增的。例如示例 crcaokroak 非法：在处理到第一个 'a' 的位置时，'a' 的计数是 1，'o' 的计数是 0，所以必然不合法。
因此，我们可以维护每个字符的出现次数，在处理每个字符时先累加当前字符的出现次数，再检查上一个阶段的字符的出现次数是否大于等于当前字符的出现次数（'c' 不需要检查）。
另外，题目要求的是最多青蛙数量，答案应该记录 'c' 和 'k' 字符的最大差值。
class Solution {
fun minNumberOfFrogs(croakOfFrogs: String): Int {
// 字符映射到数字
val ids = mapOf('c' to 0, 'r' to 1, 'o' to 2, 'a' to 3, 'k' to 4)
var ret = 0
// 字符计数
val cnts = IntArray(5)
// 枚举字符
for (c in croakOfFrogs) {
++cnts[ids[c]!!]
// 检查上一个阶段的字符是否足够
if ('c' != c && cnts[ids[c]!! - 1] < cnts[ids[c]!!]) return -1
// 记录最大差值
ret = Math.max(ret, cnts[0] - cnts[4])
}
// 检查各个阶段出现次数是否相等
if (!cnts.all { it == cnts[0] }) return -1
return ret
}
}复杂度分析：
- 时间复杂度：$O(n + C)$ 其中 $n$ 是 $croakOfFrogs$ 字符串的长度，$C$ 是字符集大小，$C$ 为常数 $5$；
- 空间复杂度：$O(C)$ 计数数组空间。
相似题目：
T3 · 复原 IP 地址（Medium）
题目地址
https://leetcode.cn/problems/restore-ip-addresses/
题目描述
有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
- 例如：
"0.1.2.201"和"192.168.1.1"是 有效 IP 地址，但是"0.011.255.245"、"192.168.1.312"和"192.168@1.1"是 无效 IP 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
题解（回溯）
简单回溯模板题，按照回溯三要素编码即可：
- 终止条件：index == s.length
- 路径 path：已选择的片段，我们用 List 记录，再输出结果时再补充分隔符
- 选择列表：可以选择 1 到 3 个字符，限制条件是不能有前导 0 且数字大小不超过 255。
class Solution {
fun restoreIpAddresses(s: String): List<String> {
val ret = LinkedList<String>()
backtrack(s, 0, LinkedList<String>(), ret)
return ret
}
private fun backtrack(s: String, index: Int, path: LinkedList<String>, result: LinkedList<String>) {
// 终止条件
if (index == s.length) {
// 满足 IPv4 格式
if (path.size == 4) result.add(path.joinToString("."))
return
}
// 剪枝：已经达到 4 个片段但字符串未结束
if (path.size == 4) return
// 剪枝：1 到 3 个字符，但不能有前导 0 和越界
val maxIndex = if (s[index] == '0') index else Math.min(index + 2, s.length - 1)
// 枚举选项
for (toIndex in index..maxIndex) {
val segment = s.substring(index, toIndex + 1)
// 剪枝：超过 255 范围
if (segment.toInt() > 255) return
// 选择
path.add(segment)
// 递归
backtrack(s, toIndex + 1, path, result)
// 回溯
path.removeLast()
}
}
}复杂度分析：
- 时间复杂度：$O(3^4·n)$ 其中 3 是每一层的最大选择列表；4 是最大片段数，n 是字符串的长度。回溯递归栈的最大深度是 4 层，每一层有 3 种选项，因此一共有 $3^4$ 种子状态，每个子状态最多需要花费 $O(n)$ 时间构造结果字符串；
- 空间复杂度：$O(4)$ 递归栈空间，不考虑结果数组和路径数组。
相似题目：
T4 · 课程表 III（Hard）
题目地址
https://leetcode.cn/problems/course-schedule-iii/description/
题目描述
这里有 n 门不同的在线课程，按从 1 到 n 编号。给你一个数组 courses ，其中 courses[i] = [durationi, lastDayi] 表示第 i 门课将会 持续 上 durationi 天课，并且必须在不晚于 lastDayi 的时候完成。
你的学期从第 1 天开始。且不能同时修读两门及两门以上的课程。
返回你最多可以修读的课程数目。
题解（排序 + 贪心 + 大顶堆）
这道题可以用常识辅助思考：
- 如果两门课的 DDL 不同，那么应该优先学 DDL 较早的；
亦可严格证明：设两门课为 c1(t1, d1), c2(t2, d2)，且满足 d1 ≤ d2，即 c1 的截止时间较早，则有 4 种上课方案（设学期开始时间为 0）：
- 只上 c1，需要满足
t1 <= d1 - 只上 c2：需要满足
t2 <= d2 - 先上 c1 再上 c2，需要满足
t1 + t2 <= d2 - 先上 c2 再上 c1，需要满足
t2 + t1 <= d1 <= d2
由于 d1 <= d2，因此 「先学习后者，再学习前者」的条件 t2 + t1 <= d1 成立，也说明 「先学习前者，再学习后者」的条件 t2 + t1 <= d2 也成立。但反过来，如果 t1 + t2 <= d2 无法推出 t2 + t1 <= d1 成立。
以上说明先学习截止时间晚的方案不会比先学习截止时间早的方案更优。因此，我们可以先将所有的课程按照截止时间进行升序排序，再依次挑选课程进行学习。
- 如果两门课的 DDL 相同，那么应该优先学 Duration 较短的；
亦可用类似的方式证明，也很容易直观理解，优先学习时长更短的课程能够减缓时间推进速度，更有利于选出更优的方案。
- 如果一门课没有足够的时间完成，那么可以尝试战术性淘汰已选择列表中耗时最长课程，给之后的课程留出时间。
这一点比较不好想到，但是编码不难，难的是如何证明 “淘汰已选择列表中耗时最长课程” 的做法是最优的方案，以及如何保证替换淘汰后替换成当前课程后也能够满足截止时间限制。
亦可简单证明：设已选择的前 i - 1 门课程的最优方案为 {t_1、t_2、t_3、…t_{i-1}} 有学习总时长 time，那么对于课程 courses[i] 来说，则有：
- 如果
time + courses[i][0] ≤ courses[i][1]，那么可以进行学习； - 否则，我们从已选择列表中寻找出学习时长最长的课程
courses[j]，且满足courses[j][0] > courses[i][0]，即该课程的学习时长大于当前课程的时长。那么我们替换这两个课程（每个课程的贡献都是 1 的前提下），一定不会得到更差的方案，且能够减缓时间的推进进度。
最后剩下的问题是如何寻找 “已选择列表中耗时最长课程”，这个用大顶堆很简单。
class Solution {
fun scheduleCourse(courses: Array<IntArray>): Int {
// 按照截止时间排序
Arrays.sort(courses) { c1, c2 ->
c1[1] - c2[1]
}
// 选择列表（大顶堆，按照时长降序）
val heap = PriorityQueue<IntArray>() { c1, c2 ->
c2[0] - c1[0]
}
var time = 0
for (course in courses) {
if (time + course[0] <= course[1]) {
// 可以选择
time += course[0]
heap.offer(course)
} else if (!heap.isEmpty() && heap.peek()[0] > course[0]) {
// 无法选择，尝试淘汰并替换耗时最长任务
time -= heap.poll()[0]
time += course[0]
heap.offer(course)
} // else 无法替换
}
// 选择列表
return heap.size
}
}复杂度分析：
- 时间复杂度：$O(nlgn + n)$ 其中 $n$ 为 $courses$ 数组的长度；
- 空间复杂度：$O(lgn + n)$ 排序递归栈空间和大顶堆空间。
相似题目：
