1722. 执行交换操作后的最小汉明距离

1722. 执行交换操作后的最小汉明距离

并查集

class Solution {
public:
    vector<int>p;
    int find(int x){
        if(p[x]!=x)p[x]=find(p[x]);
        return p[x];
    }

    void merge(int a,int b){
        int ra=find(a),rb=find(b);
        p[ra]=rb;
    }
    int minimumHammingDistance(vector<int>& s, vector<int>& t, vector<vector<int>>& as) {
        int n=s.size();
        p=vector<int>(n);
        for(int i=0;i<n;i++)p[i]=i;

        for(auto v:as){
            int x=v[0],y=v[1];
            merge(x,y);
        }

        map<int,vector<int>>mp;
        for(int i=0;i<n;i++){
            int ra=find(p[i]);
            mp[ra].push_back(i);
        }

        int res=0;

        for(auto i:mp){
            vector<int>v=i.second;
            int l=v.size();
            vector<int>aa(l),bb(l);
            map<int,int>m1,m2;
            for(int i=0;i<l;i++){
                m1[s[v[i]]]++;
                m2[t[v[i]]]++;
            }

            for(auto j:m1){
                res+=min(j.second,m2[j.first]);
            }
        }
        return n-res;
    }
};

跟这个题差不多 1202. 交换字符串中的元素

class Solution {
public:
    vector<int>p;
    int find(int x){
        if(p[x]!=x)p[x]=find(p[x]);
        return p[x];
    }
    void merge(int a,int b){
        int ra=find(a),rb=find(b);
        p[ra]=rb;
    }
    string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
        int n=s.size();
        p.resize(n);
        for(int i=0;i<n;i++)p[i]=i;

        for(auto v:pairs){
            merge(v[0],v[1]);
        }

        map<int,vector<char>>mp;

        for(int i=0;i<n;i++){
            int t=find(i);
            mp[t].push_back(s[i]);
        }

        for(auto &pp:mp){
            auto &v=pp.second;
            sort(v.rbegin(),v.rend());
        }

        for(int i=0;i<n;i++){
            int t=find(i);
            char pos=mp[t].back();
            s[i]=pos;
            mp[t].pop_back();
        }

        return s;
    }
};