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

更新于：2020年10月19日

浏览量：183

开启您的 职业生涯

完成课程后获得认证

开始学习
广告