数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究Python程序：交换操作后最小化汉明距离
假设我们有两个整数数组 src 和 tgt，它们长度相同。我们还有一个数组 allowedSwaps，其中 allowedSwaps[i] 包含一对 (ai, bi)，表示我们可以交换数组 src 中索引 ai 处的元素与索引 bi 处的元素。(我们可以在任何顺序下对特定索引对的元素进行任意多次交换)。众所周知，两个相同长度数组 src 和 tgt 的汉明距离是元素不同的位置的数量。我们需要找到在对数组 src 执行任意数量的交换操作后，src 和 tgt 的最小汉明距离。
因此，如果输入类似于 src = [2,3,4,5]，tgt = [3,2,5,6]，allowedSwaps = [[0,1],[2,3]]，则输出将为 1，因为 src 可以通过以下方式转换：交换索引 0 和 1，因此 source = [3,2,4,5]，交换索引 2 和 3，因此 source = [3,2,5,4]。此处 src 和 tgt 的汉明距离为 1，因为它们在 1 个位置（索引 3）上不同。
为了解决这个问题，我们将遵循以下步骤：
- graph := 一个与 src 长度相同的列表，并用 n 填充
- 定义一个函数 find()。它将接收 x
- 当 graph[x] 不等于 x 时，执行以下操作：
- graph[x] := graph[graph[x]]
- x := graph[x]
- 返回 x
- 定义一个函数 union()。它将接收 x, y
- x1 := find(x), y1 := find(y)
- graph[x1] := y1
- 从主方法开始，执行以下操作：
- 对于 allowedSwaps 中的每个对 (x, y)，执行以下操作：
- union(x, y)
- groups := 一个映射，其中值是列表，默认情况下列表为空
- 对于从 0 到 src 大小 - 1 的每个 i，执行以下操作：
- i1 := find(i)
- 将 i 插入到 groups[i1] 的末尾
- ans := 0
- 对于 groups 所有值的列表中的每个 ids，执行以下操作：
- counter := 一个空映射，用于保存计数值
- 对于 ids 中的每个 idx，执行以下操作：
- counter[src[idx]] := counter[src[idx]] + 1
- counter[tgt[idx]] := counter[tgt[idx]] - 1
- ans := ans + (counter 所有值的绝对值的总和) / 2
- 返回 ans
示例
让我们查看以下实现以更好地理解：
from collections import defaultdict, Counter def solve(src, tgt, allowedSwaps): graph = [ n for n in range(len(src)) ] def find(x): while graph[x] != x: graph[x] = graph[graph[x]] x = graph[x] return x def union(x, y): x1, y1 = find(x), find(y) graph[x1] = y1 for x, y in allowedSwaps: union(x,y) groups = defaultdict(list) for i in range(len(src)): i1 = find(i) groups[i1].append(i) ans = 0 for ids in groups.values(): counter = Counter() for idx in ids: counter[src[idx]] += 1 counter[tgt[idx]] -= 1 ans += sum( abs(val) for val in counter.values())/2 return ans src = [2,3,4,5] tgt = [3,2,5,6] allowedSwaps = [[0,1],[2,3]] print(solve(src, tgt, allowedSwaps))
输入
[2,3,4,5], [3,2,5,6], [[0,1],[2,3]]
输出
1
更新于: 2021年10月6日
234 次查看
广告