LeetCode 题解工作台
需要教语言的最少人数
在一个由 m 个用户组成的社交网络里，我们获取到一些用户之间的好友关系。两个用户之间可以相互沟通的条件是他们都掌握同一门语言。 给你一个整数 n ，数组 languages 和数组 friendships ，它们的含义如下： 总共有 n 种语言，编号从 1 到 n 。 languages[i] 是第…
3
题型
6
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
对于每个好友关系，如果两个人掌握的语言集合不相交，则需要教一门语言，使得两个人可以相互沟通，我们将这些人放入一个哈希集合 中。 然后在这个集合 中，统计每种语言掌握的人数，获取最大的人数，我们记为 ，那么答案就是 $|s| - mx$。其中 表示集合 的大小。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
在一个由 m 个用户组成的社交网络里，我们获取到一些用户之间的好友关系。两个用户之间可以相互沟通的条件是他们都掌握同一门语言。
给你一个整数 n ，数组 languages 和数组 friendships ，它们的含义如下：
- 总共有
n种语言，编号从1到n。 languages[i]是第i位用户掌握的语言集合。friendships[i] = [ui, vi]表示ui 和vi为好友关系。
你可以选择 一门 语言并教会一些用户，使得所有好友之间都可以相互沟通。请返回你 最少 需要教会多少名用户。
请注意，好友关系没有传递性，也就是说如果x 和 y 是好友，且 y 和 z 是好友， x 和 z 不一定是好友。
示例 1：
输入：n = 2, languages = [[1],[2],[1,2]], friendships = [[1,2],[1,3],[2,3]] 输出：1 解释：你可以选择教用户 1 第二门语言，也可以选择教用户 2 第一门语言。
示例 2：
输入：n = 3, languages = [[2],[1,3],[1,2],[3]], friendships = [[1,4],[1,2],[3,4],[2,3]] 输出：2 解释：教用户 1 和用户 3 第三门语言，需要教 2 名用户。
提示：
2 <= n <= 500languages.length == m1 <= m <= 5001 <= languages[i].length <= n1 <= languages[i][j] <= n1 <= ui < vi <= languages.length1 <= friendships.length <= 500- 所有的好友关系
(ui, vi)都是唯一的。 languages[i]中包含的值互不相同。
解题思路
方法一：模拟 + 统计
对于每个好友关系，如果两个人掌握的语言集合不相交，则需要教一门语言，使得两个人可以相互沟通，我们将这些人放入一个哈希集合 中。
然后在这个集合 中，统计每种语言掌握的人数，获取最大的人数，我们记为 ，那么答案就是 。其中 表示集合 的大小。
时间复杂度 。其中 为语言的数量，而 为好友关系的数量。
class Solution:
def minimumTeachings(
self, n: int, languages: List[List[int]], friendships: List[List[int]]
) -> int:
def check(u: int, v: int) -> bool:
for x in languages[u - 1]:
for y in languages[v - 1]:
if x == y:
return True
return False
s = set()
for u, v in friendships:
if not check(u, v):
s.add(u)
s.add(v)
cnt = Counter()
for u in s:
for l in languages[u - 1]:
cnt[l] += 1
return len(s) - max(cnt.values(), default=0)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidates should be able to identify the need for efficient lookups, especially with hash tables.
- question_mark
A good candidate will propose either the brute force or greedy approach and discuss trade-offs.
- question_mark
Look for understanding of greedy algorithms and optimization strategies when candidates discuss minimizing the number of users.
常见陷阱
外企场景- error
Focusing only on one approach without considering the trade-offs in terms of time complexity.
- error
Neglecting to handle users who already speak a common language, leading to over-counting the number of users to teach.
- error
Forgetting to account for edge cases, such as users who are isolated in the network and don't need any teaching.
进阶变体
外企场景- arrow_right_alt
Extend the problem to handle larger networks, requiring more advanced algorithms to scale efficiently.
- arrow_right_alt
Consider constraints where users can speak multiple languages and need to be taught multiple languages.
- arrow_right_alt
Add additional constraints, such as fixed language choices or a limited number of languages that can be taught.