用 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 填充
• 对于 0 到 N 范围内的 u，执行
  • if seen[u] 为零，则
    • queue := 队列并插入 u
    • seen[u] := True
    • 对于队列中的每个节点，执行
      • 对于 graph[node] 中的每个 nei，执行
        • 如果 seen[nei] 为 false，则
          • 将 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

相关文章

• Python 中元组列表到字典的转换
• Python - 从两个列表中配对，使得成对的元素不相同
• 使用 Python 和 SQLite 的 SQL
• 使用 pytrie 模块在 Python 中进行前缀匹配
• 创建和访问 Python 包
• 如何使用正则表达式和数据类型选择多个 DataFrame 列
• 如何在 Pandas 中查找和过滤重复行?
• 用 Python 编写程序以正确的顺序查找机场?
• 如何在 Python Pandas 中使用字典顺序切片选择数据子集?
• 用 Python 编写程序检查我们是否可以从给定的字符串字符中创建 k 个回文?

有用资源

• python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/