LeetCode刷题实战399:除法求值
共 4182字,需浏览 9分钟
·
2021-10-08 18:09
示例
解题
public class Solution {
private MapstringToInteger = new HashMap<>();
private int index = 0;
private double[][] graph;
private boolean[] visited;
public double[] calcEquation(List> equations, double[] values, List
) {> queries
for (Listlist : equations) {
for (String string : list) {
if (!stringToInteger.containsKey(string)) {
stringToInteger.put(string, index++);
}
}
}
graph = new double[index][index];
for (int i = 0; i < equations.size(); i++) {
Listlist = equations.get(i);
String string0 = list.get(0), string1 = list.get(1);
int index1 = stringToInteger.get(string0), index2 = stringToInteger.get(string1);
graph[index1][index2] = values[i];
graph[index2][index1] = 1.0 / values[i];
}
double[] result = new double[queries.size()];
Arrays.fill(result, -1.0);
for (int i = 0; i < result.length; i++) {
Listlist = queries.get(i);
String string0 = list.get(0), string1 = list.get(1);
if (stringToInteger.containsKey(string0) && stringToInteger.containsKey(string1)) {
if (string0.equals(string1)) {
result[i] = 1.0;
} else {
int index1 = stringToInteger.get(string0), index2 = stringToInteger.get(string1);
visited = new boolean[index];
double len = 1.0;
dfs(index1, index2, len, result, i);
}
}
}
return result;
}
private void dfs(int begin, int end, double len, double[] result, int k) {
if (graph[begin][end] == 0) {
visited[begin] = true;
for (int i = 0; i < index; i++) {
if (!visited[i] && graph[begin][i] != 0) {
dfs(i, end, len * graph[begin][i], result, k);
}
}
} else {
result[k] = len * graph[begin][end];
}
}
}
LeetCode刷题实战381:O(1) 时间插入、删除和获取随机元素