leetcode-399

LeetCode 399. 除法求值

1 题目描述

• 题目链接：399. 除法求值

给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。

另有一些以数组 queries 表示的问题，其中 queries[j] = [Cj, Dj] 表示第 j 个问题，请你根据已知条件找出 Cj / Dj = ? 的结果作为答案。

返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -1.0 替代这个答案。

注意：输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。

示例1：

输入: equations = [[“a”,”b”],[“b”,”c”]], values = [2.0,3.0], queries = [[“a”,”c”],[“b”,”a”],[“a”,”e”],[“a”,”a”],[“x”,”x”]]
输出: [6.00000,0.50000,-1.00000,1.00000,-1.00000]
解释:
条件：a / b = 2.0, b / c = 3.0
问题：a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
结果：[6.0, 0.5, -1.0, 1.0, -1.0 ]

示例2：

输入: equations = [[“a”,”b”],[“b”,”c”],[“bc”,”cd”]], values = [1.5,2.5,5.0], queries = [[“a”,”c”],[“c”,”b”],[“bc”,”cd”],[“cd”,”bc”]]
输出: [3.75000,0.40000,5.00000,0.20000]

示例3：

输入: equations = [[“a”,”b”]], values = [0.5], queries = [[“a”,”b”],[“b”,”a”],[“a”,”c”],[“x”,”y”]]
输出: [0.50000,2.00000,-1.00000,-1.00000]

提示:

• 1 <= equations.length <= 20
• equations[i].length == 2
• 1 <= Ai.length, Bi.length <= 5
• values.length == equations.length
• 0.0 < values[i] <= 20.0
• 1 <= queries.length <= 20
• queries[i].length == 2
• 1 <= Cj.length, Dj.length <= 5
• Ai, Bi, Cj, Dj 由小写英文字母与数字组成

2 思路

  这道题实际上是带权值的有向图，因此首先需要建图；其次，我们希望通过已有的条件来计算queries中的式子，那么就需要知道图中的顶点间是否可以连通，即是否可以通过若干次已知运算，得到queries[i]的结果，那么可以想到用并查集的方法，如果queries[i]中分子分母同属于一个连通块，则说明可以通过计算来得到其结果，否则无法进行计算，因而将其结果视为-1.0。

  此外，由于每个等式的分子分母都是string类型，要获得它在图中对应的顶点编号，那么采用哈希表的方式来获取，也就是首先创建一个map，然后将分子分母分别存到map中，其值为一个从0开始递增的整数，也就是实现string和int的映射，方便后续取编号以及判断queries[i]的分子分母是否在equations[i]中出现过，没出现就必然算不出结果，也就是-1.0，有我们才进行计算。

  那么，怎么在图中查询queries[i]的结果呢？我们可以采用bfs的方式来搜索，以分子为起点，分母为终点来进行搜索，搜索过程中实时计算每一步的结果(通过图的权值进行计算)，最后返回对应的结果即可。

  总结一下，其实就是哈希实现string到int的映射，得到每个变量对应的索引；建图，实现两个不同变量构成的等式关系，其中邻接矩阵的值为权值；并查集查询变量间是否可以进行通过转换得到结果；BFS用来求最终的计算结果。

class Solution {
    vector<int> fa;
    vector<int> rank;
    vector<vector<double>> edges;
    unordered_map<string, int> hash;
    int cnt;
    int find(int x) {
        return fa[x] == x ? x : (fa[x] = find(fa[x]));
    }
    void merge(int x, int y) {
        int fx = find(x), fy = find(y);
        if(fx != fy) {
            if(rank[fx] >= rank[fy]) 
                fa[fy] = fx;
            else 
                fa[fx] = fy;
            if(rank[fx] == rank[fy])    ++rank[fx];
        }
    }
    double getVal(int x, int y) {
        if(find(x) != find(y))  return -1.0;
        else if(x == y) return 1.0;
        queue<int> q;
        q.emplace(x);
        vector<double> result(cnt, 1.0);
        vector<bool> vis(cnt, false);
        while(!q.empty()) {
            int cur = q.front();
            q.pop();
            for(int i = 0; i < cnt; ++i) {
                if(edges[cur][i] == 0.0 || vis[i])    continue;
                q.emplace(i);
                result[i] = result[cur] * edges[cur][i];
                vis[i] = true;
            }
        }
        return result[y];
    }
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        cnt = 0;
        for(auto vec: equations) {
            if(hash.find(vec[0]) == hash.end()) 
                hash[vec[0]] = cnt++;
            if(hash.find(vec[1]) == hash.end())
                hash[vec[1]] = cnt++;
        }
        edges = vector<vector<double>> (cnt, vector<double>(cnt, 0.0));
        fa.resize(cnt);
        rank = vector<int> (cnt, 0);
        for(int i = 0; i < cnt; ++i)  fa[i] = i;
        int n = equations.size();
        for(int i = 0; i < n; ++i) {
            int j = hash[equations[i][0]], k = hash[equations[i][1]];
            merge(j, k);
            edges[j][k] = values[i], edges[k][j] = 1.0 / values[i];
        }
        vector<double> ret;
        for(auto it: queries) {
            if(!hash.count(it[0]) || !hash.count(it[1])) {
                ret.emplace_back(-1.0);
            }else {
                int j = hash[it[0]], k = hash[it[1]];
                ret.emplace_back(getVal(j, k));
            }
        }
        return ret;
    }
};