寻找用 Python 教授的最少人数的程序
假设我们有一个数字n、一个名为“languages”的数组和一个名为“friendships”的数组,因此有n种语言,从1到n编号,languages[i]表示第i个用户知道的一组语言,而friends[i]持有一对[ui,vi]表示用户ui和vi之间的友谊。我们可以选择一种语言并教给一些用户,这样所有的朋友都可以互相交流。我们必须找到教学所需的最少用户数。(我们必须记住的一件事是,友谊不是可传递的,所以如果x是y的朋友,y是z的朋友,这并不意味着x是z的朋友)。
所以,如果输入是n=3种语言=[[2],[1,3],[1,2],[3]]友谊=[[1,4],[1,2],[3],4],[2,3]],那么输出将是2,因为我们需要为用户1和3训练语言3,因为有两个用户要教,所以输出是2。
示例
让我们看看以下实现以获得更好的理解-
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