哪里建设网站好,自己注册公司多少钱,有什么做详情页的参考网站,达州建网站文章目录题目描述思路 代码题目描述
第二道图题#xff0c;大概是hot100里唯二的图题了。。
思路 代码
邻接矩阵存储#xff0c;g[i][j] 代表 i / j 的值通过已知的表达式#xff0c;对矩阵进行维护#xff08;包括间接得到的值#xff0c;见注…
文章目录题目描述思路 代码题目描述
第二道图题大概是hot100里唯二的图题了。。
思路 代码
邻接矩阵存储g[i][j] 代表 i / j 的值通过已知的表达式对矩阵进行维护包括间接得到的值见注释的步骤2部分通过三重循环把全部可能的间接关系补上
class Solution {public double[] calcEquation(ListListString equations, double[] values, ListListString queries) {// 1. 统计所有出现的字符并赋予对应的 indexint count 0; MapString, Integer map new HashMap();for(ListString list : equations) {for(String s : list) {if(!map.containsKey(s)) {map.put(s, count);}}}// 1. 邻接矩阵初始化double[][] graph new double[count 1][count 1];for(String s : map.keySet()) {int x map.get(s);graph[x][x] 1.0; // 自身相除得0}int index 0;// 由已知等式更新矩阵值for(ListString list : equations) {String a list.get(0);String b list.get(1);int aa map.get(a);int bb map.get(b);double value values[index];graph[aa][bb] value;graph[bb][aa] 1 / value;}// 2. 通过 Floyd 算法进行计算for(int i 0; i count; i) {for(int j 0; j count; j) {for(int k 0; k count; k) {// Case 1: 已出现过if(j k || graph[j][k] ! 0) {continue;}// Case 2: 传递赋值 j / i x, i / k y j / k x * yif(graph[j][i] ! 0 graph[i][k] ! 0) {graph[j][k] graph[j][i] * graph[i][k];}}}}// 3. 查询矩阵得到答案double[] res new double[queries.size()];for(int i 0; i res.length; i) {ListString q queries.get(i);String a q.get(0);String b q.get(1);// 字符串存在判断if(map.containsKey(a) map.containsKey(b)) {double ans graph[map.get(a)][map.get(b)];// 未知则取 -1.0res[i] (ans 0) ? -1.0 : ans;}else {// 未出现字符也取 -1.0res[i] -1.0;}}return res;}
}
