力扣399——除法求值

這道題主要涉及的是對樹的理解，相關的算法是BFS、DFS、並查集。

原題

給出方程式 A / B = k, 其中 A 和 B 均為代表字符串的變量， k 是一個浮點型數字。根據已知方程式求解問題，並返回計算結果。如果結果不存在，則返回 -1.0。

示例 :

<code>給定 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
string, 
string
>> equations, 
vector
<
double
> values, 
vector
string, 
string
>> queries(方程式，方程式結果，問題方程式)。
其中 equations.size() == values.size()，即方程式的長度與方程式結果長度相等（程式與結果一一對應），並且結果值均為正數。以上為方程式的描述。
返回
vector
 
<
double
>類型。/<code>

基於上述例子，輸入如下：

<code>equations(方程式) = [ [
"a"
, 
"b"
], [
"b"
, 
"c"
] ],
values
(方程式結果) = [
2.0
, 
3.0
],
queries(問題方程式) = [ [
"a"
, 
"c"
], [
"b"
, 
"a"
], [
"a"
, 
"e"
], [
"a"
, 
"a"
], [
"x"
, 
"x"
] ]. /<code>

輸入總是有效的。你可以假設除法運算中不會出現除數為0的情況，且不存在任何矛盾的結果。

原題url：https://leetcode-cn.com/problems/evaluate-division/

解題

BFS或DFS

一般而言，如果我們知道了a/b和b/c，求a/c的話，可以通過a/b * b/c求得結果。聯想成樹的話，也就是節點與節點之間是否相連。總的來說，我們需要進行關係的轉換。

利用遞歸的話，可以很好寫出代碼，我提供一個 DFS 的例子：

<code>
class
 
Solution
 {
    
public
 
double
[] 
calcEquation
(
List> equations, 
double
[] values, List> queries) {
         
        Set keySet = 
new
 HashSet<>();
         
        Map> map = 
new
 HashMap<>();
         
        
int
 count = 
0
;
         
        
for
 (List 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 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> map,
        Set divisorSet,
        Set keySet
) {
         
         
if
 (!keySet.contains(divisor) || !keySet.contains(divided)) {
            
return
 
-1.0
;
        }
         
        Map 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
;
            }
             
            
if
 (
value
 == 
-1.0
) {
                
continue
;
            }
             
             
            
if
 (divisorSet.contains(key)) {
                
continue
;
            }
            divisorSet.
add
(key);
                         
            
double
 tempResult = cal(key, divided, map, divisorSet, keySet);
             
            putValue(tempResult, key, divided, map);
             
            
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> map) {
         
        Map valueMap = map.
get
(divisor);
        
if
 (valueMap == 
null
) {
            valueMap = 
new
 HashMap<>();
            map.put(divisor, valueMap);
             
            valueMap.put(divisor, 
1.0
);
        }
        valueMap.put(divided, 
value
);
         
        valueMap = map.
get
(divided);
        
if
 (valueMap == 
null
) {
            valueMap = 
new
 HashMap<>();
            map.put(divided, valueMap);
             
            valueMap.put(divided, 
1.0 
);
        }
        valueMap.put(divisor, 
1.0
 / 
value
);
    }
}/<code>

提交OK，大家可以嘗試寫一個 BFS(廣度優先搜索) 的版本，需要借用隊列記錄中間遍歷過的節點。

並查集

首先，我們需要了解什麼是並查集，可以參考這一篇博客：https://www.cnblogs.com/noKing/p/8018609.html

我的理解是：當我們知道了一堆元素裡某幾個之間的關聯關係，可以將所有元素歸併到一個集合中，這個集合中所有元素都是有關係的。

雖然並查集在構造時複雜，消耗一定的時間，但它可以提高了查找的效率。

針對這道題目，我們不僅需要記錄 數字 與 數字 之間是否存在關聯，還需要記錄具體的倍數關係。其實你可以簡單理解為：

<code>
當我們知道了：
a
 
/ b = 3
b
 
/ d = 2 

c
 
/ d = 4
  
d 看成是根節點，它有子節點 b、c，b有子節點 a
/<code>

這樣是不是好理解多了。

我是利用一個 HashMap 存儲了節點之間是否關聯，用另一個 HashMap 存儲了節點之間的倍數關係，代碼如下：

<code>
class
 
Solution
 {
     
    
private
 Map parents = 
new
 HashMap<>();
     
    
private
 Map values = 
new
 HashMap<>();

    
private
 
void
 
add
(
String 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);
         
        String p1 = find(parent);
        String p2 = find(child);
         
        
if
 (!p1.
equals
(p2)) {
             
            parents.put(p2, p1);
            values.put(p2, 
value
 * (values.
get
(parent) / values.
get
(child)));
        }
    }

     
    
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> equations, 
double
[] values, List> 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
;
            }
             
            
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;
    }
}/<code>

提交OK，我的這個寫法中，並查集是沒有進行路徑壓縮的，有興趣的同學可以在此之上進行優化，這樣當 queries 越大時，查找的效率會越高。

總結

以上就是這道題目我的解答過程了，不知道大家是否理解了。這道題主要涉及的是對樹的理解，相關的算法是BFS、DFS、並查集。

有興趣的話可以訪問我的博客或者關注我的公眾號、頭條號，說不定會有意外的驚喜。

https://death00.github.io/

關鍵字: value 力扣 divisor