圖論進階應用 計算除法的值 Evaluate Division_Leetcode #399 精選75題

ThisisEngineering RAEng on Unsplash

題目敘述

圖目會給定我們一串已知變數作除法的值，以分子在前，分母在後的形式表達。

要求我們針對未知的變數除法作計算，以浮點數的形式返回答案；

如果無解，返回-1.0。

題目的原文敘述

測試範例

Example 1:

Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]
Explanation: 
Given: a / b = 2.0, b / c = 3.0
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? 
return: [6.0, 0.5, -1.0, 1.0, -1.0 ]
note: x is undefined => -1.0

Example 2:

Input: equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
Output: [3.75000,0.40000,5.00000,0.20000]

Example 3:

Input: equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
Output: [0.50000,2.00000,-1.00000,-1.00000]

約束條件

Constraints:

• 1 <= equations.length <= 20

已知的變數除法計算的條件介於1~20之間。

• equations[i].length == 2

equations陣列內每個元素都是一組pair，以分子在前，分母在後的形式表達。

• 1 <= Ai.length, Bi.length <= 5

已知的變數名稱長度最少是一個字元，最長5個字元。

• values.length == equations.length

已知的除法答案 和 給定已知的變數除法計算一樣多。

• 0.0 < values[i] <= 20.0

保證不會有除以零。另外，給定已知變數的除法答案大於0，小於等於20。

• 1 <= queries.length <= 20

動態測試時，提問的除法數目介於1~20之間。

• queries[i].length == 2