這道題主要涉及的是對樹的理解，相關的算法是BFS、DFS、並查集。
原題
給出方程式 A / B = k, 其中 A 和 B 均爲代表字符串的變量， k 是一個浮點型數字。根據已知方程式求解問題，並返回計算結果。如果結果不存在，則返回 -1.0。
示例 :
給定 a / b = 2.0, b / c = 3.0 問題: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? 返回 [6.0, 0.5, -1.0, 1.0, -1.0 ]
輸入爲: vector<pair<string, string>> equations, vector<double> values, vector<pair<string, string>> queries(方程式，方程式結果，問題方程式)。 其中 equations.size() == values.size()，即方程式的長度與方程式結果長度相等（程式與結果一一對應），並且結果值均爲正數。以上爲方程式的描述。 返回vector<double>類型。
基于上述例子，輸入如下：
equations(方程式) = [ [“a”, “b”], [“b”, “c”] ], values(方程式結果) = [2.0, 3.0], queries(問題方程式) = [ [“a”, “c”], [“b”, “a”], [“a”, “e”], [“a”, “a”], [“x”, “x”] ].
輸入總是有效的。你可以假設除法運算中不會出現除數爲0的情況，且不存在任何矛盾的結果。
原題url：https://leetcode-cn.com/problems/evaluate-division/
解題
BFS或DFS
一般而言，如果我們知道了a/b和b/c，求a/c的話，可以通過a/b * b/c求得結果。聯想成樹的話，也就是節點與節點之間是否相連。總的來說，我們需要進行關系的轉換。
利用遞歸的話，可以很好寫出代碼，我提供一個 DFS 的例子：
class Solution { public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) { // 記錄出現了哪些字符串 Set<String> keySet = new HashSet<>(); // 記錄等式關系，第一層key爲除數，第二層key爲被除數，第二層value爲結果 Map<String, Map<String, Double>> map = new HashMap<>(); // 當前是第幾個等式，也代表當前要去取第幾個結果 int count = 0; // 遍曆等式 for (List<String> equation : equations) { // 除數 String divisor = equation.get(0); keySet.add(divisor); // 被除數 String divided = equation.get(1); keySet.add(divided); // 結果 double value = values[count]; // 賦值 putValue(value, divisor, divided, map);
count++; } // 計算結果 double[] result = new double[queries.size()]; count = 0; for (List<String> query : queries) { // 除數 String divisor = query.get(0); // 被除數 String divided = query.get(1); // 求結果 result[count] = cal(divisor, divided, map, new HashSet<>(), keySet); count++; }
return result; }
public double cal( String divisor, String divided, Map<String, Map<String, Double>> map, Set<String> divisorSet, Set<String> keySet) { // 但凡除數、被除數有一個不存在，則直接返回-1.0 if (!keySet.contains(divisor) || !keySet.contains(divided)) { return -1.0; } // 根據除數，獲取valueMap Map<String, Double> valueMap = map.get(divisor); // 查找是否有現成結果 Double result = valueMap.get(divided); // 如果有就直接返回 if (result != null) { return result; }
// 沒有就進行計算 for (String key : keySet) { Double value = valueMap.get(key); if (value == null) { continue; } // 如果爲-1.0，說明無法計算 if (value == -1.0) { continue; } // 原本是計算”divisor/divided”，現在可以嘗試求出”divisor/key”和”key/divided” // 如果key的數據已經計算過，則不再重複計算 if (divisorSet.contains(key)) { continue; } divisorSet.add(key); // DFS double tempResult = cal(key, divided, map, divisorSet, keySet); // 記錄中間結果 putValue(tempResult, key, divided, map); // 如果爲-1.0，說明無法計算 if (tempResult == -1.0) { continue; } // 記錄最終結果 putValue(value * tempResult, divisor, divided, map); // 返回結果 return value * tempResult; }
// 說明無法計算 putValue(-1.0, divisor, divided, map); return -1.0; }
public void putValue( double value, String divisor, String divided, Map<String, Map<String, Double>> map) { // 根據除數賦值 Map<String, Double> valueMap = map.get(divisor); if (valueMap == null) { valueMap = new HashMap<>(); map.put(divisor, valueMap); // 記錄”divisor/divisor = 1.0″ valueMap.put(divisor, 1.0); } valueMap.put(divided, value); // 根據被除數賦值 valueMap = map.get(divided); if (valueMap == null) { valueMap = new HashMap<>(); map.put(divided, valueMap); // 記錄”divided/divided = 1.0″ valueMap.put(divided, 1.0); } valueMap.put(divisor, 1.0 / value); } }
提交OK，大家可以嘗試寫一個 BFS(廣度優先搜索) 的版本，需要借用隊列記錄中間遍曆過的節點。
並查集
首先，我們需要了解什麽是並查集，可以參考這一篇博客：https://www.cnblogs.com/noKing/p/8018609.html
我的理解是：當我們知道了一堆元素裏某幾個之間的關聯關系，可以將所有元素歸並到一個集合中，這個集合中所有元素都是有關系的。
雖然並查集在構造時複雜，消耗一定的時間，但它可以提高了查找的效率。
針對這道題目，我們不僅需要記錄 數字 與 數字 之間是否存在關聯，還需要記錄具體的倍數關系。其實你可以簡單理解爲：
當我們知道了： a / b = 3 b / d = 2 c / d = 4 我們可以將 d 看成是根節點，它有子節點 b、c，b有子節點 a
這樣是不是好理解多了。
我是利用一個 HashMap 存儲了節點之間是否關聯，用另一個 HashMap 存儲了節點之間的倍數關系，代碼如下：
class Solution { /** * 並查集 * key : 當前節點 * value : 其父節點(也可以認爲是大哥節點) */ private Map<String, String> parents = new HashMap<>(); /** * 並查集 * key : 當前節點 * value : 父節點(也可以認爲是大哥節點) /當前節點 */ private Map<String, Double> values = new HashMap<>();
private void add(String x) { // 添加節點x if (!parents.containsKey(x)) { parents.put(x, x); values.put(x, 1.0); } }
private void union(String parent, String child, double value) { // 添加節點 add(parent); add(child); // 找到parent和child的最終父節點 String p1 = find(parent); String p2 = find(child); // 如果兩個結果不等 if (!p1.equals(p2)) { // 記錄p1、p2的關系 parents.put(p2, p1); values.put(p2, value * (values.get(parent) / values.get(child))); } }
/** * 找到x的最終父節點 */ private String find(String x) { while (!parents.get(x).equals(x)) { x = parents.get(x); } return x; }
/** * 一直計算到和根節點的關聯 */ private double cal(String x) { double v = values.get(x); while (!parents.get(x).equals(x)) { x = parents.get(x); v *= values.get(x); } return v; }
public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) { // 構建並查集 for (int i = 0; i < equations.size(); i++) { union(equations.get(i).get(0), equations.get(i).get(1), values[i]); } // 最終的結果 double[] answer = new double[queries.size()]; // 計算 for (int i = 0; i < queries.size(); i++) { // 需要計算的兩個數 String c1 = queries.get(i).get(0); String c2 = queries.get(i).get(1); // 如果有一個是不存在的，則沒有計算的必要 if (!parents.containsKey(c1) || !parents.containsKey(c2)) { answer[i] = -1; continue; } // 如果兩者相等，則返回1 if (c1.equals(c2)) { answer[i] = 1; continue; } // 找到兩者的最終父節點，也就是各自的根節點 String p1 = find(c1); String p2 = find(c2); // 如果兩者不等，說明兩個節點無法構成關聯 if (!p1.equals(p2)) { answer[i] = -1; continue; } // 計算兩者的結果 answer[i] = cal(c2) / cal(c1); } return answer; } }
提交OK，我的這個寫法中，並查集是沒有進行路徑壓縮的，有興趣的同學可以在此之上進行優化，這樣當 queries 越大時，查找的效率會越高。
總結
以上就是這道題目我的解答過程了，不知道大家是否理解了。這道題主要涉及的是對樹的理解，相關的算法是BFS、DFS、並查集。
有興趣的話可以訪問我的博客或者關注我的公衆號、頭條號，說不定會有意外的驚喜。
https://death00.github.io/
公衆號：健程之道