資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
廣告