Cinte's Leetcode Record
0%

399. 除法求值

Posted on Edited on In Disqus:
Symbols count in article: 1.7k Reading time ≈ 2 mins.

399. 除法求值

直接看解析

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
66
67
68
69
70
71
72
73
class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        unordered_map<string, int> map;
        UnionFind uf(equations.size() * 2);
        int id = 0;
        for(int i = 0; i < equations.size(); ++i)
        {
            auto a = equations[i][0];
            auto b = equations[i][1];
            if(map.emplace(a, id).second)
                ++id;
            if(map.emplace(b, id).second)
                ++id;
            
            uf.doUnion(map[a], map[b], values[i]);
        }
        vector<double> ret;
        for(auto& query : queries)
        {
            if(map.find(query[0]) != map.end() && map.find(query[1]) != map.end())
                // map如果其中不包含值会初始化为0，因此这里需要先判断
                ret.push_back(uf.isConnect(map[query[0]], map[query[1]]));
            else
                ret.push_back(-1.0);
        }
        return ret;
    }
private:
    class UnionFind {
        public:
            UnionFind(int size) : parent(vector<int>(size)), weights(vector<double>(size, 1.0))
            {
                for(int i = 0; i < size; ++i)
                    parent[i] = i;
            }
			// 归并，如果已经连接了，那就算了，如果没有连接，由于他们出现在同一式中，因此必定可以建立连接。如果他们的根没有连接那就计算一下然后连接，在find操作时会执行路径压缩
            void doUnion(int x, int y, double val)
            {
                int rootX = find(x);
                int rootY = find(y);
                if(rootX == rootY)
                    return;
                parent[rootX] = rootY;
                weights[rootX] = weights[y] * val / weights[x];
            }
			// 如果连在同一个父节点就是有值
            double isConnect(int x, int y)
            {
                int rootX = find(x);
                int rootY = find(y);
                if(rootX == rootY)
                    return weights[x] / weights[y];
                else
                    return -1.0;
            }
        private:
            vector<int> parent;
            vector<double> weights;
        private:
        	// 寻找父节点顺便路径压缩
            int find(int x)
            {
                if(x != parent[x])
                {
                    int ori = parent[x];
                    parent[x] = find(parent[x]);
                    weights[x] *= weights[ori];
                }
                return parent[x];
            }
    };
};