# 399. Evaluate Division

Equations are given in the format `A / B = k`, where `A` and `B` are variables represented as strings, and `k` is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return `-1.0`.

Example:
Given `a / b = 2.0, b / c = 3.0.`
queries are: `a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? .`
return `[6.0, 0.5, -1.0, 1.0, -1.0 ].`

The input is: `vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries `, where `equations.size() == values.size()`, and the values are positive. This represents the equations. Return `vector<double>`.

According to the example above:

``````equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].
``````

The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.

1. 已知: a / b = 2, b / c = 3， 求 a / c
2. 已知: a / c = 2, b / c = 3， 求 a / b
3. 已知: a / b = 2, a / c = 3， 求 b / c

1. 已知: a / b = 2 ，b / a = 1/2， b / c = 3 ，c / b = 1/3，求 a / c
2. 已知: a / c = 2 ，c / a = 1/2，b / c = 3， c / b = 1/3 ，求 a / b
3. 已知: a / b = 2， b / a = 1/2a / c = 3 ，c / a = 1/3，求 b / c

``````class Solution {
public:
vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
vector<double> res;
for (int i = 0; i < equations.size(); ++i) {
m[equations[i].first][equations[i].second] = values[i];
m[equations[i].second][equations[i].first] = 1.0 / values[i];
}
for (auto query : queries) {
unordered_set<string> visited;
double t = helper(query.first, query.second, visited);
res.push_back((t > 0.0) ? t : -1);
}
return res;
}
double helper(string up, string down, unordered_set<string>& visited) {
if (m[up].count(down)) return m[up][down];
for (auto a : m[up]) {
if (visited.count(a.first)) continue;
visited.insert(a.first);
double t = helper(a.first, down, visited);
if (t > 0.0) return t * a.second;
}
return -1.0;
}

private:
unordered_map<string, unordered_map<string, double>> m;
};
``````

``````class Solution {
public:
vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
vector<double> res;
unordered_map<string, unordered_map<string, double>> g;
for (int i = 0; i < equations.size(); ++i) {
g[equations[i].first].emplace(equations[i].second, values[i]);
g[equations[i].first].emplace(equations[i].first, 1.0);
g[equations[i].second].emplace(equations[i].first, 1.0 / values[i]);
g[equations[i].second].emplace(equations[i].second, 1.0);
}
for (auto query : queries) {
if (!g.count(query.first) || !g.count(query.second)) {
res.push_back(-1.0);
continue;
}
queue<pair<string, double>> q;
unordered_set<string> visited{query.first};
bool found = false;
q.push({query.first, 1.0});
while (!q.empty() && !found) {
for (int i = q.size(); i > 0; --i) {
auto t = q.front(); q.pop();
if (t.first == query.second) {
found = true;
res.push_back(t.second);
break;
}
for (auto a : g[t.first]) {
if (visited.count(a.first)) continue;
visited.insert(a.first);
a.second *= t.second;
q.push(a);
}
}
}
if (!found) res.push_back(-1.0);
}
return res;
}
};
``````

https://leetcode.com/problems/evaluate-division/

https://leetcode.com/problems/evaluate-division/discuss/88347/c-bfs-solution-easy-to-understand

https://leetcode.com/problems/evaluate-division/discuss/88287/esay-understand-java-solution-3ms

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation