Leetcode 第 205 场周赛

直接模拟
为啥会写出这种又臭又菜的代码

---

class Solution {
public:
    string modifyString(string s) {
        s += '?';
        string ans="";
        for(int i=0; i<s.size()-1; i++){
            if(i==0){
                if(s[i]!='?')
                    ans += s[i];
                else{
                    for(int j =0; j<26; j++){
                        if('a'+j!=s[i+1]){
                            ans += 'a'+j;
                            break;
                        }
                    }
                }
            }else{
                if(s[i]!='?'){
                    ans += s[i];
                    continue;
                }
                for(int j =0; j<26; j++){
                        if('a'+j!=s[i+1]&&'a'+j!=ans.back()){
                            ans += 'a'+j;
                            break;
                        }
                }
            }
        }
        return ans;
    }
};

反正时间松不会超时，就最暴力的玩把

---

class Solution {
public:
    int numTriplets(vector<int>& nums1, vector<int>& nums2) {
        int ans = 0;
        map<int, int> mmp, mp;
        for(int i=0; i<nums2.size(); i++){
            mmp[nums2[i]] += 1;
        }
        for(int i=0; i<nums1.size(); i++){
            mp.clear();
            for(int j=0; j<nums2.size(); j++){
                mp[nums2[j]] +=1;
                if(((long long)nums1[i]*nums1[i])%nums2[j]!=0)
                    continue;
                else{
                    ans += (mmp[((long long)nums1[i]*nums1[i])/nums2[j]]-mp[((long long)nums1[i]*nums1[i])/nums2[j]]);
                }
            }
        }
        mmp.clear();
        mp.clear();
        for(int i=0; i<nums1.size(); i++){
            mmp[nums1[i]] += 1;
        }
        for(int i=0; i<nums2.size(); i++){
            mp.clear();
            for(int j=0; j<nums1.size(); j++){
                mp[nums1[j]]++;
                if((long long)((long long)nums2[i]*nums2[i])%nums1[j]!=0)
                    continue;
                else{
                    ans += (mmp[((long long)nums2[i]*nums2[i])/nums1[j]]-mp[((long long)nums2[i]*nums2[i])/nums1[j]]);
                }
            }
        }
        return ans;
    }
};

比第一题简单多了，双指针贪心

---

class Solution {
public:
    int minCost(string s, vector<int>& cost) {
        int ans = 0;
        int c = 2147483647;
        int sum = 0;
        int j = 0;
        for(int i=0; i<s.size();){
            c = 0;
            sum = 0;
            while(j<s.size()&&s[j]==s[i]){
                c = max(c, cost[j]);
                sum += cost[j];
                j++;
                
            }
            if(j-i>1){
                cout<<sum-c<<endl;
                ans += sum-c;
               
            }
            i = j;
            if(j==s.size())
                break;
        }
        return ans;
    }
};

直觉就是先用公共的来制造尽量少的连通块，然后各自分别去把连通块联通就可
所以两次并查集就可解决问题，反正不超时

---

class Solution {
public:
    vector<int> fa;
    vector<int> fa1;
    
    int find(int x){
        if(fa[x]==-1)
            return x;
        return fa[x] = find(fa[x]);
    }
    int find2(int x){
        if(fa1[x]==-1)
            return x;
        return fa1[x] = find2(fa1[x]);
    }
    int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {
        //先用第三种边做并查集求连通块
        // 这样计算出了用多少的能用的最省的
        // 然后再看两个人各自去遍历图能否有联通分支
        int cnt = 0;
        int fa2,fa3;
        int cnt2=0;
        int cnt3=0;
        fa = vector<int>(n+5, -1);
        for(auto e:edges){
            if(e[0]==3){
                int fa2=find(e[1]);
                int fa3 = find(e[2]);
                if(fa2==fa3)
                    continue;
                else{
                    cnt ++;
                    fa[fa2]=fa3;
                }
            }
        }
       if(cnt==n-1)
           return edges.size()-cnt;
        fa1 = fa;
        for(auto e:edges){
            if(e[0]==1){
                fa2=find(e[1]);
                fa3 = find(e[2]);
                if(fa2==fa3)
                    continue;
                cnt2 ++;
                fa[fa2]=fa3;
            }
        }
        for(auto e:edges){
            if(e[0]==2){
                fa2=find2(e[1]);
                fa3 = find2(e[2]);
                if(fa2==fa3)
                    continue;
                cnt3 ++;
                fa1[fa2]=fa3;
            }
        }
        if(cnt+cnt2!=n-1||cnt+cnt3!=n-1)
            return -1;
        return edges.size()-cnt-cnt2-cnt3;
    }
};