399 Evaluate Division
Equations are given in the format
A / B = k, whereAandBare variables represented as strings, andkis 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, whereequations.size() == values.size(), and the values are positive. This represents the equations. Returnvector<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) DFS
class Solution {
class Edge {
String val;
double weight;
public Edge(String val, double weight) {
this.val = val;
this.weight = weight;
}
}
public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
double[] res = new double[queries.length];
if (equations.length == 0 || equations[0].length == 0) {
return res;
}
Map<String, List<Edge>> adjList = new HashMap<>();
for (int i = 0; i < equations.length; i++) {
String vertex1 = equations[i][0];
String vertex2 = equations[i][1];
Edge edge1 = new Edge(vertex2, values[i]);
Edge edge2 = new Edge(vertex1, 1 / values[i]);
if (adjList.containsKey(vertex1)) {
adjList.get(vertex1).add(edge1);
}
else {
List<Edge> edges = new ArrayList<>();
edges.add(edge1);
adjList.put(vertex1, edges);
}
if (adjList.containsKey(vertex2)) {
adjList.get(vertex2).add(edge2);
}
else {
List<Edge> edges = new ArrayList<>();
edges.add(edge2);
adjList.put(vertex2, edges);
}
}
for (int i = 0; i < queries.length; i++) {
String start = queries[i][0];
String end = queries[i][1];
Set<String> visited = new HashSet<>();
dfs(start, end, 1.0, i, visited, adjList, res);
if (res[i] == 0 && !start.equals(end)) {
res[i] = -1.0;
}
}
return res;
}
public void dfs(String start, String end, double value, int index, Set<String> visited, Map<String, List<Edge>> adjList, double[] res) {
if (!adjList.containsKey(start) || !adjList.containsKey(end)) {
res[index] = -1.0;
return;
}
if (start.equals(end)) {
res[index] = value;
return;
}
if (visited.contains(start)) {
return;
}
visited.add(start);
List<Edge> edges = adjList.get(start);
for (Edge edge : edges) {
dfs(edge.val, end, value * edge.weight, index, visited, adjList, res);
}
}
}
(2) BFS
class Solution {
class Edge {
String val;
double weight;
public Edge(String val, double weight) {
this.val = val;
this.weight = weight;
}
}
public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
double[] res = new double[queries.length];
if (equations.length == 0 || equations[0].length == 0) {
return res;
}
Map<String, List<Edge>> adjList = new HashMap<>();
for (int i = 0; i < equations.length; i++) {
String vertex1 = equations[i][0];
String vertex2 = equations[i][1];
Edge edge1 = new Edge(vertex2, values[i]);
Edge edge2 = new Edge(vertex1, 1 / values[i]);
if (adjList.containsKey(vertex1)) {
adjList.get(vertex1).add(edge1);
}
else {
List<Edge> edges = new ArrayList<>();
edges.add(edge1);
adjList.put(vertex1, edges);
}
if (adjList.containsKey(vertex2)) {
adjList.get(vertex2).add(edge2);
}
else {
List<Edge> edges = new ArrayList<>();
edges.add(edge2);
adjList.put(vertex2, edges);
}
}
for (int i = 0; i < queries.length; i++) {
String start = queries[i][0];
String end = queries[i][1];
Set<String> visited = new HashSet<>();
bfs(start, end, i, visited, adjList, res);
if (res[i] == 0 && !start.equals(end)) {
res[i] = -1.0;
}
}
return res;
}
public void bfs(String start, String end, int index, Set<String> visited, Map<String, List<Edge>> adjList, double[] res) {
if (!adjList.containsKey(start) || !adjList.containsKey(end)) {
res[index] = -1.0;
return;
}
Queue<String> queue = new LinkedList<>();
Queue<Double> values = new LinkedList<>();
queue.add(start);
values.add(1.0);
while (!queue.isEmpty()) {
String curVertex = queue.remove();
double curValue = values.remove();
if (!adjList.containsKey(curVertex)) {
res[index] = -1.0;
return;
}
if (curVertex.equals(end)) {
res[index] = curValue;
return;
}
if (visited.contains(curVertex)) {
continue;
}
visited.add(curVertex);
for (Edge edge : adjList.get(curVertex)) {
String nextVertex = edge.val;
queue.add(nextVertex);
double nextValue = curValue * edge.weight;
values.add(nextValue);
}
}
}
}
DFS:
BFS:
Last modified 3yr ago