力扣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 divided 1.0