[LeetCode] 399. Evaluate Division

本文主要是介绍[LeetCode] 399. Evaluate Division，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题：https://leetcode.com/problems/evaluate-division/

题目大意

给定 equations 和式子结果 values ，求 queries 的结果。

思路

dfs

先构建一个图。
queries 是两点之间边的权重乘积。

class Solution {double dfs(List<Double> resList,Map<String,Map<String,Double>> map,Set<String> hasVistedSet,String os,String ds){if(os.equals(ds))return 1;Map<String,Double> curmap = map.get(os);for(Map.Entry<String,Double> entry:curmap.entrySet()){if(hasVistedSet.contains(entry.getKey())) continue;hasVistedSet.add(entry.getKey());double nextPart = dfs(resList,map,hasVistedSet,entry.getKey(),ds);if(nextPart>0)return entry.getValue() * nextPart;}return -1;}public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {Map<String,Map<String,Double>> map = new HashMap();for(int i =0 ; i < equations.length;i++){String[] equation = equations[i];if(!map.containsKey(equation[0]))map.put(equation[0],new HashMap());map.get(equation[0]).put(equation[1],values[i]);if(!map.containsKey(equation[1]))map.put(equation[1],new HashMap());map.get(equation[1]).put(equation[0],1/values[i]);}List<Double> resList = new ArrayList<>();for(String[] query:queries){String os = query[0];String ds = query[1];if(!map.containsKey(os))resList.add(-1.0);elseresList.add(dfs(resList,map,new HashSet(),os,ds));}double[] resArr = new double[resList.size()];int i = 0;for(double res:resList){resArr[i++] = res;}return resArr;}
}

并查集

将所有数化为一个基数的倍数。

class BaseNumPair{String baseNum;double ratio;public BaseNumPair(String baseNum,double ratio){this.baseNum = baseNum;this.ratio = ratio;}
}class UnionFindSet{Map<String,BaseNumPair> map = new HashMap();BaseNumPair find(String s){if(!map.containsKey(s))return null;BaseNumPair tBaseNumPair = map.get(s);if(!tBaseNumPair.baseNum.equals(s)){BaseNumPair nBaseNumPair = find(tBaseNumPair.baseNum);tBaseNumPair.baseNum = nBaseNumPair.baseNum;tBaseNumPair.ratio = tBaseNumPair.ratio * nBaseNumPair.ratio;}return tBaseNumPair;}void union(String s,String p,double ratio){boolean hasMapS = map.containsKey(s);boolean hasMapP = map.containsKey(p);if(!hasMapS&&!hasMapP){map.put(s,new BaseNumPair(p,ratio));map.put(p,new BaseNumPair(p,1));}else if(!hasMapS){map.put(s,new BaseNumPair(p,ratio));}else if(!hasMapP){map.put(p,new BaseNumPair(s,1/ratio));}else{BaseNumPair sBaseNumPair = find(s);BaseNumPair pBaseNumPair = find(p);BaseNumPair rSBaseNumPair = map.get(sBaseNumPair.baseNum);BaseNumPair rPBaseNumPair = map.get(pBaseNumPair.baseNum);rSBaseNumPair.baseNum = rPBaseNumPair.baseNum;rSBaseNumPair.ratio =  ratio * pBaseNumPair.ratio / sBaseNumPair.ratio;}}
}class Solution {    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {UnionFindSet unionfindSet = new UnionFindSet();for(int i = 0 ; i < equations.length ;i++){unionfindSet.union(equations[i][0],equations[i][1],values[i]);}double[] res = new double[queries.length];int i = 0;for(String[] query:queries){BaseNumPair sBaseNumPair = unionfindSet.find(query[0]);BaseNumPair pBaseNumPair = unionfindSet.find(query[1]);if(sBaseNumPair==null || pBaseNumPair==null || !sBaseNumPair.baseNum.equals(pBaseNumPair.baseNum)){res[i++] = -1;}else{res[i++] = sBaseNumPair.ratio/pBaseNumPair.ratio;}}return res;}
}