「leetcode系列」第二十四期 除法求值

題目正文

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

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

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

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

解題思路

從列子上可以看到x / x 為-1 ， 所以未出現的字母，即使是除以本身，這裡也返回 -1

然後利用BFS的算法來求解，具體可以看代碼，並不晦澀。

這裡說明一下，BFS的算法並不是最優解，但卻非常容易理解的方法，如果有感興趣的同學，可以留言回覆更優的解法。

解答

var calcEquation = function(equations, values, queries) {
 var neighbours = {};
 // Initialise the adjacency list!
 for (var e = 0; e < equations.length; e++){
 neighbours[equations[e][0]] = [];
 neighbours[equations[e][1]] = [];
 }
 for (var e = 0; e < equations.length; e++){
 neighbours[equations[e][0]].push([equations[e][1], values[e]]);
 neighbours[equations[e][1]].push([equations[e][0], 1/values[e]]);
 }
 
 res = [];
 for (e of queries){
 res.push(evaluateExpression(e, neighbours))
 }
 return res;
};
function evaluateExpression(expression, neighboursList){
 if (!(expression[0] in neighboursList) || !(expression[1] in neighboursList)) { return -1; }
 if (expression[0] == expression[1]) { return 1; } 
 
 // Initialise with the expression we want to get! We start with the numerator's children in the queue.
 var q = neighboursList[expression[0]].slice();
 var checked = [];
 
 while (q.length > 0){
 //console.log(q, checked)
 var elem = q.shift();
 
 // If our element is part of the expression, then we're done!
 if (elem[0] == expression[1]){ 
 //console.log("DONE")
 return elem[1] 
 }
 checked.push(elem[0]);
 
 // Otherwise add the neighbours to the queue with updated divisors.
 var neighbours = neighboursList[elem[0]];
 for (var n = 0; n < neighbours.length; n++){
 var nextToCheck = neighbours[n];
 if (checked.includes(nextToCheck[0])){ continue ;}
 q.push([nextToCheck[0], nextToCheck[1]*elem[1]])
 }
 }
 
 
 return -1;
}