力扣399.除法求值

力扣399.除法求值

• 带权并查集

  • w存每个节点与根节点的比值
  • 带权并查集的路径压缩写法
  • 连接两连通块的写法

•   class Solution {
        int p[30];
        double w[30];
    public:
        vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
            int n = equations.size();
            unordered_map<string,int> mp;
            //每种字母给一个编号 顺便记录字母总数
            int s = 0;
            for(int i=0;i<n;i++)
            {
                if(mp.find(equations[i][0]) == mp.end())
                    mp[equations[i][0]] = s ++;
                if(mp.find(equations[i][1]) == mp.end())
                    mp[equations[i][1]] = s ++;
            }
            for(int i=0;i<s;i++) p[i] = i , w[i] = 1.0;
            for(int i=0;i<n;i++)
            {
                //取出两编号 合并并查集
                int va = mp[equations[i][0]] ,vb = mp[equations[i][1]];
                merge(va,vb,values[i]);
            }
            vector<double> ans;
            for(const auto& q:queries)
            {
                double res = -1.0;
                if(mp.find(q[0]) != mp.end() && mp.find(q[1]) != mp.end())
                {
                    int na = mp[q[0]] ,nb = mp[q[1]];
                    int fa = find(na),fb = find(nb);
                    //同一个并查集 有关系
                    if(fa == fb)
                        res = w[na]/w[nb];
                }
                ans.emplace_back(res);
            }
            return ans;
        }
        
        int find(int x)
        {
            if(p[x] != x) 
            {
                int f = find(p[x]);
                //需要路径压缩时，w[x]存在是到父节点的值而不是根节点
                w[x] = w[x] * w[p[x]];
                p[x] = f;
            }
            return p[x];
        }
        
        void merge(int x,int y,double val){// 合并集合
            int fx = find(x) , fy = find(y) ;
            p[fx] = fy ;
            //v[x]/v[y] = k, w[fx] = k * w[y]/w[x];
            w[fx] = val * 1.0 * w[y] / w[x] ;   
        }
    };
  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