0%

[Leetcode]399. Evaluate Division(C++)

题目描述

题目链接:399. Evaluate Division

You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] represent the equation Ai / Bi = values[i]. Each Ai or Bi is a string that represents a single variable.

You are also given some queries, where queries[j] = [Cj, Dj] represents the jth query where you must find the answer for Cj / 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。图构建完成后,给定某个等式,只需要找到两个节点之间的路径即可,等式结果为各边权重相乘,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#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