LeetCode399 除法求值

发表于 | 分类于 |
字数统计: 522 | 阅读时长 ≈ 2

链接： https://leetcode-cn.com/problems/evaluate-division/

题面

给定一串等式除法的式子和计算结果，要求你根据这些式子计算出另一些除法的计算结果，如果无法计算则输出-1

解法

带权并查集。
核心思想是维护子节点与父节点上的权重，作为父节点与子节点的比值
然后每次在查找的时候都会进行路径压缩，更新父节点的同时也会更新权重值
union的时候同样需要根据等式来进行权重的更新
还是常规的并查集的操作，合并两棵树和查找父节点
只是在查找和合并的时候需要进行权重的更新
还需要保留原父节点以便进行更新
实现起来细节比较多，可以结合代码理解

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class Solution {
public:
    map<string, int> index;
    vector<int> par;
    vector<double> weight;
    int find(int i) {
        if (par[i] == i) return i;
        int root = find(par[i]);
        weight[i] *= weight[par[i]];
        return par[i] = root;
    }
    void unions(int a, int b, double val) {
        int pa = find(a);
        int pb = find(b);
        weight[pa] = weight[b] * val / weight[a];
        par[pa] = pb;
    }
    void init(vector<vector<string>>& equations) {
        int n = equations.size();
        par.resize(n * 2);
        weight.resize(n * 2);
        int id = 0;
        for (auto idx: equations) {
            if (index.find(idx[0]) == index.end()) {
                index[idx[0]] = id++;
            }
            if (index.find(idx[1]) == index.end()) {
                index[idx[1]] = id++;
            }
        }
        for (int i = 0; i < id; i++) {
            par[i] = i;
            weight[i] = 1;
        }
    }
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        unordered_map<string, double> val;
        if (equations.size() < 0) {
            return vector<double>(queries.size(), -1);
        }
        int n = equations.size();
        init(equations);
        for (int i = 0; i < n; i++) {
            auto idx = equations[i];
            unions(index[idx[0]], index[idx[1]], values[i]);
        }
        vector<double> ans;
        for (auto idx: queries) {
            string a = idx[0], b = idx[1];
            if (index.find(a) == index.end() || index.find(b) == index.end()) {
                ans.push_back(-1);
            }
            else {
                int pa = index[a], pb = index[b];
                if (find(pa) == find(pb)) {
                    ans.push_back(weight[pa] / weight[pb]);
                }
                else {
                    ans.push_back(-1);
                }
            }
        }
        return ans;
    }
};