這道題主要涉及的是對樹的理解，相關的算法是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/
公衆號：健程之道