- 问题来源
- 问题简介
给出一系列式子 a / b = k（k为非零小数），要求算出指定的算式，如:
给出 a / b = 2.0, b / c = 3.0；
则求 a / c。
结果: 6.0
若求不出，则为 -1。
解题思路
若有 a / b, b / c
则可求 a / c = a / b * b / c
同理，对于 a / b
若有 a / d, d / b
则可求 a / b
以此类推，直到无法继续拓展。
这就有点像分治了。问题是在求a / c 时，我们如何确定这个b的值？
如果将 a / b 看成 a->b，那么，a / b, b / c就可以看成 a -> b -> c
则：
我们从a开始遍历，看是否存在一条路径使得a和c是连通的。
这里需要注意的是，若我们有 a / b的值，那么我们也就同时拥有 b / a 的值了。
也就是说这道题涉及到的是无向图的遍历了。
| 时间复杂度 | 空间复杂度 |
|---|---|
| O(未知) | O(未知) |
Code
class Solution {
public:
vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
unordered_map<string, unordered_map<string, double>> next;
unordered_set<string> all;
pair<string, string> cur;
double val;
for (int i = 0, len = equations.size(); i < len; i++) {
cur = equations[i];
val = values[i];
next[cur.first][cur.second] = val;
next[cur.second][cur.first] = 1 / val;
all.insert(cur.first);
all.insert(cur.second);
}
vector<double> rs(queries.size(), -1.0);
auto it = rs.begin();
for (auto &i : queries) {
auto a_c = all;
if (next.find(i.first) == next.end() || next.find(i.second) == next.end()) {
*it++ = -1;
} else {
*it++ = dfs(i.first, i.second, next, a_c);
}
}
return rs;
}
double dfs(const string &cur, const string &goal,
unordered_map<string, unordered_map<string, double>> &next,
unordered_set<string> &all) {
if (cur == goal) {
return next.find(cur) != next.end() ? !!(next[cur].begin() -> second) : -1;
}
if (next[cur].find(goal) != next[cur].end()) {
return next[cur][goal];
}
all.erase(cur);
auto &next_set = next[cur];
double nextVal = -1;
for (auto &i : next_set) {
if (all.find(i.first) == all.end()) {
continue;
}
nextVal = dfs(i.first, goal, next, all);
if (nextVal != -1) {
return nextVal * i.second;
}
}
return -1;
}
};
