题解 | #牛群之间的体重比#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param weightRatios string字符串二维数组
     * @param ratioValues double浮点型一维数组
     * @param questions string字符串二维数组
     * @return double浮点型一维数组
     */
    public double[] calcWeightRatios (String[][] weightRatios, double[] ratioValues,
                                      String[][] questions) {
        // write code here
		double[] res = new double[questions.length];
		HashMap<String, String> stringMap = new HashMap<>();
		HashMap<String, Double> map = new HashMap<>();
		for (int i = 0; i < weightRatios.length; i++) {
			String c1 = weightRatios[i][0];
			String c2 = weightRatios[i][1];
			if (!stringMap.containsKey(c1)) {
				stringMap.put(c1, c2);
				map.put(c1, ratioValues[i]);
			} else {
				if (!stringMap.containsKey(c2)) {
					stringMap.put(c2, c1);
					map.put(c2, 1 / ratioValues[i]);
				}
			}
		}
		for (int i = 0; i < questions.length; i++) {
			// 根据0索引的字符在stringMap寻找1索引的字符
			String c1 = questions[i][0];
			String c2 = questions[i][1];
			res[i] = findCharacter_process(c1, c2, stringMap, map);
			if (res[i] == -1.0000) {
				res[i] = 1 / findCharacter_process(c2, c1, stringMap, map);
			}
		}
		return res;
    }
    // [["a","b"],["b","c"]],[2.0,3.0],[["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
    // [6.00000,0.50000,-1.00000,1.00000,-1.00000]
    public double findCharacter_process(String source, String target, HashMap<String, String> stringMap,
			HashMap<String, Double> map) {
		if (stringMap.containsKey(source) && source.equals(target)) {
			return 1.0;
		}
		double res = 1.0;
		String cur = source;
		while (true) {
			// 下面只是能直接找出的情况
			if (stringMap.containsKey(cur)) {
				String c = stringMap.get(cur);
				if (c.equals(target)) {
					return res * map.get(cur);
				}
				if (c == source) {
					return -1;
				}
				res *= map.get(cur);
				cur = c;
			} else {
				return -1;
			}
		}
	}
}

HashMap是去重的，所以如果有两个key值相同但value值不同的元素，就会替换掉一个，所以 最后就会造成结果的不正确性

• 解决：如果key和value都相同，直接去重，如果只有key值相同，那么将这两个中的一个翻转，然后再比较是否还有相同的key，如果有，丢弃
• 如果没有添加到map中，重复此操作，直到map中确保信息都添加进去为止 这样确保了map将信息完全接收(生成了最小生成组)

第二个需要解决的问题：我们如何将map中的值和它们对应的商值映射在一起？,并且怎么通过map找到它们对应的商值？

• 由于我们生成了最小生成组，所以它们的key值是唯一的，所以根据它们的key和value的组合的不同，
• 再次创建一个map1用来映射key和value的double值记作key->double