399. Evaluate Division

Medium
Description

給定方程式 equations 和對應的值 values，其中 equations[i] = [A, B] 且 values[i] = A / B。回答查詢 queries[i] = [C, D]，即 C / D 的值。若無法求得，回傳 -1.0。

Example:

Input: equations = [[“a”,“b”],[“b”,“c”]], values = [2.0,3.0], queries = [[“a”,“c”],[“b”,“a”],[“a”,“e”],[“a”,“a”],[“x”,“x”]] Output: [6.0,0.5,-1.0,1.0,-1.0]

Intuition#

將除法關係建成帶權有向圖，a/b = k 表示從 a 到 b 邊權為 k。查詢 C/D 就是找 C 到 D 的路徑乘積。

  • a / b = 2 表示 a 到 b 的邊權為 2，b 到 a 的邊權為 0.5
  • 查詢 a / c = 從 a 到 c 的路徑上所有邊權的乘積
  • 用 DFS/BFS 在圖上搜尋路徑

Approaches#

⭐1: DFS#

  • 概念: 建立帶權鄰接表，對每個查詢做 DFS 找路徑，將沿途邊權相乘
  • 時間複雜度: O(Q * (V + E))，Q 為查詢數
  • 空間複雜度: O(V + E)
class Solution {
    fun calcEquation(equations: List<List<String>>, values: DoubleArray, queries: List<List<String>>): DoubleArray {
        val graph = HashMap<String, MutableList<Pair<String, Double>>>()

        for (i in equations.indices) {
            val (a, b) = equations[i]
            graph.getOrPut(a) { mutableListOf() }.add(b to values[i])
            graph.getOrPut(b) { mutableListOf() }.add(a to 1.0 / values[i])
        }

        fun dfs(src: String, dst: String, visited: MutableSet<String>): Double {
            if (src !in graph || dst !in graph) return -1.0
            if (src == dst) return 1.0
            visited.add(src)
            for ((next, weight) in graph[src]!!) {
                if (next in visited) continue
                val result = dfs(next, dst, visited)
                if (result != -1.0) return weight * result
            }
            return -1.0
        }

        return DoubleArray(queries.size) { i ->
            dfs(queries[i][0], queries[i][1], mutableSetOf())
        }
    }
}

2: BFS#

  • 概念: BFS 搜尋路徑，追蹤累計乘積
  • 時間複雜度: O(Q * (V + E))
  • 空間複雜度: O(V + E)
class Solution {
    fun calcEquation(equations: List<List<String>>, values: DoubleArray, queries: List<List<String>>): DoubleArray {
        val graph = HashMap<String, MutableList<Pair<String, Double>>>()

        for (i in equations.indices) {
            val (a, b) = equations[i]
            graph.getOrPut(a) { mutableListOf() }.add(b to values[i])
            graph.getOrPut(b) { mutableListOf() }.add(a to 1.0 / values[i])
        }

        fun bfs(src: String, dst: String): Double {
            if (src !in graph || dst !in graph) return -1.0
            if (src == dst) return 1.0
            val visited = HashSet<String>()
            val queue = ArrayDeque<Pair<String, Double>>()
            queue.add(src to 1.0)
            visited.add(src)
            while (queue.isNotEmpty()) {
                val (node, product) = queue.removeFirst()
                for ((next, weight) in graph[node]!!) {
                    if (next == dst) return product * weight
                    if (next !in visited) {
                        visited.add(next)
                        queue.add(next to product * weight)
                    }
                }
            }
            return -1.0
        }

        return DoubleArray(queries.size) { i -> bfs(queries[i][0], queries[i][1]) }
    }
}

🔑 Takeaways#

  • Pattern: 帶權圖路徑搜尋 – 除法關係形成帶權有向圖
  • 關鍵技巧: a/b = k 建兩條邊（正向 k，反向 1/k）；路徑乘積就是除法結果；注意處理不存在的變數