LeetCode---377周赛---Floyd算法+字典树

题目列表

2974. 最小数字游戏

2975. 移除栅栏得到的正方形田地的最大面积

2976. 转换字符串的最小成本 I

2977. 转换字符串的最小成本 II

一、最小数字游戏

这题看懂题意就好，可以结合示例模拟一下，你就会发现规律，本质就是将数组排序，然后将相邻两个数字交换一下即可

代码如下

class Solution {
public:
    vector<int> numberGame(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int n=nums.size();
        for(int i=0;i<n-1;i+=2){
            swap(nums[i],nums[i+1]);
        }
        return nums;
    }
};

?二、移除栏杆得到的正方形田地的最大面积

这题就是单纯暴力求解两个栏杆之间的距离，代码如下

class Solution {
public:
    unordered_set<int> f(vector<int>&a,int mx){
        a.push_back(1);
        a.push_back(mx);
        sort(a.begin(),a.end());
        unordered_set<int>s;
        for(int i=0;i<a.size();i++){
            for(int j=i+1;j<a.size();j++){
                s.insert(a[j]-a[i]);
            }
        }
        return s;
    }
    int maximizeSquareArea(int m, int n, vector<int>& hFences, vector<int>& vFences) {
        auto h=f(hFences,m);
        auto v=f(vFences,n);
        int ans=0;
        for(auto x:h){
            if(v.count(x))
                ans=max(ans,x);
        }
        return ans?1LL*ans*ans%1000000007:-1;
    }
};

?三、转换字符串的最小成本I

这题的关键是你的看出来这是求全源最短路问题，题目要求将source变成target的最小成本，也就是字符之间的相互转换的代价最小，同时，题目允许出现一个字符到另一个字符中间有其他"中转站"的情况，很明显在考Floyd算法，代码如下

class Solution {
public:
    long long minimumCost(string source, string target, vector<char>& original, vector<char>& changed, vector<int>& cost) {
        map<pair<char,char>,int>mp;
        int n=source.size();
        int m=original.size();
        vector<vector<int>>g(26,vector<int>(26,-1));
        for(int i=0;i<m;i++){
            int x=original[i]-'a';
            int y=changed[i]-'a';
            if(g[x][y]==-1) g[x][y]=cost[i];
            else g[x][y]=min(g[x][y],cost[i]);
        }
        
        //Floyd算法
        for(int k=0;k<26;k++){
            for(int i=0;i<26;i++){
                for(int j=0;j<26;j++){
                    if(g[i][k]!=-1&&g[k][j]!=-1){
                        if(g[i][j]==-1) g[i][j]=g[i][k]+g[k][j];
                        else g[i][j]=min(g[i][k]+g[k][j],g[i][j]);
                    }
                }
            }
        }
        
        long long ans=0;
        for(int i=0;i<n;i++){
            if(source[i]!=target[i]){
                int x=source[i]-'a';
                int y=target[i]-'a';                
                if(g[x][y]!=-1) ans+=g[x][y];
                else return -1;
            }
        }
        return ans;
    }
};

四、转换字符串的最小成本II

这题和上一题一样，只是重字符之间的转化，改成了字符串之间的转换，我们依旧是用Floyd算法，但问题是我们如何标识和处理字符串，这里要用到字典树(208. 实现 Trie (前缀树)?标准的字典树模型，不认识的可以先去写这道题)。

同时，这题还需要用到dp，而且题目都帮我们降低难度了，说我们每次修改的区域不能出现重合。

状态定义为dp[i]表示以i为起始位置的字符串从source变成target的最小代价

dp[i]=min( dp[j] + g[i][j] ) 前提是区间[i，j]内的source字符串能变成target对应部分的字符串

代码如下

struct Node{
    Node*child[26]={0};
    int sid=-1;//用来标识字符串，表示以该结点为结尾的字符串序号
};

class Solution {
public:
    long long minimumCost(string source, string target, vector<string>& original, vector<string>& changed, vector<int>& cost) {
        Node*root=new Node();
        int sid=0;
        //字典树
        function<int(string)>put=[&](string s)->int{ 
            Node*node=root;
            for(auto e:s){
                int x=e-'a';
                if(node->child[x]==nullptr)
                    node->child[x]=new Node();
                node=node->child[x];
            }
            if(node->sid==-1)
                node->sid=sid++;
            return node->sid;
        };

        int n=original.size();
        vector<vector<int>>g(2*n,vector<int>(2*n,-1));
        for(int i=0;i<n;i++){
            int x=put(original[i]);
            int y=put(changed[i]);
            if(g[x][y]!=-1) g[x][y]=min(g[x][y],cost[i]);
            else g[x][y]=cost[i];
        }

        for(int k=0;k<sid;k++){
            for(int i=0;i<sid;i++){
                if(g[i][k]==-1) continue;//这行代码能进一步优化时间
                for(int j=0;j<sid;j++){
                    if(g[k][j]!=-1){
                        if(g[i][j]==-1) g[i][j]=g[i][k]+g[k][j];
                        else g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
                    }
                }
            }
        }

        int m=source.size();
        //递归写法
        // vector<long long>memo(m,-1);
        // function<long long(int)>dfs=[&](int i)->long long{
        //     if(i>=m) return 0;
        //     auto& res=memo[i];
        //     if(res!=-1) return res;
        //     res=LLONG_MAX/2;
        //     if(source[i]==target[i])//不要改
        //         res=dfs(i+1);
        //     Node*q=root,*p=root;
        //     for(int j=i;j<m;j++){
        //         q=q->child[source[j]-'a'];
        //         p=p->child[target[j]-'a'];
        //         if(q==nullptr||p==nullptr)
        //             break;
        //         if(q->sid<0||p->sid<0)
        //             continue;
        //         int d=g[q->sid][p->sid];
        //         if(d!=-1)
        //             res=min(res,dfs(j+1)+d);
        //     }
        //     return res;
        // };
        // long long ans = dfs(0);
        // return ans < LLONG_MAX / 2 ? ans : -1;

        //递推写法
        vector<long long>dp(m+1);
        for(int i=m-1;i>=0;i--){
            long long res=LLONG_MAX/2;
            if(source[i]==target[i])//不要改
                res=dp[i+1];
            Node*q=root,*p=root;
            for(int j=i;j<m;j++){
                q=q->child[source[j]-'a'];
                p=p->child[target[j]-'a'];
                if(q==nullptr||p==nullptr)
                    break;
                if(q->sid<0||p->sid<0)
                    continue;
                int d=g[q->sid][p->sid];
                if(d!=-1)
                    res=min(res,dp[j+1]+d);
            }
            dp[i]=res;
        }
        return dp[0]<LLONG_MAX/2?dp[0]:-1;
    }
};