Leetcode 399. Evaluate Division

Jimmy   Feb 25, 2025   659 words   ~20 mins
#Array #String #Depth-First Search #Breadth-First Search #Union Find #Graph #Shortest Path

Table of Contents

題目資訊

  • 題目編號: 399
  • 題目連結: Evaluate Division
  • 主題: Array, String, Depth-First Search, Breadth-First Search, Union Find, Graph, Shortest Path

題目敘述

你有一個變數對的陣列 equations 和一個實數陣列 values，其中 $equations[i] = [A_i, B_i]$ 且 $values[i]$ 代表方程式 $A_i / B_i = values[i]$。每個 $A_i$ 或 $B_i$ 是表示單一變數的字串。

你還有一些 queries，其中 $queries[j] = [C_j, D_j]$ 代表第 $j$ 個查詢，你必須找出 $C_j / D_j = ?$ 的答案。

返回所有查詢的答案。如果無法確定單一答案，則返回 -1.0。

**注意：**輸入總是有效的。你可以假設計算查詢不會導致除以零，且沒有矛盾存在。

**注意：**在方程式列表中不存在的變數是未定義的，因此無法確定它們的答案。

範例 1:

輸入: equations = [[“a”,“b”],[“b”,“c”]], values = [2.0,3.0], queries = [[“a”,“c”],[“b”,“a”],[“a”,“e”],[“a”,“a”],[“x”,“x”]]
輸出: [6.00000,0.50000,-1.00000,1.00000,-1.00000]
解釋:
給定: 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 ]
注意: x 是未定義的 => -1.0

範例 2:

輸入: equations = [[“a”,“b”],[“b”,“c”],[“bc”,“cd”]], values = [1.5,2.5,5.0], queries = [[“a”,“c”],[“c”,“b”],[“bc”,“cd”],[“cd”,“bc”]]
輸出: [3.75000,0.40000,5.00000,0.20000]

範例 3:

輸入: equations = [[“a”,“b”]], values = [0.5], queries = [[“a”,“b”],[“b”,“a”],[“a”,“c”],[“x”,“y”]]
輸出: [0.50000,2.00000,-1.00000,-1.00000]

約束條件:

  • $1 \leq equations.length \leq 20$
  • $equations[i].length == 2$
  • $1 \leq A_i.length, B_i.length \leq 5$
  • $values.length == equations.length$
  • $0.0 < values[i] \leq 20.0$
  • $1 \leq queries.length \leq 20$
  • $queries[i].length == 2$
  • $1 \leq C_j.length, D_j.length \leq 5$
  • $A_i, B_i, C_j, D_j$ 由小寫英文字符和數字組成。

直覺

這個問題涉及根據一些等式來評估除法表達式。等式以變數對的形式給出，並且相關的值表明第一個變數除以第二個變數的結果。查詢要求計算特定除法的結果。該問題可以被有效地轉化為圖論問題，其中變數是節點而除法是有權重的邊。Floyd-Warshall演算法非常適合這個任務，因為它能夠計算出所有節點對之間的最短路徑，讓我們可以基於傳遞關係來確定任意變數對的除法結果。

解法

該解法首先將每個唯一變量映射到一個索引，用以形成一個圖，其中節點代表變量。我們使用鄰接矩陣 grid 來存儲變數之間的除法結果作為邊的權重。在初始化該矩陣時，我們根據給定的等式和其對應的值來填充它。我們對應的矩陣值來同時處理正反關係（即 $A / B$ 和 $B / A$）。

具體方法如下：

  1. 首先，我們使用一個映射為每個變量賦予一個唯一的索引。
  2. 創建一個方形矩陣 grid，使得 grid[i][j] 初始儲存一個很大的值（代表無限），表示尚未知的直接關係。
  3. 用已知的除法結果及其倒數來填充矩陣：
    • 對於每個等式 $A_i / B_i = \text{value}_i$，更新 grid 中對應的值。
    • 對於每個 $i$，我們也將 grid[i][i] 設定為1，代表 $A / A = 1$。
  4. 我們應用Floyd-Warshall演算法來計算通過中介節點的潛在路徑。這涉及迭代所有可能的中介節點 k，並嘗試使用 k 作為中介找到節點 i 和 j 之間較短的路徑（或有效連接）。具體而言，對於每個節點三元組 (i, k, j)，如果存在從 i 到 k 且從 k 到 j 的路徑，並且 grid[i][j] 之前未知，我們將 grid[i][j] 更新為乘積 grid[i][k] * grid[k][j]。
  5. 一旦 grid 完全填充，我們可以通過直接檢索查詢對 (C, D) 的 grid[i][j] 的值來回答查詢。如果其中一個變量不在我們的映射中或 grid[i][j] 保持為無限，則這表示該除法無法計算，我們返回 -1.0。

此解法透過使用預先計算的傳遞關係，有效地回答查詢，且在準備階段後每個查詢的查找時間為常數。

程式碼

C++

#include <vector>
#include <string>
#include <map>
#define MAX 500

class Solution {
public:
    std::vector<double> calcEquation(std::vector<std::vector<std::string>>& equations, 
                                     std::vector<double>& values, 
                                     std::vector<std::vector<std::string>>& queries) {
        int elementIndex = 0;
        std::map<std::string, int> elementMap;

        // 給每個方程式裡的變數分配一個唯一的索引值
        for (int i = 0; i < equations.size(); ++i) {
            if (elementMap.find(equations[i][0]) == elementMap.end()) {
                elementMap[equations[i][0]] = elementIndex++;
            }
            if (elementMap.find(equations[i][1]) == elementMap.end()) {
                elementMap[equations[i][1]] = elementIndex++;
            }
        }
        
        // 初始化一個網格來存儲直接的除法結果
        std::vector<std::vector<double>> grid(elementMap.size(), std::vector<double>(elementMap.size(), MAX));

        // 使用給定的方程式中的已知值填充網格
        for (int i = 0; i < equations.size(); ++i) {
            grid[elementMap[equations[i][0]]][elementMap[equations[i][1]]] = values[i];
            grid[elementMap[equations[i][1]]][elementMap[equations[i][0]]] = 1.0 / values[i];
        }
        
        // 設定任何變數除以自身的結果為1
        for (int i = 0; i < elementMap.size(); ++i) {
            grid[i][i] = 1.0;
        }

        // 應用 Floyd-Warshall 演算法來找到所有點對間的最短路徑
        for (int k = 0; k < elementMap.size(); ++k) {
            for (int i = 0; i < elementMap.size(); ++i) {
                if (grid[i][k] == MAX) continue;
                for (int j = 0; j < elementMap.size(); ++j) {
                    if (grid[k][j] == MAX || grid[i][j] != MAX) continue;
                    grid[i][j] = grid[i][k] * grid[k][j];
                }
            }
        }

        // 回答每個查詢
        std::vector<double> answers(queries.size());
        for (int i = 0; i < queries.size(); ++i) {
            if (elementMap.find(queries[i][0]) == elementMap.end() || 
                elementMap.find(queries[i][1]) == elementMap.end() || 
                grid[elementMap[queries[i][0]]][elementMap[queries[i][1]]] == MAX) {
                answers[i] = -1.0; // 如果查詢無法解決，則返回 -1.0
            } else {
                answers[i] = grid[elementMap[queries[i][0]]][elementMap[queries[i][1]]];
            }
        }

        return answers;
    }
};

Python

class Solution:
    def calcEquation(self, equations, values, queries):
        elementIndex = 0
        elementMap = {}

        # 為每個方程式中的變數分配一個唯一的索引
        for i in range(len(equations)):
            if equations[i][0] not in elementMap:
                elementMap[equations[i][0]] = elementIndex
                elementIndex += 1
            if equations[i][1] not in elementMap:
                elementMap[equations[i][1]] = elementIndex
                elementIndex += 1
        
        # 初始化一個網格來儲存直接的除法結果
        grid = [[float('inf')] * len(elementMap) for _ in range(len(elementMap))]
        
        # 使用給定的方程式填充已知的值到網格中
        for i in range(len(equations)):
            grid[elementMap[equations[i][0]]][elementMap[equations[i][1]]] = values[i]
            grid[elementMap[equations[i][1]]][elementMap[equations[i][0]]] = 1.0 / values[i]
        
        # 設定任何變數與其自身的除法為1
        for i in range(len(elementMap)):
            grid[i][i] = 1.0

        # 應用 Floyd-Warshall 演算法來尋找所有對的最短路徑
        for k in range(len(elementMap)):
            for i in range(len(elementMap)):
                if grid[i][k] == float('inf'):
                    continue
                for j in range(len(elementMap)):
                    if grid[k][j] == float('inf') or grid[i][j] != float('inf'):
                        continue
                    grid[i][j] = grid[i][k] * grid[k][j]

        # 回答每個查詢
        answers = [0.0] * len(queries)
        for i in range(len(queries)):
            if (queries[i][0] not in elementMap or 
                queries[i][1] not in elementMap or 
                grid[elementMap[queries[i][0]]][elementMap[queries[i][1]]] == float('inf')):
                answers[i] = -1.0 # 如果查詢無法解決，則返回-1.0
            else:
                answers[i] = grid[elementMap[queries[i][0]]][elementMap[queries[i][1]]]
        
        return answers

複雜度分析

  • 時間複雜度: 演算法使用修改後的 Floyd-Warshall 方法來計算結果，其時間複雜度為 $O(n^3)$。其中，$n$ 為不同變數的數量，這由 equations 陣列中獨特元素的數量決定。給每個變數分配索引需要 $O(e)$ 時間，其中 $e$ 是方程式的數量。構建初始網格需要 $O(e)$ 時間。Floyd-Warshall 演算法隨後在 $O(n^3)$ 時間內處理此網格。最後，每個查詢在常數時間 $O(1)$ 內解決，因此查詢所需的時間是 $O(q)$，其中 $q$ 是查詢的數量。因此，整體的時間複雜度為 $O(e + n^3 + q)$，在給定的限制條件下可以簡化為 $O(n^3)$（從限制條件推斷，$n$ 至多為 40）。

  • 空間複雜度: 這個解法的空間複雜度為 $O(n^2)$，這是由於儲存所有變數之間可能的直接除法結果的 grid 所造成。此外，儲存變數到索引的映射也需要 $O(n)$ 空間。因此，總體空間複雜度以 $O(n^2)$ 為主。

Disclaimer: All reference materials on this website are sourced from the internet and are intended for learning purposes only. If you believe any content infringes upon your rights, please contact me at csnote.cc@gmail.com, and I will remove the relevant content promptly.


Feedback Welcome: If you notice any errors or areas for improvement in the articles, I warmly welcome your feedback and corrections. Your input will help this blog provide better learning resources. This is an ongoing process of learning and improvement, and your suggestions are valuable to me. You can reach me at csnote.cc@gmail.com.