LeetCode 399. Evaluate Division

Posted on Edited on In 
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
class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        int varCnt = 0;
        unordered_map<string, int> variables;
        const int n = equations.size();
        for (int i = 0; i < n; ++i) {
            if (variables.find(equations[i][0]) == variables.end())
                variables[equations[i][0]] = varCnt++;
            if (variables.find(equations[i][1]) == variables.end())
                variables[equations[i][1]] = varCnt++;
        }
        vector<vector<pair<int, double>>> edges(varCnt);
        for (int i = 0; i < n; ++i) {
            int leftVar = variables[equations[i][0]], rightVar = variables[equations[i][1]];
            edges[leftVar].emplace_back(rightVar, values[i]);
            edges[rightVar].emplace_back(leftVar, 1.0 / values[i]);
        }
        vector<double> ans;
        for (const auto& q : queries) {
            double result = -1.0;
            if (variables.find(q[0]) != variables.end() & variables.find(q[1]) != variables.end()) {
                int leftIndex = variables[q[0]], rightIndex = variables[q[1]];
                if (leftIndex == rightIndex)
                    result = 1.0;
                else {
                    queue<int> points;
                    points.push(leftIndex);
                    vector<double> ratios(varCnt, -1);
                    ratios[leftIndex] = 1.0;
                    vector<bool> visited(varCnt, false);
                    while (!points.empty() && ratios[rightIndex] == -1) {
                        leftIndex = points.front(); points.pop();
                        for (const auto [nextIndex, val] : edges[leftIndex]) {
                            if (ratios[nextIndex] == -1) {
                                ratios[nextIndex] = ratios[leftIndex] * val;
                                points.push(nextIndex);
                            }
                        }
                    }
                    result = ratios[rightIndex];
                }
            }
            ans.push_back(result);
        }
        return ans;
    }
};
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
class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        int varCnt = 0;
        unordered_map<string, int> variables;
        const int n = equations.size();
        for (int i = 0; i < n; ++i) {
            if (variables.find(equations[i][0]) == variables.end())
                variables[equations[i][0]] = varCnt++;
            if (variables.find(equations[i][1]) == variables.end())
                variables[equations[i][1]] = varCnt++;
        }
        vector<vector<double>> graph(varCnt, vector<double>(varCnt, -1.0));
        for (int i = 0; i < n; ++i) {
            int leftVar = variables[equations[i][0]], rightVar = variables[equations[i][1]];
            graph[leftVar][rightVar] = values[i];
            graph[rightVar][leftVar] = 1.0 / values[i];
        }
        for (int k = 0; k < varCnt; ++k)
            for (int i = 0; i < varCnt; ++i)
                for (int j = 0; j < varCnt; ++j)
                    if (graph[i][k] != -1 && graph[k][j] != -1)
                        graph[i][j] = graph[i][k] * graph[k][j];
        vector<double> ans;
        for (const auto& q : queries) {
            double result = -1.0;
            if (variables.find(q[0]) != variables.end() && variables.find(q[1]) != variables.end()) {
                int leftIndex = variables[q[0]], rightIndex = variables[q[1]];
                if (graph[leftIndex][rightIndex] != -1)
                    result = graph[leftIndex][rightIndex];
            }
            ans.push_back(result);
        }
        return ans;
    }
};
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
class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        int varCnt = 0;
        unordered_map<string, int> variables;
        const int n = equations.size();
        for (int i = 0; i < n; ++i) {
            if (variables.find(equations[i][0]) == variables.end())
                variables[equations[i][0]] = varCnt++;
            if (variables.find(equations[i][1]) == variables.end())
                variables[equations[i][1]] = varCnt++;
        }
        vector<int> f(varCnt);
        vector<double> w(varCnt, 1.0);
        for (int i = 0; i < varCnt; ++i)
            f[i] = i;
        for (int i = 0; i < n; ++i) {
            int leftVar = variables[equations[i][0]], rightVar = variables[equations[i][1]];
            merge(f, w, leftVar, rightVar, values[i]);
        }
        vector<double> ans;
        for (const auto& q : queries) {
            double result = -1.0;
            if (variables.find(q[0]) != variables.end() && variables.find(q[1]) != variables.end()) {
                int leftIndex = variables[q[0]], rightIndex = variables[q[1]];
                int fl = findf(f, w, leftIndex), fr = findf(f, w, rightIndex);
                if (fl == fr)
                    result = w[leftIndex] / w[rightIndex];
            }
            ans.push_back(result);
        }
        return ans;
    }
private:
    int findf(vector<int>& f, vector<double>& w, int x) {
        if (x != f[x]) {
            int father = findf(f, w, f[x]);
            w[x] = w[x] * w[f[x]];
            f[x] = father;
        }
        return f[x];
    }
    void merge(vector<int>& f, vector<double>& w, int x, int y, double val) {
        int fx = findf(f, w, x);
        int fy = findf(f, w, y);
        f[fx] = fy;
        w[fx] = val * w[y] / w[x];
    }
};