題目描述:給定一組等式 equations(格式為 [Ai, Bi])與對應的值 values(代表 Ai / Bi = values[i]),以及一組查詢 queries(格式為 [Ci, Di]),計算每個查詢 Ci / Di 的結果。若無法確定,回傳 -1.0。
解題思路:將此問題建模為帶權有向圖。對每個等式 A / B = k,建立邊 A → B(權重 k)與反向邊 B → A(權重 1/k)。查詢 C / D 等價於在圖中從 C 走到 D 所經過邊的權重乘積。若 C 或 D 不在圖中,或從 C 無法到達 D,則回傳 -1.0。對每個查詢執行 BFS(或 DFS),從起點出發,累積路徑上的乘積,找到終點時即為答案。BFS 用佇列,記錄 (當前節點, 累積乘積) 與已訪問集合避免循環。
時間複雜度:O((E + V) * Q) — 建圖 O(E),每次 BFS 最壞遍歷所有節點和邊 O(V + E),共 Q 次查詢,其中 E 為等式數、V 為變數數、Q 為查詢數。
空間複雜度:O(V + E) — 圖的鄰接表儲存所有節點與邊;每次 BFS 使用 O(V) 的佇列與已訪問集合。
1. Build a weighted directed graph:
- For each equation [A, B] with value k: add edge A->B (weight k) and B->A (weight 1/k)
2. For each query [C, D]:
a. If C or D not in graph, answer is -1.0
b. If C == D, answer is 1.0
c. BFS from C:
- Queue stores (current_node, accumulated_product), initialized with (C, 1.0)
- Mark C as visited
- While queue not empty:
- Dequeue (node, product)
- For each neighbor of node with edge weight w:
- If neighbor == D, return product * w
- If not visited, enqueue (neighbor, product * w) and mark visited
- If D never reached, return -1.0
3. Collect and return all answers方法一:DFS(深度優先搜尋) 以 DFS 取代 BFS 遍歷圖。從起點遞迴探索所有路徑,累積乘積,找到終點時回傳結果。邏輯與 BFS 相同,但 DFS 使用遞迴棧而非佇列。時間複雜度 O((V+E)*Q),空間複雜度 O(V)(遞迴深度)。BFS 與 DFS 在此題表現相近,DFS 程式碼通常更簡潔。
方法二:帶權 Union-Find(加權並查集)
用並查集維護各節點相對於根節點的比值。合併時更新權重關係;查詢時若兩節點同根,返回權重商。時間複雜度 O((E + Q) * α(V)),幾乎為線性。適合大量查詢的場景,但實作較複雜,需在 find 路徑壓縮時同步更新累積乘積。
方法三:Floyd-Warshall 全對最短路
預先計算所有節點對之間的乘積(如同最短路問題)。建立 V×V 矩陣,初始化已知比值,然後用三重迴圈更新:dist[i][j] = dist[i][k] * dist[k][j](若路徑存在)。預處理 O(V³),之後每次查詢 O(1)。適合 V 小但查詢量極大的情況。
A/B = 2 且 A/B = 3),你的解法會如何處理?如何偵測並回報矛盾?