题目描述
You are given an array of variable pairs
equations
and an array of real numbersvalues
, whereequations[i] = [Ai, Bi]
andvalues[i]
represent the equationAi / Bi = values[i]
. EachAi
orBi
is a string that represents a single variable.You are also given some queries, where
queries[j] = [Cj, Dj]
represents thejth
query where you must find the answer forCj / Dj = ?
.Return the answers to all queries. If a single answer cannot be determined, return
-1.0
.
例子
例子 1
Input:
equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
Output:[6.00000,0.50000,-1.00000,1.00000,-1.00000]
Explanation: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 ]
例子 2
Input:
equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
Output:[3.75000,0.40000,5.00000,0.20000]
例子 3
Input:
equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
Output:[0.50000,2.00000,-1.00000,-1.00000]
Constraints
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
consist of lower case English letters and digits.
解题思路
根据给定的等式构建有向图,注意每个等式Ai, Bi, vi
可以构建两条边:Ai->Bi: vi, Bi->Ai: 1/vi
。图构建完成后,给定某个等式,只需要找到两个节点之间的路径即可,等式结果为各边权重相乘,代码如下:
#include <queue>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
class Solution {
public:
std::vector<double> calcEquation(
std::vector<std::vector<std::string>>& equations,
std::vector<double>& values,
std::vector<std::vector<std::string>>& queries) {
for (int i = 0; i < equations.size(); ++i) {
graph[equations[i][0]].push_back({equations[i][1], values[i]});
graph[equations[i][1]].push_back(
{equations[i][0], 1.0 / values[i]});
}
// cout << "graph" << endl;
std::vector<double> results;
for (auto query : queries) {
double result = 1.0;
std::unordered_set<std::string> visited;
if (dfs(query[0], query[1], result, visited))
results.push_back(result);
else
results.push_back(-1.0);
}
return results;
}
private:
std::unordered_map<std::string, std::vector<std::pair<std::string, double>>>
graph;
bool dfs(const std::string& current, const std::string& target,
double& result, std::unordered_set<std::string>& visited) {
if (graph.find(current) == graph.end()) {
return false;
}
if (current == target) {
return true;
}
visited.insert(current);
for (auto edge : graph[current]) {
if (visited.count(edge.first)) continue;
result *= edge.second;
if (dfs(edge.first, target, result, visited)) {
return true;
}
result /= edge.second;
}
return false;
}
};
- 时间复杂度:
O(n*||V|+|E||)
- 空间复杂度:
O(||V|+|E||)
GitHub 代码同步地址: 399.EvaluateDivision.cpp
其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions