399. 除法求值

mid

给你一个变量对数组 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 的情况，且不存在任何矛盾的结果。

图 + DFS

太难了。。。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
func calcEquation(equations [][]string, values []float64, queries [][]string) []float64 {
	graph := map[string][]node{}
	for i := 0; i < len(equations); i++ {
		a, b, v := equations[i][0], equations[i][1], values[i]
		graph[a] = append(graph[a], node{b, v})              // a / b == v
		graph[b] = append(graph[b], node{a, float64(1 / v)}) // b / a == 1/v
	}
	var ans []float64
	for i := 0; i < len(queries); i++ {
		ans = append(ans, dfs(graph, queries[i], &map[string]bool{}))
	}
	return ans
}

type node struct {
	s string  //除数
	v float64 //结果
}

func dfs(graph map[string][]node, query []string, onpath *map[string]bool) float64 {
	a, b := query[0], query[1]
	if (*onpath)[a] { //遍历过，直接返回
		return -1.0
	}
	(*onpath)[a] = true
	for _, nxt := range graph[a] {
		if nxt.s == b {
			return nxt.v
		}
		v := dfs(graph, []string{nxt.s, b}, onpath)
		if v != -1.0 { //找到中间结果
			return v * nxt.v

		}
	}
	(*onpath)[a] = false
	return -1.0
}