Python 交換後最大化等價對數量的程式

假設我們有兩個相同長度的數字列表 A 和 B。我們還有一個二維數字列表 C，其中每個元素都是 [i, j] 的形式，這表示我們可以根據需要多次交換 A[i] 和 A[j]。我們必須找到交換後 A[i] = B[i] 的對數最大值。

因此，如果輸入類似於 A = [5, 6, 7, 8]，B = [6, 5, 8, 7]，C = [[0, 1],[2, 3]]，則輸出為 4，因為我們可以交換 A[0] 和 A[1]，然後交換 A[2] 和 A[3]。

為了解決這個問題，我們將遵循以下步驟：

• N := A 的大小
• graph := 透過雙向連線給定邊來建立一個圖。
• ans := 0
• seen := 一個大小為 N 的列表，並填充為 False
• 對於 u 從 0 到 N，執行：
  • 如果 seen[u] 為零，則
    • queue := 一個佇列，並插入 u
    • seen[u] := True
    • 對於佇列中的每個節點，執行：
      • 對於 graph[node] 中的每個鄰居 nei，執行：
        • 如果 seen[nei] 為假，則
          • 將 nei 插入佇列的末尾
          • seen[nei] := True
    • count := 一個對映，包含佇列中所有 i 的 B[i] 元素的計數
    • 對於佇列中的每個 i，執行：
      • 如果 count[A[i]] 不為零，則
        • count[A[i]] := count[A[i]] - 1
        • ans := ans + 1
• 返回 ans

讓我們來看下面的實現，以便更好地理解：

示例

線上演示

from collections import Counter
class Solution:
   def solve(self, A, B, edges):
      N = len(A)
      graph = [[]
      for _ in range(N)]
         for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)
      ans = 0
      seen = [False] * N
      for u in range(N):
         if not seen[u]:
            queue = [u]
            seen[u] = True
            for node in queue:
               for nei in graph[node]:
                  if not seen[nei]:
                     queue.append(nei)
                     seen[nei] = True
            count = Counter(B[i] for i in queue)
            for i in queue:
               if count[A[i]]:
                  count[A[i]] -= 1
            ans += 1
      return ans
ob = Solution()
A = [5, 6, 7, 8]
B = [6, 5, 8, 7]
C = [[0, 1],[2, 3]]
print(ob.solve(A, B, C))

輸入

[5, 6, 7, 8], [6, 5, 8, 7], [[0, 1],[2, 3]]

輸出

4

Arnab Chakraborty

更新於：2020年10月19日

瀏覽量：183

開啟您的 職業生涯

完成課程後獲得認證

開始學習