力扣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] ; }};