나눗셈 문제를 평가할 때 A / B = k 형식으로 몇 가지 방정식을 제공했습니다. 여기서 A와 B는 문자열이고 k는 실수입니다. 답변이 존재하지 않으면 -1을 반환합니다.
차례
예
입력:
방정식 : a / b = 2.0 및 b / c = 3.0
쿼리 : a / c =?, b / a =?, a / e =?, a / a =?, x / x =?
출력:
{6.0, 0.5, -1.0, 1.0, -1.0}
방정식은 목록의 목록으로 표시됩니다. 문자열, 값은 다음과 같이 표시됩니다. 정렬 이중 및 쿼리는 list_of_list_of 문자열로도 표시됩니다. 즉, 위의 예에서 입력은 다음과 같이 표시됩니다.
방정식 = {{“a”,“b”}, {“a”,“c”}}
값 = {2.0, 3.0}
검색어 = {{ "a", "c"}, { "b", "a"}, { "a", "e"}, { "a", "a"}, { "x", "x ”}}
나눗셈 평가를위한 알고리즘
위의 문제는 그래프를 나타냅니다.
방정식의 변수는 노드이고 방정식의 값은 모서리의 가중치입니다.
꼭지점 x에서 꼭지점 y까지의 가장자리는 x / y와 같은 가중치를 갖습니다.
위 예의 그래프는 다음과 같습니다.
쿼리에 대한 응답은 다음을 수행하여 찾을 수 있습니다. DFS 에서 검색 그래프.
- 위에서 언급 한대로 그래프를 작성하십시오.
- 각 쿼리는 소스와 대상의 형태이므로 소스에서 시작하여 대상에 도달해야합니다.
- 모든 쿼리에 대해 소스에서 시작하고 소스가 없으면 -1을 반환합니다.
- 소스에 필요한 대상에 대한 직접 에지가있는 경우 에지 값을 반환합니다.
- 그렇지 않으면 소스를 방문으로 표시하고 아직 방문하지 않은 소스의 모든 인접 항목에 대해 반복하면 인접 항목이 소스가되고 대상은 동일하게 유지됩니다. 인접 항목의 응답이 -1이 아닌 경우 소스에서 인접 항목으로 에지 가중치를 반환합니다. 더하기 이웃의 대답.
평가 부문을위한 JAVA 코드
import java.util.*;
public class EvaluateDivision {
private static double[] calcEquation(List<List<String>> equations, double[] values,
List<List<String>> queries) {
// Build the graph
HashMap<String, HashMap<String, Double>> graph = new HashMap<>();
for (int i = 0; i < equations.size(); i++) {
String from = equations.get(i).get(0);
String to = equations.get(i).get(1);
// From source to destination the weight of edge is values[i]
if (graph.containsKey(from)) {
graph.get(from).put(to, values[i]);
} else {
HashMap<String, Double> map = new HashMap<>();
map.put(to, values[i]);
graph.put(from, map);
}
// From destination to source the weight of edge is (1 / values[i])
if (graph.containsKey(to)) {
graph.get(to).put(from, 1 / values[i]);
} else {
HashMap<String, Double> map = new HashMap<>();
map.put(from, 1 / values[i]);
graph.put(to, map);
}
}
// Solve queries
double ans[] = new double[queries.size()];
for (int i = 0; i < queries.size(); i++) {
// Visited set
HashSet<String> visited = new HashSet<>();
ans[i] = dfs(graph, queries.get(i).get(0), queries.get(i).get(1), visited);
}
return ans;
}
private static double dfs(HashMap<String, HashMap<String, Double>> graph, String from, String to,
HashSet<String> visited) {
// Source not found
if (!graph.containsKey(from)) {
return -1.0;
}
// Direct edge
if (graph.get(from).containsKey(to)) {
return graph.get(from).get(to);
}
// Mark source as visited
visited.add(from);
for (Map.Entry<String, Double> entry : graph.get(from).entrySet()) {
if (!visited.contains(entry.getKey())) {
// For all unvisited neighbors of source do dfs
// neighbor becomes the source and destination remains same
double ans = dfs(graph, entry.getKey(), to, visited);
if (ans != -1.0) {
// If ans of any neighbor is not -1, return (edge weight * ans of neighbor)
return (ans * entry.getValue());
}
}
}
// All neighbors returned -1, return -1
return -1.0;
}
public static void main(String[] args) {
// Example
List<List<String>> equations = new ArrayList<>();
ArrayList<String> eq1 = new ArrayList<>();
eq1.add("a");
eq1.add("b");
equations.add(eq1);
ArrayList<String> eq2 = new ArrayList<>();
eq2.add("b");
eq2.add("c");
equations.add(eq2);
double values[] = new double[2];
values[0] = 2.0;
values[1] = 3.0;
List<List<String>> queries = new ArrayList<>();
ArrayList<String> q1 = new ArrayList<>();
q1.add("a");
q1.add("c");
queries.add(q1);
ArrayList<String> q2 = new ArrayList<>();
q2.add("b");
q2.add("a");
queries.add(q2);
ArrayList<String> q3 = new ArrayList<>();
q3.add("a");
q3.add("e");
queries.add(q3);
ArrayList<String> q4 = new ArrayList<>();
q4.add("a");
q4.add("a");
queries.add(q4);
ArrayList<String> q5 = new ArrayList<>();
q5.add("x");
q5.add("x");
queries.add(q5);
double ans[] = calcEquation(equations, values, queries);
for (int i = 0; i < ans.length; i++) {
System.out.print(ans[i] + " ");
}
}
}
Evaluate Division을위한 C ++ 코드
#include<bits/stdc++.h>
using namespace std;
double dfs(unordered_map<string, unordered_map<string, double>> &graph,
string from, string to, unordered_set<string> &visited) {
// Source not found
if (graph.find(from) == graph.end()) {
return -1.0;
}
// Direct edge
if (graph[from].find(to) != graph[from].end()) {
return graph[from][to];
}
// Mark source as visited
visited.insert(from);
for (auto i : graph[from]) {
if (visited.find(i.first) == visited.end()) {
// For all unvisited neighbors of source do dfs
double ans = dfs(graph, i.first, to, visited);
if (ans != -1.0) {
// If ans of any neighbor is not -1, return (edge weight * ans of neighbor)
return (ans * i.second);
}
}
}
// All neighbors returned -1, return -1
return -1.0;
}
vector<double> calcEquation(vector<vector<string>>& equations,
vector<double>& values,
vector<vector<string>>& queries) {
// Build the graph
unordered_map<string, unordered_map<string, double>> graph;
for (int i = 0; i < equations.size(); i++) {
string from = equations[i][0];
string to = equations[i][1];
// From source to destination the weight of edge is values[i]
if (graph.find(from) == graph.end()) {
unordered_map<std::string, double> m;
m.insert(make_pair(to, values[i]));
graph.insert(make_pair(from, m));
} else {
graph[from].insert(make_pair(to, values[i]));
}
// From destination to source the weight of edge is (1 / values[i])
if (graph.find(to) == graph.end()) {
unordered_map<std::string, double> m;
m.insert(make_pair(from, 1 / values[i]));
graph.insert(make_pair(to, m));
} else {
graph[to].insert(make_pair(from, 1 / values[i]));
}
}
// Solve queries
vector<double> ans;
for (int i = 0; i < queries.size(); i++) {
unordered_set<string> visited;
ans.push_back(dfs(graph, queries[i][0], queries[i][1], visited));
}
return ans;
}
int main() {
// Example
vector<vector<string>> equations;
vector<string> eq1;
eq1.push_back("a");
eq1.push_back("b");
equations.push_back(eq1);
vector<string> eq2;
eq2.push_back("b");
eq2.push_back("c");
equations.push_back(eq2);
vector<double> values;
values.push_back(2.0);
values.push_back(3.0);
vector<vector<string>> queries;
vector<string> q1;
q1.push_back("a");
q1.push_back("c");
queries.push_back(q1);
vector<string> q2;
q2.push_back("b");
q2.push_back("a");
queries.push_back(q2);
vector<string> q3;
q3.push_back("a");
q3.push_back("e");
queries.push_back(q3);
vector<string> q4;
q4.push_back("a");
q4.push_back("a");
queries.push_back(q4);
vector<string> q5;
q5.push_back("x");
q5.push_back("x");
queries.push_back(q5);
vector<double> ans = calcEquation(equations, values, queries);
for (int i = 0; i < ans.size(); i++) {
cout<<ans[i]<<" ";
}
return 0;
}
6 0.5 -1 1 -1
복잡성 분석
시간 복잡성 = O (q * (V + E))어디로
q –> 쿼리 수
V –> 그래프의 꼭지점 수 (또는 변수 수)
E –> 그래프의 모서리 수 (또는 방정식 수)
