leetcode 399. 除法求值

题目描述

给出方程式 A / B = k, 其中 A 和 B 均为代表字符串的变量, k 是一个浮点型数字。根据已知方程式求解问题,并返回计算结果。如果结果不存在,则返回 -1.0。

示例 :
给定 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 ]

输入为: vector<pair<string, string>> equations, vector& values, vector<pair<string, string>> queries(方程式,方程式结果,问题方程式), 其中 equations.size() == values.size(),即方程式的长度与方程式结果长度相等(程式与结果一一对应),并且结果值均为正数。以上为方程式的描述。 返回vector类型。

基于上述例子,输入如下:
equations(方程式) = [ [“a”, “b”], [“b”, “c”] ],
values(方程式结果) = [2.0, 3.0],
queries(问题方程式) = [ [“a”, “c”], [“b”, “a”], [“a”, “e”], [“a”, “a”], [“x”, “x”] ].
输入总是有效的。你可以假设除法运算中不会出现除数为0的情况,且不存在任何矛盾的结果。

题解

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
}