399 除法求值

题目描述#

给定一组等式 equations[i] = [Ai, Bi] 和对应的值 values[i]，表示 Ai / Bi = values[i]。再给定一组查询 queries[j] = [Cj, Dj]，求每个 Cj / Dj 的值。若无法确定或变量未定义，返回 -1.0。

思路#

把每个变量看作图中的节点，每个等式 A / B = k 转化为两条有向带权边：A → B（权重 k）和 B → A（权重 1/k）。查询 C / D 就是在图中从 C 走到 D，把路径上所有边的权重连乘起来。

用 BFS 来求路径乘积：从源节点出发，队列中同时维护「当前节点」和「累计乘积」，每次扩展邻居时把新权重乘进去。到达目标节点时直接返回当前乘积。若队列耗尽仍未到达，说明两节点不连通，返回 -1.0。

边界处理有两条：一是查询的任意一个变量在图中不存在时，直接返回 -1.0；二是查询两个相同变量时（X / X），只要变量存在就返回 1.0。

知识边界#

带权有向图建模：一条除法等式 = 两条互为倒数的有向边，是本题的关键转化
BFS 队列里同时携带状态（累计乘积）是路径权重类问题的常见手法，区别于只记录节点的普通 BFS
用 map[string]map[string]float64 表示邻接表，Go 中需要在添加前检查外层 map 是否为 nil
查询中出现图中不存在的节点时必须提前判断，否则访问不存在的节点会返回零值而非 -1.0

代码#

func calcEquation(equations [][]string, values []float64, queries [][]string) []float64 {
    // 用带权图来做，graph[u][v] 来表示 u / v的值
    graph := make(map[string]map[string]float64)

    // 添加边的函数
    addEdge := func(u, v string, w float64) {
        if graph[u] == nil {
            graph[u] = make(map[string]float64)
        }
        graph[u][v] = w
    }

    // 将算式的链接加入图
    for i, eq := range equations {
        u, v := eq[0], eq[1]
        addEdge(u, v, values[i])
        addEdge(v, u, 1.0/values[i])
    }

    // 开始遍历 bfs
    bfs := func(src, dst string) float64 {
        // 当有任意一个节点不存在的时候，返回-1.0
        if graph[src] == nil || graph[dst] == nil {
            return -1.0
        }
        // 当两个节点相等的时候，返回1.0
        if src == dst {
            return 1.0
        }

        visited := make(map[string]bool)
        // 队列存 [当前节点, 累计乘积]
        type item struct {
            node string
            prod float64
        }
        queue := []item{{src, 1.0}}
        visited[src] = true

        for len(queue) > 0 {
            // 每次取出队头 cur
            cur := queue[0]
            queue = queue[1:]

            // 注意map的遍历是 键 -> 值
            for next, w := range graph[cur.node] {
                newProd := cur.prod * w
                if next == dst {
                    return newProd
                }
                if !visited[next] {
                    visited[next] = true
                    queue = append(queue, item{next, newProd})
                }
            }
        }
        return -1.0
    }
    ans := make([]float64, len(queries))
    for i, q := range queries {
        ans[i] = bfs(q[0], q[1])
    }
    return ans
}