本文已收录到 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）
题目地址
题目描述
给你两个字符串 s 和 goal ，只要我们可以通过交换 s 中的两个字母得到与 goal 相等的结果，就返回 true ；否则返回 false 。
i 和 j （下标从 0 开始）且满足 i != j ，接着交换 s[i] 和 s[j] 处的字符。
- 例如，在
"abcd" 中交换下标 0 和下标 2 的元素可以生成 "cbad" 。
题解（模拟）
- 如果
- 如果
s和goal不相符的位置数量超过 2，则必然不符； - 如果
s和goal不相符的位置数量为 2，则必然相符（因为词频相同，所以可以不用判断这两个位置上的字符是否对立）； - 如果
s和goal不相符的位置数量为 1，则必然不符； - 如果
s和goal不相符的位置数量为 0，则需要判断是否至少存在一个字符的词频大于 1。
s 和 goal 的长度不同或者词频不同，则必然不符；
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$ 计数数组空间。
相似题目：
- 1790. 仅执行一次字符串交换能否使两个字符串相等
- 242. 有效的字母异位词
- 387. 字符串中的第一个唯一字符
T2 · 数青蛙（Medium）
题目地址
题目描述
给你一个字符串 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$ 计数数组空间。
相似题目：
- 20. 有效的括号