EvaluateDivision [source code]
public class EvaluateDivision {
static
/****************************************************************************/
class Solution {
Map<String, Set<Edge>> adjlists;
Set<String> visited;
public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
adjlists = new HashMap<> ();
for (int i = 0; i < equations.length; i++) {
String a = equations[i][0], b = equations[i][1];
adjlists.computeIfAbsent (a, s -> new HashSet<> ()).add (new Edge (b, values[i]));
adjlists.computeIfAbsent (b, s-> new HashSet<> ()).add (new Edge (a, 1.0 / values[i]));
}
double[] res = new double[queries.length];
Arrays.fill (res, -1.0);
visited = new HashSet<> ();
for (int i = 0; i < queries.length; i++) {
String a = queries[i][0], b = queries[i][1];
if (adjlists.containsKey (a) && adjlists.containsKey (b)) {
res[i] = dfs (a, b, 1.0);
}
}
return res;
}
double dfs (String src, String target, double path) {
visited.add (src);
double res = -1.0;
if (src.equals (target)) {
res = path;
} else {
for (Edge nei : adjlists.get (src)) {
if (!visited.contains (nei.other)) {
double neret = dfs (nei.other, target, path * nei.weight);
if (neret > 0) {
res = neret;
break;
}
}
}
}
visited.remove (src);
return res;
}
class Edge {
String other;
double weight;
Edge (String o, double w) {
other = o;
weight = w;
}
}
}
/****************************************************************************/
public static void main(String[] args) {
EvaluateDivision.Solution tester = new EvaluateDivision.Solution();
String[][][] inputs = {
{ {"a","b"},{"b","c"} }, { {"a","c"},{"b","c"},{"a","e"},{"a","a"},{"x","x"} },
{{"a", "b"}}, {{"a", "b"}, {"b","a"}},
};
double[][] numbers = {
{2.0,3.0}, {6.0,3.0,-1.0,1.0,-1.0},
{2.0}, {2.0, 0.5},
};
for (int i = 0; i < inputs.length / 2; i++) {
System.out.println (Printer.separator ());
String[][] equations = inputs[2 * i], queries = inputs[2 * i + 1];
double[] values = numbers[2 * i], ans = numbers[2 * i + 1];
double[] output = tester.calcEquation (equations, values, queries);
System.out.printf ("equations:\n%svalues:\t%s\nqueries:\n%s%s\n%s\n",
Matrix.printMatrix (equations), Printer.array (values), Matrix.printMatrix (queries),
Printer.wrap (Printer.array (output), check (output, ans) ? 92 : 91), Printer.array (ans)
);
}
}
static boolean check (double[] a, double[] b) {
if (a.length != b.length)
return false;
for (int i = 0; i < a.length; i++) {
if (Math.abs (a[i] - b[i]) > 10e-5)
return false;
}
return true;
}
}
感觉题目意思很清晰, 也是很自然的就想到用graph来做, 和那个汇率问题是很类似的;
题目给的条件, 有一个包含, 没有contradiction, 这个contradiction估计就是cycle之类的? 这样两个点之间就有不同的path了;
这个题给的node全都是string, 有没有必要搞一个tokennization? 实际上也不难, 之前上ML的时候, 写脚本写了好几次了;
不过这题现在时间紧张, 暂时先不搞这些歪门邪道; don't Premature Optmization;
题目意思既然很清晰, 争取尽可能的写完, 不要浪费时间;
说是问x/x也是合理的, 这个是为什么? 不是没有x吗? 或许是, 如果是unseen node, 自己除自己的无所谓(不考虑等于0的情况), 否则的话, 找不到这个path就没有了;
今天发现一个好玩的东西:
你看, 我现在这样刷题, 把笔记放到旁边的一个小窗口里面去; 这样感觉方便很多; 这样程序文件主窗口就不用动来动去的了; 然后周期性的从这个小窗口把东西往主java文件里面拷就行了;
回到题目:
有一个小坑: 这里这个graph到底是directed还是undirected? 这个其实不重要, 重要的是, 给你的这个equation, 其实你要双向都要保存! 比如给你a/b=2, 那么b/a=0.5你也要保存; 这个是很明显的一个坑;
实际上一个一直没有讨论过的小问题, 就是关于preleaf判断还是leaf的判断, 很多时候其实两个配合使用, 效果也不错; 比如visited这种的prune, 放在pre很多时候比放在leaf的位置要好(尤其是需要print来debug的时候);
而有些特殊的base case, 比如确实是depth要求达到了, 这种实际上好像很多时候放在leaf的位置好一些?
思考的时候不要想太复杂, 尤其是脑子debug这个DFS的时候, 就用一个1个edge或者两个edge的path来帮助思考就行了;
因为是为了帮助应付面试, 我现在开始适当的使用全局变量了; 反正不要太多就行了;
一些不变的, 比如这里的adjlists, 或者是很常规的虽然要更新但是非常常规的结构, 比如visited这种, 我觉得放到全局变量里面, 一般面试官应该不会有太多意见的;
不对, x/x到底应该返回什么? 题面好像并没有明说; OJ试一下; 返回的是-1.0, 所以x/x实际上是不应该给特例的;
这题的visited到底应该怎么维护? 好像不是简单的一个DFS那种visited就行? 应该是维护path!
这个也简单, 改成backtrack写法就行了; 关键是要想到;
比较开心的是居然一次bugfree直接AC了, 比较不开心的是速度很蛇皮: 67(5);
不知道问题出在哪里, 好像也没有专门的string操作啊;
editorial
https://leetcode.com/problems/evaluate-division/discuss/88169/Java-AC-Solution-using-graph
Image a/b = k as a link between node a and b, the weight from a to b is k, the reverse link is 1/k. Query is to find a path between two nodes.
public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
HashMap<String, ArrayList<String>> pairs = new HashMap<String, ArrayList<String>>();
HashMap<String, ArrayList<Double>> valuesPair = new HashMap<String, ArrayList<Double>>();
for (int i = 0; i < equations.length; i++) {
String[] equation = equations[i];
if (!pairs.containsKey(equation[0])) {
pairs.put(equation[0], new ArrayList<String>());
valuesPair.put(equation[0], new ArrayList<Double>());
}
if (!pairs.containsKey(equation[1])) {
pairs.put(equation[1], new ArrayList<String>());
valuesPair.put(equation[1], new ArrayList<Double>());
}
pairs.get(equation[0]).add(equation[1]);
pairs.get(equation[1]).add(equation[0]);
valuesPair.get(equation[0]).add(values[i]);
valuesPair.get(equation[1]).add(1/values[i]);
}
double[] result = new double[queries.length];
for (int i = 0; i < queries.length; i++) {
String[] query = queries[i];
result[i] = dfs(query[0], query[1], pairs, valuesPair, new HashSet<String>(), 1.0);
if (result[i] == 0.0) result[i] = -1.0;
}
return result;
}
private double dfs(String start, String end, HashMap<String, ArrayList<String>> pairs, HashMap<String, ArrayList<Double>> values, HashSet<String> set, double value) {
if (set.contains(start)) return 0.0;
if (!pairs.containsKey(start)) return 0.0;
if (start.equals(end)) return value;
set.add(start);
ArrayList<String> strList = pairs.get(start);
ArrayList<Double> valueList = values.get(start);
double tmp = 0.0;
for (int i = 0; i < strList.size(); i++) {
tmp = dfs(strList.get(i), end, pairs, values, set, value*valueList.get(i));
if (tmp != 0.0) {
break;
}
}
set.remove(start);
return tmp;
}
这个速度就很正常, 4(65);
开头的解释也是很简单的;
好像这题很多人都纠结一个怎么维护edge的问题, 一个方法就是我这样, 我直接自己把一个edge的node和weight给封装起来; 不过最后速度也是很丢人;
他这里的方法, 其实就是自己手动做一个类似assoc list的感觉; 或者说, 反正就是维护两个平行Map;
主函数看完感觉没有什么不同的地方; 他没有使用全局变量;
感觉完全一样的算法, 最后我的慢这么多, 只能解释为封装对速度不利了; 不过为什么呢?
一个教训就是自己要知道这么一个方法的存在, 就是手动维护平行数据结构, 这个在有些BFS里面见得其实已经很多了;
好像还有很多人用这种东西来维护这个graph:
HashMap<String, HashMap<String, Double>> map = new HashMap<String, HashMap<String, Double>>();
这个基本上就是有点踩坑了;
注意我自己实际上写的时候, 是有一点的, 这题实际上是不用特别判断query的两个操作数是否相等的; 我的DFS写法, 自动handle这个问题: 就是因为hit target这个base case我放在leaf位置处理了, 所以最后代码写起来这一点处理的很轻松;
takanashi 10 October 21, 2016 7:32 PMReport
you dont need to add "set.remove(start);"
还有很多人同意; 为什么?
好像是不需要? 这题其实并不是维护path, 只要一个避免cycle就行了; 这种情况下, 对啊, 就好像subset问题那种, 你是要维护path的时候才需要undo; 这题有这个必要吗?
当然有时候确实就是直接用visited来维护path, 但是这题这个visited没有必要这样理解;
就是保证一个DFS不回头, 也就是避免cycle就足够了;
class Solution {
public:
vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
unordered_map<string, Node*> map;
vector<double> res;
for (int i = 0; i < equations.size(); i ++) {
string s1 = equations[i].first, s2 = equations[i].second;
if (map.count(s1) == 0 && map.count(s2) == 0) {
map[s1] = new Node();
map[s2] = new Node();
map[s1] -> value = values[i];
map[s2] -> value = 1;
map[s1] -> parent = map[s2];
} else if (map.count(s1) == 0) {
map[s1] = new Node();
map[s1] -> value = map[s2] -> value * values[i];
map[s1] -> parent = map[s2];
} else if (map.count(s2) == 0) {
map[s2] = new Node();
map[s2] -> value = map[s1] -> value / values[i];
map[s2] -> parent = map[s1];
} else {
unionNodes(map[s1], map[s2], values[i], map);
}
}
for (auto query : queries) {
if (map.count(query.first) == 0 || map.count(query.second) == 0 || findParent(map[query.first]) != findParent(map[query.second]))
res.push_back(-1);
else
res.push_back(map[query.first] -> value / map[query.second] -> value);
}
return res;
}
private:
struct Node {
Node* parent;
double value = 0.0;
Node() {parent = this;}
};
void unionNodes(Node* node1, Node* node2, double num, unordered_map<string, Node*>& map) {
Node* parent1 = findParent(node1), *parent2 = findParent(node2);
double ratio = node2 -> value * num / node1 -> value;
for (auto it = map.begin(); it != map.end(); it ++)
if (findParent(it -> second) == parent1)
it -> second -> value *= ratio;
parent1 -> parent = parent2;
}
Node* findParent(Node* node) {
if (node -> parent == node)
return node;
node -> parent = findParent(node -> parent);
return node -> parent;
}
};
Update:
- Please also check Java solutions below.
- Special thanks to @iambright and @Scarlett_comeup.
比较蛇皮的是还真的有人用UF来做, 我没有想到; 不过地里看面经的时候, 好像确实有人说过这种问题用UF可以? 换个角度, 小岛问题都记得吧, 那些题目都是UF和DFS都可以的; 反正是一个关于connected component的问题;
第一个for循环的操作, 好像是单向的:
并不像是我们之前DFS的时候, 给的一个edge, 两个方向都存了;
第一个for的最后一个else, 对应的是S1和S2都存在的情况; 这种他调用union操作;
这种不借助于数组的UF我其实还是第一次写; 不对, 我根本就没有写过; 本质上其实是理解是一回事的, 毕竟所有这些其实都是mapping: parent就是一个node到一个node之间的mapping, 然后size这些attribute, 你就把这个Map理解为一个查询结构就行了;
union里面, 这个看起来可能有点奇怪:
for (auto it = map.begin(); it != map.end(); it ++)
if (findParent(it -> second) == parent1)
it -> second -> value *= ratio;
这个其实就是P1的所有的child, 都要更改自己的value; 看这个图:
注意看上面这个图, 这个代码最后把这个2的ratio乘的, 是上面这个group的所有的node, 包括P1, 也就是S4;
当然, 最终的目的是, 保证S3和S5的关系满足最后一个edge的要求: 现在是6/2=3了; 但是不要忘了, 同时我们也要尊重联通以前P1的group内部的这些edge关系, 所以给他们所有的一个scaling;
这个思路的想法还是不错的, 而且感觉其实不是很容易想到;
有一个小问题就是感觉复杂度有点炸? 传统的UF能够做到logN的复杂度, 是因为即使是在有rank和path compression的情况下, 最后union的时候, 除了find的cost, 最后唯一需要做的就是改几个指针, 但是这里不一样;
这里首先, 他并没有做rank操作; 其次, 每一次union, 分子所在的整个group都要被遍历. 感觉很姜;
一会儿看看下面有没有人分析复杂度, 这个应该是这个解法无法躲避的一个弱点;
最后一个for循环, 第一个branch判断的是, 要么不存在, 要么不连通, 就返回-1; 否则的话, 就返回一个查询出来的结果;
但是我认为他的这个UF实际上写的不是很好, 除开上面讲的这个各种复杂度的问题, 他还有一个问题就是, 他所有的node的信息, 最后都是存在node自己身上的; 而且你看他主函数也就是处理呢他里面, 还调用了find, 我认为这个是不太好的设计, find我没有记错是不应该暴露给client的操作: 当然他这里也好改, 加一个connected函数就行了, 他调用find的方式非常的简单;
这题确实跟一般的UF有点区别, 没有办法让root来统一存储所有成员的信息; 必须每一个node要保存一点自己的信息; 这个是没有办法的;
我唯一不满的是他union的时候这个遍历操作, 能不能避免?
暂时想不到什么特别好的办法;
iaming 571 September 16, 2016 12:05 PMReport
JAVA, similar idea, but not union-find.
I did considered union-find, but union() for union-find does not provide a good way to traverse the set.
Iterating the whole map does not make it a typical union-find union().
没错, 这个人也意识到这个问题了, union的时候遍历也太蛇皮了;
public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
Map<String, Integer> sets = new HashMap<>();
Map<String, Double> vals = new HashMap<>();
List<List<String>> list = new ArrayList<>();
int nextSetNum = 0;
for (int i = 0; i < equations.length; ++i) {
String a = equations[i][0], b = equations[i][1];
Integer setA = sets.get(a), setB = sets.get(b);
if (setA == null && setB == null) {
sets.put(a, nextSetNum);
sets.put(b, nextSetNum++);
vals.put(a, values[i]);
vals.put(b, 1.0);
list.add(new LinkedList<>(Arrays.asList(a, b)));
} else if (setB == null) {
sets.put(b, setA);
vals.put(b, vals.get(a) / values[i]); // not consider 0.0
list.get(setA).add(b);
} else if (setA == null) {
sets.put(a, setB);
vals.put(a, vals.get(b) * values[i]);
list.get(setB).add(a);
} else if (!setA.equals(setB)) {
double factor = vals.get(a) / values[i] / vals.get(b);
for (String str : list.get(setB)) {
sets.put(str, setA);
vals.put(str, vals.get(str) * factor);
}
}
}
double[] ans = new double[queries.length];
for (int i = 0; i < queries.length; ++i) {
Integer setA = sets.get(queries[i][0]), setB = sets.get(queries[i][1]);
if (setA != null && setA.equals(setB)) ans[i] = vals.get(queries[i][0]) / vals.get(queries[i][1]);
else ans[i] = -1.0;
}
return ans;
}
sets和nextSetNum好像是用来搞tokenization的; 真正面试的时候, 不用一上来就提这个, 就用string做也行; 然后最后做完的时候说一下, 可以用tokenization来进行优化什么的;
List<List<String>> 估计他是想用来做一个int -> list of strings的mapping;
好像是这么一回事, 你看他只有第一个branch用到了这个nextSetsNum这个seed, 然后只有第一个branch有list.add的操作;
大概思路跟之前的那个有点类似, 基本上就是所有新加入进来的node的value, 最后都用一个scaled based on previous value的技巧来计算;
虽然题目要求给的是一些相对的ratio, 但是最后我们整个数据结构里面存储的只能是绝对的value, 这个就是这个题目的一个重要insight;
again, it's not union find. 但是这个思想本身是没有问题的;
连除就是正常的从左到右的计算, 不神奇:
java> 8.0 / 4.0 / 2.0
java.lang.Double res0 = 1.0
java> 1. / 2. / 2.
java.lang.Double res1 = 0.25
他这个vals.get(a) / values[i] / vals.get(b)其实跟上面那个c++写法的是类似的一个计算, 就是value * (a / b); 这个在上面那个图上面也有展示;
哦不对哦, 这里他这个a / v / b, 实际上是不等于v (a / b)的; 应该是(1 / v) (a / b);
最后一个branch, 就是需要merge的时候, setA和setB可以认为是A和B的group ID; 然后这两个不相等, 那么我们现在只能把他们合并到一个group里面;
list里面存的其实是每一个node的undirected neighbor. 所以他这里做的工作就是找到B所有的undirected neighbor, 用factor来更新他们的value, 然后扔到setA对应的group里面去; 这个是对vals的更新, 同时, 他还有对sets的更新, 这个就类似于之前的更新parent links的操作;
forestwn 7 September 28, 2016 5:09 PM
@iambright yes, you are right. They have the same time complexity. But union find is a little faster since it does not copy many times. Based on current test cases, union find uses 0 ms while your solution uses 3ms in C++, however your code is much shorter. :)
反正都不好说, 其实他这个做法跟c++做法的区别在于, c++做法是explicit的维护了很多的node, 然后最后需要scale的时候, 直接对这些node进行操作就行了;
而这里这个java做法, 所有的node都是implicit的(用数字表示), 然后所有的更新都是各种collection数据结构的更新; 最后可能是吃了这个overhead的亏. 不过这个家伙也是睿智, 拿c++的解法跟java的解法比绝对速度有意义吗? 哦不对, 他的意思是他改写过了; 姑且信他的了;
iaming 571 September 28, 2016 4:47 PM
@forestwn you are going to visit each element of one of the set to union and multiply the ratio anyway.
怼回去了; 基本思路还是对的, 最后其实差别应该是collection造成的overhead带来的;
这个人后面还在纠缠, 这个作者没高兴理他了, 我感觉这个fore根本没看懂;
zorro77 33 December 1, 2017 2:51 PM
It seems intuitive to use Union-Find to solve this problem. The idea is that, given a query [a, b], if they share the same root, find out the value of common_root/a and comon_root/b, then the result is (comon_root/b) / (comon_root/a)
class Solution {
public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
if(equations==null || equations.length==0) return new double [] {};
Map<String, String>root=new HashMap<>();
Map<String, Double>map=new HashMap<>();
for (int i=0;i<equations.length;i++){
String x1=equations[i][0], x2=equations[i][1];
root.putIfAbsent(x1, x1);
root.putIfAbsent(x2, x2);
map.putIfAbsent(x1, 1.0);
map.putIfAbsent(x2, 1.0);
String r1=find(root, x1);
String r2=find(root, x2);
root.put(r2, r1);
map.put(r2, map.get(x1)*values[i]/map.get(x2));
}
double[] res=new double[queries.length];
for (int i=0;i<queries.length;i++){
res[i]=-1.0;
String x1=queries[i][0], x2=queries[i][1];
if (!root.containsKey(x1) || !root.containsKey(x2)) continue;
String r1=find(root, x1);
String r2=find(root, x2);
if (r1.equals(r2))
res[i]=get(root, map, x2) / get(root, map, x1);
}
return res;
}
private String find(Map<String, String>root, String var){
if (root.get(var).equals(var)) return var;
return find(root, root.get(var));
}
private double get(Map<String, String>root, Map<String, Double>map, String var){
String r=root.get(var);
double result=map.get(var);
if (r.equals(var)) return result;
return result*get(root, map, r);
}
}
还没有彻底的看懂, 不过大概意思好像是把复杂度往get端推一推?
没有使用tokenization, 读起来方便了一些; root应该就是一个简单的存parent mapping的思路;
这个思路也没有用explicit的node; 直接用数据结构来存这个graph, 比如Map什么的;
他的解释倒是不难理解, 意思就是, a/b = (1/b)/(1/a), 大概是这个意思, 然后用一个公倍数common_root来normalie还是什么的;
对应的, 你看他的tree的上下定义跟前面的答案是不一样的; 他这里, 分子是parent, 然后分母是child; 这样比如我们有a/b=2, 那么他给b存的就是1, 然后给a存的就是2, 然后a还是这个小group的root, 对应的也就是上面说的common_root的概念;
注意他这里的putIfAbsent的使用, 新的edge条件的出现, 不会强制初始化之前的结果;
就看他第一个for循环这里, 你看他R1和R2找到之后, 直接加上一个root[R2]=R1的操作, 这个其实是安全的, 因为如果他俩不相等的话, 那么我们要的就是这个结果, R1吞并R2; 但是如果他俩相等的话, 最后是一个no-op, 因为本来root里面就有类似x -> x这样的条目了; 不对, 只有root才是这样, 而我们这两个讨论的都是root, 所以没问题;
R1应该吞并R2, 对应于上面说的, 分子是分母的parent: 为了帮助记忆, 你可以认为a/b是一个大于1的数字, 那么a就比b大, 这个就好记忆了; 大的数字做parent, 没毛病;
我重新画一个图, 注意这里箭头的方向是跟除号的方向反过来的;
感觉还是没有彻底理解, 假如一开始只有一个x1 / x2 =2, 你得到的是什么? 没错, 简化升级, 先看看base case发生的是什么;
感觉这个做法才是一个真正的完整的针对string的UF做法; 注意, 他这里也没有explicit的node的概念, 最后实际上node的维护还是一个Map搞定的; 没啥问题; 无非是用Map来模拟封装, 这个也是见过很多次了;
用一个简单的例子来看:
可以看到, 这个就是他所谓的, 存的是1/a和1/b这个的意思; 然后你看他最后算query结果的时候, 是直接返回get(b) / get(a). 对应的实际上就是(1/b) / (1/a), 符合之前的结论;
核心逻辑就是他第一个循环最后一句的map.put, 这个更新的实际上, 最后更新的是child的信息, 更新的方式就是图上展示的, 本质上就是按照R1的value来作为基准, 然后scale R2的value;
具体的计算没有去深究了, 反正就是让root来作为基准; 然后所有的child每次来了就是一个反向更新;
这个算法其实很不错的, 没有遍历操作, 而且代码也很简练;
想到把公倍数存在root里面, 其实是挺聪明的; 他注意到了一个点, 如果一个query是有效的, 那么这个query的两个操作数肯定在一个group里面, 贡献一个root; 所以只要你merge的时候操作得当: 一个group里面的所有的node都承认咱们的root, 最后一个group内部的计算就不会出问题;
注意你看他get函数里面,直接用root.get来找root, 其实是没有问题的, 因为他find里面其实也没有实现一个path compression.
把这些都加上的话, 他这个算法就比较完美了;
对了, 少了一点分析, 这种情况:
怎么解释? 这样一个union之后, 他更新的实际上是R2的值;
首先, 还是记住一点, 假如没有这个union的时候, R2这个group, 你随便改R2本身的value, 是没有关系的, 因为group里面所有的其他node的value都是按照同意个基准计算的: R2 / x这样的;
然后现在R1要吞并R2, 那么我们最后只要修改R2的value; 为什么要修改? 因为这个是为了让R2和所有R1之前的child有一个公共对照洗. 比如X1里面本来存的是R1 / X1, 不对, 我说错了, 他每一个node里面存的是1 / X, 然后root存的就是自己的R value;
回来, X1里面存的是1/X1, 然后R1存的是R1, 然后X2存的是1/X2, R2存的是R2;
你想想现在假如要get (X1, X2), 那么我们先get (X1) = (1/X1) R1, get (X2) = (1 / X2) R2 * R1; 这两个一除, 我们希望得到的是
get(X2) / get(X1) = (1/X2) / (1/X1), 那么自然的就得到了...不对啊;
看这个图就知道了, 反正真正自己写代码的时候还是得有个例子:
这个还是可以看出来比较好的例子的; 他这个对R2的修改的这个数值, 实际上是跟他最后get方法的实现是有关系的; 反正最后X2没有修改, 但是R2进行修改, 作为一个链接X2和新的大root R1的中间量; 这个中间量为什么知道这样计算呢? 还不知道怎么回答;
在合并之前, 我们如果get(X2), 得到的是(1/X2) * R2, 然后乘上假如R2和X2中间还有所有其他node的value;
这个值在合并之前用来和R2 group内部的其他的node进行query, 是完全没有问题的;
但是我们现在要合并了; 他这里的设计思路就是, 按理说R2这个group要被吞并了, 很多value都要改变, 但是基于之前说的, root作为一个公倍数的思想, 他就控制, 我就只让R2改变, 其他的value都不改; 因为最后get的时候其实get出来的还是一个path to root上面的所有的node的乘积, 所以对于X2来说, 他现在合并之后新的path, 就是多了一个R1而已;
还是有点绕, 只能结合例子来思考:
这个上面写的还是比较清楚的;
注意你看他的find方式, 如果比如我们X2多了一个child, X3, 最后x3实际上跟直接连在r2上面是没有多大区别的; 因为find的时候(第一个for循环里面的两个find), 直接就找到r2了(说的是r1和r2 union之前); 所以最后就跟x3是x2的sibling差不多的效果; 你可能会说这样怎么保证(x2, x3)这条除法的完整性呢? 前面说过了啊, 因为x2和x3的value都是基于r2计算的, 所以只要他们维护和r2的正确的比例, 最后他们之间的比例也是自然维护的;
看到这里想了想, 这题的find如果加了path compression, 反而会很麻烦; 很难实现;
这个算法就大概先理解到这儿吧, 下面还有一些其他的评论, 感觉都是一些不靠谱的乱搞, 没仔细看了;
后来想了一下, 上面x3这种情况不太合理, 比如你一开始是r2和x2合并, 然后这个时候x3来了, 实际上你看代码, 他会和r2进行操作, 而不是直接连到x2上面去; 所以最后其实跟这里的r1和r2的合并过程是类似的;
UNFINISHED
Problem Description
Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0.
Example:
Given a / b = 2.0, b / c = 3.0.
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? .
return [6.0, 0.5, -1.0, 1.0, -1.0 ].
The input is: vector
According to the example above:
equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].
The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.
Difficulty:Medium
Total Accepted:30.7K
Total Submissions:72.1K
Contributor:LeetCode
Companies
google
Related Topics
graph