除法求值
题目
给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。
另有一些以数组 queries 表示的问题，其中 queries[j] = [Cj, Dj] 表示第 j 个问题，请你根据已知条件找出 Cj / Dj = ? 的结果作为答案。
返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -1.0 替代这个答案。
注意：输入总是有效的。你可以假设除法运算中不会出现除数为 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：
a b 互相关联，并且对应的值是a/b=2.0；b c 互相关联，并且对应的值是b/c= 3.0。
此时我们很容易把 a、b、c 想像成图中的 3 个节点，对应关联的值则可以表示节点的边。（注意，这里的为相除之后的值，所以从 a->b 与 b-> a 是不同的）
那么根据给出的信息可以得到 从 a 变成 b，代价是 2.0，从 b 变成 a 代价是 1/2.0，同理可以得到 b 和 c 也是相互链接的节点。
此时 abc 三者的结构就构成了一个图，节点的一个出度和入度，代表了要变成目标节点时的代价。
观察 示例1 的 quereis[0]：
此时讨论 a-> c , 我们的上面的图中 a 和 c 并没有直接产生关联，但是可以通过 a-> b -> c 这个路径到达 c
观察此时的过程，我们从 a 出发，变到 b 的代价值变为 乘2.0，此时为 2.0✖️b ，之后从 b 到 c 代价变化为 乘3.0，此时a=2.0✖️ b=2.0✖️3.0 c。那么最终的值为 a/c = 2.0 ✖️b / c = 2.0✖️3.0✖️c / c = 6.0
有了上述过程推导，我们可以将任意queries[i] 的求解过程变为 ，发现要求的值其实就是 queries[i][0] -> queries[i][1] 的结果。我们可以很轻易的从 queries[i][0] 出发，遍历 queries[i][0] 连接的所有节点，并且记录中间过程的所有值变化，直到找到 queries[i][1]，最终将结果返回。
如果 queries[i][0] 或者 queries[i][1] 不存在，那么我们可以直接将这个 query 的值 设置为 1
题解
首先我们遍历 equations 以及对应的 values ，构建一个图，图的数据结构多种多样，为了方便查询，我采用 map[string]map[string]struct{} 的结构来表示每个节点以及对应连接的子节点。同时为了方便查找，可以直接维护一个两节点之间的值的map，用于快速得到直接相连的结果。
之后根据 queries ，根据 start 和 target 进行图遍历（这里需要维护一个 visited map，因为图是双向的，否则会死循环）
遍历过程很简单，递归的深度遍历，找出当前的 start 的所有子节点，尝试从所有子节点中递归找出 target，如果找到了 target，返回当前的 value 即可，否则说明 target 与 start 没有任何路径能够抵达，此时返回 -1 即可。
type temp struct {
x1 string
x2 string
}
func calcEquation(equations [][]string, values []float64, queries [][]string) []float64 {
var valueMp = make(map[temp]float64)
path := make(map[string]map[string]struct{}, 0)
for i, e := range equations {
valueMp[temp{
x1: e[0],
x2: e[1],
}] = values[i]
valueMp[temp{
x1: e[1],
x2: e[0],
}] = 1 / values[i]
if mp, ok := path[e[0]]; ok {
mp[e[1]] = struct{}{}
} else {
path[e[0]] = map[string]struct{}{
e[1]: {},
}
}
if mp, ok := path[e[1]]; ok {
mp[e[0]] = struct{}{}
} else {
path[e[1]] = map[string]struct{}{
e[0]: {},
}
}
}
res := make([]float64, len(queries))
for i, q := range queries {
start := q[0]
target := q[1]
_, ok1 := path[start]
_, ok2 := path[target]
if !ok1 || !ok2 {
res[i] = -1
continue
}
v, ok := processValueMap(1.0, start, target, valueMp, path, map[string]struct{}{})
if ok {
valueMp[temp{
start,
target,
}] = v
valueMp[temp{
target,
start,
}] = 1 / v
res[i] = v
if mp, ok := path[start]; ok {
mp[target] = struct{}{}
} else {
path[start] = map[string]struct{}{
target: {},
}
}
if mp, ok := path[target]; ok {
mp[start] = struct{}{}
} else {
path[target] = map[string]struct{}{
start: {},
}
}
} else {
res[i] = -1.0
}
}
return res
}
func processValueMap(curV float64, start, target string, valueMap map[temp]float64, pathMap map[string]map[string]struct{}, visitedMp map[string]struct{}) (float64, bool) {
subs := pathMap[start]
if _, ok := subs[target]; ok {
return valueMap[temp{start, target}] * curV, true
}
for sub := range subs {
if _, ok := visitedMp[sub]; ok {
continue
}
visitedMp[sub] = struct{}{}
v := valueMap[temp{start, sub}]
curV, ok := processValueMap(curV*v, sub, target, valueMap, pathMap, visitedMp)
delete(visitedMp, sub)
if ok {
return curV, ok
}
}
return -1, false
}
- 0
- 0
-
分享