九章演算法 | Google面試題 : 除法求值

撰文 | JZ

專欄 | 九章演算法

題目描述

現有一些格式為A / B = k的等式，A和B均為字元串變數，k為一個實數（浮點數）。如果能夠找到答案，則返回答案。若答案不存在，則返回-1.0。

樣例

給出等式a / b = 2.0, b / c = 3.0。n問題為a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?。n返回[6.0, 0.5, -1.0, 1.0, -1.0 ]。n輸入為vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries，其中equations.size() == values.size()並且values中均為正數。返回vector<double>。n

equations = [ ["a", "b"], ["b", "c"] ], values = [2.0, 3.0], queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ] n

此外，輸入永遠是有效的，你可以假設所有的除法不會使除數為0，亦不會產生任何衝突。

解題思路分析

1. 首先考慮這道題的難點。難點在於題目中要求的解答大多需要動態的計算。比如題目給出了a / b = 2, b / c = 2，但是題目問的問題卻是a / c。那麼我們對此進行一些思考，找到一些計算的思路。首先，如果兩個變數之間有答案，起碼它們兩個可以被n個等式連起來。比如我上面舉得例子，雖然a和c不能直接被連，但是中間有b作為中間點就可以。想到這裡我們就已經能發現，這個模型已經有點圖論的樣子了。起碼使用圖論能解決連通性的問題（即兩變數間能否有答案）。接下來我們再看看能不能用這個圖進行計算。

2. 我們將每個除數和被除數都可看做圖的頂點，等式的值則可以看成是圖的邊。需要注意的是，這個圖是一個有向圖（因為顯然a / b和b / a的值不同，除非a / b = 1），並且兩點間的兩條邊的值是互為倒數的。然而輸入只給出了一條邊，所以在錄入時要額外添加作為倒數的邊。

3. 這樣我們基本已經建立好了圖的模型，那麼具體的演算法是怎樣的呢。我們繼續思考發現，這是一個很特殊的圖。因為兩點間不管走哪條路徑，距離都是相同的。所以對於每個問題，使用廣搜從起點搜到終點即可。如果廣搜結束都無法走到終點，顯然這兩個變數間就是沒有答案的。在搜索時需要注意的一點是，走過的距離不是常見的相加，而是相乘。

4. 參考程序中的圖使用了鄰接表的存儲形式。如果不用搜索的話，另一種解法是使用鄰接矩陣存儲，如果想求出任何兩個點的最短路徑，那麼可以用Floyd演算法直接算出所有點之間的距離，再依據題目要求返回答案。

參考程序

Evaluate division題解

面試官角度分析

這道題目的難點在於能夠把求值問題轉換為圖的問題。 如果能夠轉換為圖的問題後，那麼其他求路徑的問題也都迎刃而解。這道題唯有轉化為圖上求最路徑的方法才可以拿到Hire.

LintCode相關練習題

Topological sorting

Clone graph

推薦閱讀：