別眨眼網

題目正文

給出方程式 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；}