0399. Evaluate Division
=======================
题目信息
--------
:题号: 0399
:难度: Medium
:主题: 变量比值、方程关系、查询顺序、不可推导
:原题: `LeetCode 0399 `_
:重点: 每个方程给出有向比值、查询按输入顺序返回、已知变量自除为 1、未知变量参与时返回 -1.0
题目重述
--------
给定方程数组 ``equations`` 和对应实数数组 ``values``。若 ``equations[i] = [Ai, Bi]``,则已知 ``Ai / Bi = values[i]``。对每个查询 ``[Cj, Dj]``,根据全部已知关系计算 ``Cj / Dj``,并按查询原顺序返回结果数组。
若查询中的任一变量从未出现在已知方程中,或两个已知变量之间不存在可推导的关系,则该项返回 ``-1.0``。已知变量除以自身结果为 ``1.0``,未知变量即使两侧名称相同也返回 ``-1.0``。方程数量和查询数量均位于 ``[1, 20]``,方程值位于 ``(0, 20]``;输入保证方程相互一致,变量代表非零数值。
自建示例
--------
通过中间变量推导:
.. code-block:: text
输入:equations = [["p","q"],["q","r"]]
values = [4.0,0.5]
queries = [["p","r"],["r","p"],["p","p"]]
输出:[2.0,0.5,1.0]
解释:p/r = (p/q)*(q/r) = 2;反向比值为 1/2;p 是已知变量,所以 p/p 为 1。
查询含未知变量:
.. code-block:: text
输入:queries = [["p","x"],["x","x"]]
输出:[-1.0,-1.0]
解释:x 从未出现在任何已知方程中,两项都无法根据输入关系确定。
把比值写成带权有向图
----------------------
方程 ``A / B = v`` 可表示为边 ``A -> B`` 权重 ``v``,同时加入反向边 ``B -> A`` 权重 ``1 / v``。沿路径相乘就得到起点与终点的比值;查询时从起点深搜到终点,使用访问集合避免在环中重复走回。
查询的两个变量必须都出现在图中;已知变量自除时路径长度为零,结果为 1。每个查询单独建立访问集合,不能让前一个查询的访问状态影响后一个查询。
C++ 实现
--------
.. code-block:: cpp
class Solution {
std::unordered_map<
std::string,
std::vector>> graph;
double search(const std::string& current,
const std::string& target,
std::unordered_set& visited) {
if (current == target) return 1.0;
visited.insert(current);
for (const auto& edge : graph[current]) {
if (visited.count(edge.first) != 0) continue;
double rest = search(edge.first, target, visited);
if (rest >= 0.0) return edge.second * rest;
}
return -1.0;
}
public:
std::vector calcEquation(
std::vector>& equations,
std::vector& values,
std::vector>& queries) {
graph.clear();
for (int i = 0; i < static_cast(equations.size()); ++i) {
const std::string& first = equations[i][0];
const std::string& second = equations[i][1];
graph[first].push_back({second, values[i]});
graph[second].push_back({first, 1.0 / values[i]});
}
std::vector result;
for (const auto& query : queries) {
if (graph.count(query[0]) == 0
|| graph.count(query[1]) == 0) {
result.push_back(-1.0);
continue;
}
std::unordered_set visited;
result.push_back(search(query[0], query[1], visited));
}
return result;
}
};
代码分析
--------
反向边保留了比值的倒数,路径上的边权相乘就是方程连乘;不可达时深搜返回 ``-1.0``,不会把失败路径的权重混入结果。设变量数为 ``V``、边数为 ``E``,每个查询最坏遍历 ``O(V+E)``,图及单次访问集合空间为 ``O(V+E)``。