資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究Python程式：計算不開心朋友的數量
假設我們有一個包含 n（偶數）個不同朋友的偏好列表。對於每個人 i，preferences[i] 包含一個按偏好順序排列的朋友列表。因此，列表中較早的朋友比列表中較晚的朋友更受青睞。每個列表中的朋友由整數 0 到 n-1 編號。所有朋友都分成不同的配對。其中 pairs[i] = [xi, yi] 表示 xi 與 yi 配對，反之亦然。但如果朋友 x 與 y 配對，並且存在另一個朋友 u 也與 v 配對，則朋友 x 不開心 -
- x 更喜歡 u 而不是 y，並且
- u 更喜歡 x 而不是 v。
我們需要找到不開心朋友的數量。
因此，如果輸入類似於 preferences = [[1, 2, 3], [3, 2, 0], [3, 1, 0], [1, 2, 0]] pairs = [[0, 1], [2, 3]]，則輸出將為 2，因為第一個朋友不開心，因為朋友 1 與朋友 0 配對，但更喜歡朋友 3 而不是朋友 0，並且朋友 3 更喜歡朋友 1 而不是朋友 2。朋友 3 不開心，因為朋友 3 與朋友 2 配對，但更喜歡朋友 1 而不是朋友 2，並且朋友 1 更喜歡朋友 3 而不是朋友 0。
為了解決這個問題，我們將遵循以下步驟 -
- graph := 一個鄰接表來建立圖，最初為空
- 對於 pairs 中的每個配對 (s, e)，執行以下操作
- 對於 preferences[s] 中的每個 pref，執行以下操作
- 如果 pref 與 end 相同，則
- 退出迴圈
- graph[s, pref] := 1
- 如果 pref 與 end 相同，則
- 對於 preferences[e] 中的每個 pref，執行以下操作
- 如果 pref 與 start 相同，則
- 退出迴圈
- graph[e, pref] := 1
- 如果 pref 與 start 相同，則
- 對於 preferences[s] 中的每個 pref，執行以下操作
- unhappy := 0
- 對於 pairs 中的每個配對 (s, e)，執行以下操作
- 對於 graph[s] 中的每個 pref，執行以下操作
- 如果 graph[pref][s] 不為空，則
- unhappy := unhappy + 1
- 退出迴圈
- 如果 graph[pref][s] 不為空，則
- 對於 graph[end] 中的每個 pref，執行以下操作
- 如果 graph[pref][e] 不為空，則
- unhappy := unhappy + 1
- 退出迴圈
- 如果 graph[pref][e] 不為空，則
- 對於 graph[s] 中的每個 pref，執行以下操作
- 返回 unhappy
示例
讓我們看看以下實現以獲得更好的理解 -
from collections import defaultdict def solve(preferences, pairs): graph = defaultdict(dict) for start, end in pairs: for pref in preferences[start]: if pref == end: break graph[start][pref] = 1 for pref in preferences[end]: if pref == start: break graph[end][pref] = 1 unhappy = 0 for start, end in pairs: for pref in graph[start]: if graph[pref].get(start, None): unhappy += 1 break for pref in graph[end]: if graph[pref].get(end, None): unhappy += 1 break return unhappy preferences = [[1, 2, 3], [3, 2, 0], [3, 1, 0], [1, 2, 0]] pairs = [[0, 1], [2, 3]] print(solve(preferences, pairs))
輸入
[[1, 2, 3], [3, 2, 0], [3, 1, 0], [1, 2, 0]], [[0, 1], [2, 3]]
輸出
2
更新於: 2021年10月4日
瀏覽量 182
廣告