特斯拉产品研发创新中心 3 月 22 日笔试答案-六虎

本文已收录到 AndroidFamily，技能和职场问题，请重视公众号 [彭旭锐] 提问。

大家好，我是小彭。

昨日是 「特斯拉 2023 春季公开书面考试 – 产品研发创新中心专场」，你参与了吗？这场书面考试整体来看没有难到特别离谱的题，但需求一些思维。

竞赛题解一览

T1 密切字符串（Easy）

题解：模仿 $O (n + C)$

T2 数青蛙（Medium）

题解：模仿 $O (n + C)$

T3 恢复 IP 地址（Medium）

题解：回溯 $O(3^4n)$

T4 课程表 III（Hard）

题解：贪心 + 大顶堆 $O (n l g n + n)$

T1 密切字符串（Easy）

标题地址

leetcode.cn/problems/bu…

标题描绘

给你两个字符串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$ 是 $n u m s$ 数组的长度， $C$ 是字符集巨细， $C$ 为常数 $26$ ；
空间复杂度： $O (C)$ 计数数组空间。

相似标题：

1790.仅履行一次字符串交流能否使两个字符串持平
242.有用的字母异位词
387.字符串中的第一个仅有字符

T2 数青蛙（Medium）

标题地址

leetcode.cn/problems/mi…

标题描绘

给你一个字符串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$ 是 $cro ak O f F ro g s$ 字符串的长度， $C$ 是字符集巨细， $C$ 为常数 $5$ ；
空间复杂度： $O (C)$ 计数数组空间。

相似标题：

20.有用的括号
1249.移除无效的括号

T3 恢复 IP 地址（Medium）

标题地址

leetcode.cn/problems/re…

标题描绘

有用 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^4n)$ 其间 3 是每一层的最大挑选列表；4 是最大片段数，n 是字符串的长度。回溯递归栈的最大深度是 4 层，每一层有 3 种选项，因而一共有 $3^4$ 种子状况，每个子状况最多需求花费 $O (n)$ 时刻结构成果字符串；
空间复杂度： $O (4)$ 递归栈空间，不考虑成果数组和路径数组。

相似标题：

46.全排列
77.组合

T4 课程表 III（Hard）

标题地址

leetcode.cn/problems/co…

标题描绘

这里有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 (n l g n + n)$ 其间 $n$ 为 $co u rses$ 数组的长度；
空间复杂度： $O (l g n + n)$ 排序递归栈空间和大顶堆空间。

相似标题：

55.跳跃游戏
207.课程表
210.课程表 II
252. 会议室
253. 会议室 II
2402.会议室 III

OK，这场书面考试就讲这么多，咱们下周见。

本文正在参与「金石方案」

特斯拉产品研发创新中心 3 月 22 日笔试答案

竞赛题解一览

T1 密切字符串（Easy）

标题地址

标题描绘

题解（模仿）

T2 数青蛙（Medium）

标题地址

标题描绘

题解（模仿）

T3 恢复 IP 地址（Medium）

标题地址

标题描绘

题解（回溯）

T4 课程表 III（Hard）

标题地址

标题描绘

题解（排序 + 贪心 + 大顶堆）

相关文章

高通Android 11平台上移植GNSS

来了，简单宣告下 Compose for iOS Alpha 正式发布

CSS in JS = JSS , 这个库你知道吗？

还原火山引擎A/B测试产品——DataTester 私有化部署实践经验

作者信息