求用Python教授的最少人数计算项目

求用Python教授的最少人数计算项目

假设我们有一个数字n,一个称为“languages”的数组和一个称为“friendships”的数组,因此有从1到n编号的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,因为我们需要向用户1和3培训语言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

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程