leetcode 399. 除法求值

题解

dfs深度搜索思想,首先遍历 queries 找出被除数 a,除数 b,然后根据 equations 找出 a / b 的值

示例代码(go)

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
39
40
41
func calcEquation(equations [][]string, values []float64, queries [][]string) []float64 {
n := len(queries)
res := make([]float64, n)
visited := make(map[int]bool)
for i := 0; i < n; i++ {
res[i] = calc(equations, values, visited, queries[i][0], queries[i][1], 1.0)
}
return res
}

func calc(equations [][]string, values []float64, visited map[int]bool, a, b string, answer float64) float64 {
for i, v := range equations {
if visited[i] {
continue
}
if v[0] == a && a == b || v[1] == a && a == b {
return 1.0
} else if v[0] == a {
if v[1] == b {
return answer * values[i]
}
visited[i] = true
k := calc(equations, values, visited, v[1], b, answer * values[i])
visited[i] = false
if k != -1.0 {
return k
}
} else if v[1] == a && values[i] != 0.0 {
if v[0] == b {
return answer / values[i]
}
visited[i] = true
k := calc(equations, values, visited, v[0], b, answer / values[i])
visited[i] = false
if k != -1.0 {
return k
}
}
}
return -1.0
}