LC上一道有趣的并查集題目

1722. 執行交換操作后的最小漢明距離

給你兩個整數陣列 source 和 target ，長度都是 n ，
還有一個陣列 allowedSwaps ，
其中每個 allowedSwaps[i] = [ai, bi] 表示你可以交換陣列 source 中下標為 ai 和 bi（下標從 0 開始）的兩個元素，
注意，你可以按 *******任意 順序 多次******* 交換一對特定下標指向的元素，

相同長度的兩個陣列 source 和 target 間的 *****漢明距離***** 是元素不同的下標數量，
形式上，其值等于滿足 source[i] != target[i] （下標從 0 開始）的下標 i（0 <= i <= n-1）的數量，

在對陣列 source 執行 任意 數量的交換操作后，
回傳 source 和 target 間的 ******最小漢明距離****** ，
(鏈接：https://leetcode-cn.com/problems/minimize-hamming-distance-after-swap-operations)

這里解讀一下題目:

1. 在allowedSwaps[i]里面, 只允許交換source陣列中兩個不同位置的值;
2. 交換的順序和次數都是任意, 說明只要兩個值可以交換, 這兩個值就能交換, 并且交換后不影響其他值的相對位置
3. 漢明距離是指target和source中同一個索引位置, 但值不同的數量
4. 該題是求最小的漢明距離, 因此, 要利用allowedSwaps陣列, 使tager和source中盡可能多的相同值處于相同的位置

解題思路:

1. 并查集：使用并查集, 將allowedSwaps陣列中的索引位置***建立連通分量***，在同一個分量里面的任意兩個索引位置可以***交換任意次***;
2. 使用mapSource<Integer, List>記錄source陣列中的每個值出現的索引位置;
3. 遍歷陣列target,
	（1）當target[i]和source[i]值相同時, 將mapSource中, source[i]對應的i位置洗掉;
	（2）當target[i]和source[i]值不相同時:
		a) 當source陣列中含有target[i]時:
			(a) 遍歷List<Integer> temp = mapSource.get([target[i]]), 找到temp中可交換的索引位置exchange = temp.get(j), 并記錄當前temp中的索引位置j;
			(b) 交換source[i]和source[j]的值;
			(c) 洗掉source[i]在mapSource中的當前所以位置i;
			(d) 更新source[exchange]在mapsource中的位置, 將source[exchange]當前的i值更新為exchange;

JAVA 代碼

      public int minimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) {
        //Map記錄source中的每個值所在的索引位置, 這里有一點, 一個值是可以重復出現的
        Map<Integer,List> mapSource = new HashMap<>();
        for(int i=0;i<source.length;i++){
            if(mapSource.containsKey(source[i])){
                List<Integer> temp = new ArrayList<>(mapSource.get(source[i]));
                temp.add(i);
                mapSource.put(source[i], temp);
            }else {
                List<Integer> temp = new ArrayList<>();
                temp.add(i);
                mapSource.put(source[i], temp);
            }
        }
        //====建立并查集
        int[] UF = new int[source.length];
        for(int i=0;i<UF.length;i++){
            UF[i] = i;
        }
        for(int i=0;i<allowedSwaps.length;i++){
            int val1 = allowedSwaps[i][0];
            int val2 = allowedSwaps[i][1];
            union(UF, val1, val2);
        }
        //====并查集
        int index = 0;
        int exchange = 0;
        int tempVal = 0;
        for(int i=0;i<target.length;i++){
            if(target[i]!=source[i]){
                if(mapSource.containsKey(target[i])){
                    List<Integer> temp = mapSource.get(target[i]);
                    index = -1;
                    exchange = -1;
                    for(int j=0;j<temp.size();j++){
                        if(isConnect(UF, i, temp.get(j))){
                            exchange = temp.get(j);
                            index = j;
                            break;
                        }
                        
                    }
                    if(exchange!=-1){
                        //交換source中索引位置i和exchange對應的值
                        tempVal = source[exchange];
                        source[exchange] = source[i];
                        source[i] = tempVal;
                        //交換后, 洗掉值target[i]在mapSource中的index對應的位置索引
                        temp.remove(index);
                        mapSource.put(target[i], temp);
                        //交換位置后,要更新交換后mapSource中值的對應索引位置, 將source[exchange]對應在mapSource中i的值更新為exchange
                        temp = new ArrayList<>(mapSource.get(source[exchange]));
                        for(int k=0;k<temp.size();k++){
                            if(temp.get(k)==i){
                                temp.set(k, exchange);
                            }
                        }
                        mapSource.put(source[exchange], temp);
                    }
                }
            }else {
                //當前位置的target[i]和source[i]相等時, 洗掉source[i]在mapSource中對應的i值
                List<Integer> temp = new ArrayList<>(mapSource.get(source[i]));
                for(int k=0;k<temp.size();k++){
                    if(temp.get(k)==i){
                        temp.remove(k);
                        break;
                    }
                }
                mapSource.put(source[i], temp);
            }
        }

        int ans = 0;
        for(int i=0;i<source.length;i++){
            if(source[i]!=target[i]){
                ans++;
            }
        }
        return ans;
    }

    private int findParent(int[] UF, int val){
        return UF[val] = UF[val]==val?val:findParent(UF, UF[val]);
    }

    private void union(int[] UF, int val1, int val2){
        int parent1 = findParent(UF, val1);
        int parent2 = findParent(UF, val2);
        UF[parent1] = parent2;
        return ;
    }

    private boolean isConnect(int[] UF, int val1, int val2){
        return findParent(UF, val1)==findParent(UF, val2);
    }

踩過的坑

下面的坑都是我踩過的：

1) 沒看清題目中, 只允許在source中交換兩個不同位置的值，
本人卻交換了target陣列中兩個不同位置的值

2) 題目沒有指定source中的每一個值值出現一次, 處于思想上的懶惰，
一開始當作每個值只出現一次的情況進行解答，
但是, source中, 一個值是可以重復出現的，

3) 一開始，當交換兩個不同位置的值后, 沒有去更新交換后的值對應索引位置，
導致索引位置的延滯性，致使下次交換時的索引位置出錯，
所以，在用map記錄source中的每個值的索引位置時, 
當交換兩個值(source[i]和source[j])的位置后, 
要在map中更新source[i]和source[j]的索引值;

4) 當target[i]和source[i]的值相等時, 
要去map中將值source[i]對應的當前索引位置i洗掉，
否則導致下次交換時的索引位置出錯;