題目描述

??給你一個變量對數組 equations 和一個實數值數組 values 作為已知條件，其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。每個 Ai 或 Bi 是一個表示單個變量的字符串。另有一些以數組 queries 表示的問題，其中 queries[j] = [Cj, Dj] 表示第 j 個問題，請你根據已知條件找出 Cj / Dj = ? 的結果作為答案。返回 所有問題的答案 。如果存在某個無法確定的答案，則用 -1.0 替代這個答案。如果問題中出現了給定的已知條件中沒有出現的字符串，也需要用 -1.0 替代這個答案。

解析

??這題解法還挺多的，官方題解是基于并查集的方式，視頻講解挺清晰的這里不多贅述。還有解法就是基于圖的方法，將圖構建好后，圖的深度優先遍歷或者克魯斯卡爾算法將鄰接矩陣的值更新完畢后直接查詢。這題的輸入并不多，因此對每一個queries直接DFS即可。
??下面的代碼是我一開始看錯題目了，我以為只有字母，但是可能會稍微好理解一些。

public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {double[][] distance = new double[26][26];boolean[] defined = new boolean[26];double[] res = new double[queries.size()];Arrays.fill(res, -1.0);for(int i = 0; i < equations.size(); i++) {int first = equations.get(i).get(0).charAt(0) - 97;int second = equations.get(i).get(1).charAt(0) - 97;defined[first] = true;defined[second] = true;distance[first][second] = values[i];distance[second][first] = 1 / values[i];}for(int i = 0; i < queries.size(); i++) {int first = queries.get(i).get(0).charAt(0) - 97;int second = queries.get(i).get(1).charAt(0) - 97;if(defined[first] && defined[second]) {if(distance[first][second] != 0) {res[i] = distance[first][second];continue;}if(first == second) {res[i] = 1;continue;}boolean[] visited = new boolean[26];res[i] = dfs(distance, first, second, visited);}else {res[i] = -1.;}}return res;}public double dfs(double[][] distance, int cur, int target, boolean[] visited) {if(cur == target) {return 1.0;}visited[cur] = true;for(int i = 0; i < 26; i++) {if(!visited[i] && distance[cur][i] != 0) {double res = dfs(distance, i, target, visited);if(res != -1.0) {return distance[cur][i] * res;}}}return -1.;}

??下面才是正確的代碼，實際上就是將字母的映射改為使用map去記錄字符串和下標的映射。

public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {Map<String, Integer> indexMap = new HashMap<>();int index = 0;for (List<String> equation : equations) {for (String variable : equation) {if (!indexMap.containsKey(variable)) {indexMap.put(variable, index++);}}}double[][] graph = new double[index][index];for (int i = 0; i < index; i++) {Arrays.fill(graph[i], -1.0);graph[i][i] = 1.0; // 每個變量除以自己的結果是1}for (int i = 0; i < equations.size(); i++) {int u = indexMap.get(equations.get(i).get(0));int v = indexMap.get(equations.get(i).get(1));double value = values[i];graph[u][v] = value;graph[v][u] = 1.0 / value;}double[] results = new double[queries.size()];for (int i = 0; i < queries.size(); i++) {Integer u = indexMap.get(queries.get(i).get(0));Integer v = indexMap.get(queries.get(i).get(1));if (u == null || v == null) {results[i] = -1.0;} else {results[i] = dfs(graph, u, v, new boolean[index]);}}return results;}private double dfs(double[][] graph, int cur, int target, boolean[] visited) {if (cur == target) return 1.0;visited[cur] = true;for (int i = 0; i < graph.length; i++) {if (!visited[i] && graph[cur][i] != -1) {double res = dfs(graph, i, target, visited);if (res != -1.0) {return graph[cur][i] * res;}}}return -1.0;}