除法求值
给你一个变量对数组 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：
codeType
输入：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：
codeType
输入：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：
codeType
输入：equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
输出：[0.50000,2.00000,-1.00000,-1.00000]
提示：
- 1 <= equations.length <= 20
- equations[i].length == 2
- 1 <= Ai.length, Bi.length <= 5
- values.length == equations.length
- 0.0 < values[i] <= 20.0
- 1 <= queries.length <= 20
- queries[i].length == 2
- 1 <= Cj.length, Dj.length <= 5
- Ai, Bi, Cj, Dj 由小写英文字母与数字组成
解法
ts
function calcEquation(equations: string[][], values: number[], queries: string[][]): number[] {
// 用图表示的话，每个字符就是一个点
// 每个values就是两个字符的边，而且是有向边
// 假如有路径a->b = 2 那么逆路径就是 b->a = 1/2 = 0.5
// 假如有路径a->b = 2且 b -> c = 3 那么就有 a->c = 2 * 3 = 6
// 根据这个规则，就可以根据已有路径推得大多路径，不存在的路径值即为-1
// 初始化临接表 key:当前节点 value: 临接的节点数组[目标节点, 路径长度]
const graph = new Map<string, [string, number][]>();
// 1. 构建双向带权图
for(let i = 0; i < equations.length; i++) {
const [x, y] = equations[i];
const val = values[i];
!graph.has(x) && graph.set(x, []); // 临接表创建节点x
graph.get(x)!.push([y, val]); // 创建从x->y的路径
!graph.has(y) && graph.set(y, []); // 创建节点y
graph.get(y)!.push([x, 1 / val]); // 创建逆路径
}
const res: number[] = [];
// 2. 处理每个查询
const dfs = (cur: string, target: string, visited: Set<string>): number => {
if(cur === target) return 1.0; // 目标是自己返回1
visited.add(cur); // 记录访问过的节点，防止出现循环
for(const [next, val] of graph.get(cur)!) {
if(!visited.has(next)) {
const sub = dfs(next, target, visited);
if(sub !== -1) return val * sub; // 路径值累乘
}
}
return -1.0; // 找不到路径，返回-1
}
for(const [s, t] of queries) {
if(!graph.has(s) || !graph.has(t)) res.push(-1);
else if(s === t) res.push(1);
else res.push(dfs(s, t, new Set()));
}
return res;
};