数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究Python程序：查找教授课程所需的最小人数
假设我们有一个数字n，一个名为“languages”的数组和一个名为“friendships”的数组，因此有n种语言，编号从1到n，“languages[i]”表示第i个用户知道的语言集，“friendships[i]”包含一对[ui, vi]，表示用户ui和vi之间的友谊关系。我们可以选择一种语言并教授给一些用户，以便所有朋友都可以互相交流。我们必须找到需要教授的最小用户数。（有一点需要注意的是，友谊关系不是传递的，所以如果x是y的朋友，y是z的朋友，这并不意味着x是z的朋友）。
因此，如果输入类似于n = 3 languages = [[2],[1,3],[1,2],[3]] friendships = [[1,4],[1,2],[3,4],[2,3]]，则输出将为2，因为我们需要训练语言3给用户1和3，因为有两个用户需要教授，所以输出为2。
为了解决这个问题，我们将遵循以下步骤：
- lang := 所有用户已知语言的不同集合的列表
- not_comm := 一个新的集合
- 对于friendships中的每一对a, b，执行以下操作：
- a := a - 1
- b := b - 1
- 如果lang[a]和lang[b]是不相交的，则
- 将a插入not_comm
- 将b插入not_comm
- 如果not_comm为空，则
- 返回0
- cnt := 一个空映射
- 对于not_comm中的每个人，执行以下操作：
- 存储lang[person]的频率并将其存储到cnt中
- temp := cnt所有值的列表中的最大值
- 返回not_comm的大小 - temp
示例
让我们看看以下实现以获得更好的理解：
from collections import Counter def solve(n, languages, friendships): lang = [set(L) for L in languages] not_comm = set() for a,b in friendships: a -= 1 b -= 1 if lang[a].isdisjoint(lang[b]): not_comm.add(a) not_comm.add(b) if not not_comm: return 0 cnt = Counter() for person in not_comm: cnt.update(lang[person]) temp = max(cnt.values()) return len(not_comm) - temp n = 3 languages = [[2],[1,3],[1,2],[3]] friendships = [[1,4],[1,2],[3,4],[2,3]] print(solve(n, languages, friendships))
输入
3, [[2],[1,3],[1,2],[3]], [[1,4],[1,2],[3,4],[2,3]]
输出
2
更新于: 2021年10月7日
138 次查看
广告