本文属于「征服LeetCode」系列文章之一这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁本系列将至少持续到刷完所有无锁题之日为止由于LeetCode还在不断地创建新题本系列的终止日期可能是永远。在这一系列刷题文章中我不仅会讲解多种解题思路及其优化还会用多种编程语言实现题解涉及到通用解法时更将归纳总结出相应的算法模板。为了方便在PC上运行调试、分享代码文件我还建立了相关的仓库。在这一仓库中你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解还可以一同分享给他人。由于本系列文章的内容随时可能发生更新变动欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。给你两个整数数组source和target长度都是n。还有一个数组allowedSwaps其中每个allowedSwaps[i] [ai, bi]表示你可以交换数组source中下标为ai和bi下标从 0 开始的两个元素。注意你可以按任意顺序多次交换一对特定下标指向的元素。相同长度的两个数组source和target间的汉明距离是元素不同的下标数量。形式上其值等于满足source[i] ! target[i]下标从 0 开始的下标i0 i n-1的数量。在对数组source执行任意数量的交换操作后返回source和target间的最小汉明距离。示例 1输入source[1,2,3,4],target[2,1,4,5],allowedSwaps[[0,1],[2,3]]输出1解释source 可以按下述方式转换交换下标 0 和 1 指向的元素source [2,1, 3,4]交换下标 2 和 3 指向的元素source [2,1,4,3]source 和 target 间的汉明距离是 1 二者有 1 处元素不同在下标 3 。示例 2输入source[1,2,3,4],target[1,3,2,4],allowedSwaps[]输出2解释不能对 source 执行交换操作。source 和 target 间的汉明距离是 2 二者有 2 处元素不同在下标 1 和下标 2 。示例 3输入source[5,1,2,4,3],target[1,5,4,2,3],allowedSwaps[[0,4],[4,2],[1,3],[1,4]]输出0提示n source.length target.length1 n 10^51 source[i], target[i] 10^50 allowedSwaps.length 10^5allowedSwaps[i].length 20 ai, bi n - 1ai ! bi方法 建图DFS在a i a_iai​和b i b_ibi​之间连边得到一个无向图G GG。G GG的同一个连通块中的节点下标可以随意交换。求连通块可用BFS、DFS和并查集在线查询时更优。例如s o u r c e sourcesource在某个连通块中的元素为1 , 1 , 2 , 3 1,1,2,31,1,2,3t a r g e t targettarget在这个连通块中的元素为2 , 2 , 4 , 1 2,2,4,12,2,4,1二者有一个共同的1 11和一个共同的2 22。但s o u r c e sourcesource多了一个1 11和一个3 33t a r g e t targettarget多了一个2 22和一个4 44每对多出来的元素无法匹配会贡献1 11个汉明距离。所以这个连通块贡献了2 22个汉明距离。用哈希表或者数组统计s o u r c e sourcesource和t a r g e t targettarget各自多出来的元素个数。总个数除以2 22即为无法配对的元素对的个数即汉明距离。classSolution{publicintminimumHammingDistance(int[]source,int[]target,int[][]allowedSwaps){intnsource.length;ListInteger[]gnewArrayList[n];Arrays.setAll(g,_-newArrayList());for(int[]e:allowedSwaps){intie[0];intje[1];g[i].add(j);// 建图g[j].add(i);}boolean[]visnewboolean[n];intans0;for(intx0;xn;x){if(!vis[x]){MapInteger,IntegerdiffnewHashMap();dfs(x,source,target,g,vis,diff);for(intc:diff.values()){ansMath.abs(c);}}}returnans/2;// 有 ans / 2 对多出来的元素}privatevoiddfs(intx,int[]source,int[]target,ListInteger[]g,boolean[]vis,MapInteger,Integerdiff){vis[x]true;// 避免重复访问// 抵消相同的元素最终剩下 source 和 target 各自多出来的元素对称差diff.merge(source[x],1,Integer::sum);// diff[source[x]];diff.merge(target[x],-1,Integer::sum);// diff[target[x]]--;for(inty:g[x]){if(!vis[y]){dfs(y,source,target,g,vis,diff);}}}}classSolution:defminimumHammingDistance(self,source:List[int],target:List[int],allowedSwaps:List[List[int]])-int:nlen(source)g[[]for_inrange(n)]fori,jinallowedSwaps:g[i].append(j)# 建图g[j].append(i)defdfs(x:int)-None:vis[x]True# 避免重复访问# 抵消相同的元素最终剩下 source 和 target 各自多出来的元素对称差diff[source[x]]1diff[target[x]]-1forying[x]:ifnotvis[y]:dfs(y)vis[False]*n ans0forxinrange(n):ifnotvis[x]:diffdefaultdict(int)dfs(x)anssum(map(abs,diff.values()))returnans//2# 有 ans // 2 对多出来的元素classSolution{public:intminimumHammingDistance(vectorintsource,vectorinttarget,vectorvectorintallowedSwaps){intnsource.size();vectorvectorintg(n);for(autoe:allowedSwaps){intie[0],je[1];g[i].push_back(j);// 建图g[j].push_back(i);}vectorint8_tvis(n);unordered_mapint,intdiff;autodfs[](thisautodfs,intx)-void{vis[x]true;// 避免重复访问// 抵消相同的元素最终剩下 source 和 target 各自多出来的元素对称差diff[source[x]];diff[target[x]]--;for(inty:g[x]){if(!vis[y]){dfs(y);}}};intans0;for(intx0;xn;x){if(!vis[x]){diff.clear();dfs(x);for(auto[_,c]:diff){ansabs(c);}}}returnans/2;// 有 ans / 2 对多出来的元素}};funcminimumHammingDistance(source[]int,target[]int,allowedSwaps[][]int)(ansint){n:len(source)g:make([][]int,n)for_,e:rangeallowedSwaps{i,j:e[0],e[1]g[i]append(g[i],j)// 建图g[j]append(g[j],i)}vis:make([]bool,n)diff:map[int]int{}vardfsfunc(int)dfsfunc(xint){vis[x]true// 避免重复访问// 抵消相同的元素最终剩下 source 和 target 各自多出来的元素对称差diff[source[x]]diff[target[x]]--for_,y:rangeg[x]{if!vis[y]{dfs(y)}}}forx,b:rangevis{if!b{clear(diff)dfs(x)for_,c:rangediff{ansabs(c)}}}returnans/2// 有 ans / 2 对多出来的元素}funcabs(xint)int{ifx0{return-x}returnx}复杂度分析时间复杂度O ( n m ) O(nm)O(nm)其中n nn是s o u r c e sourcesource的长度m mm是a l l o w e d S w a p s allowedSwapsallowedSwaps的长度。空间复杂度O ( n m ) O(nm)O(nm)。相似题目1202. 交换字符串中的元素1722. 执行交换操作后的最小汉明距离3695. 交换元素后的最大交替和