399. 除法求值

今天药忘吃喽~ 2022-11-28 13:35 136阅读 0赞

# 题目： #

[399. 除法求值][399.]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center]

# 题解：并查集 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 4]

# 代码：并查集 #

import java.util.*;
    
    public class code399 { 
    
        /** * key : 当前节点 value : 其父节点 */
        private Map<String, String> parents = new HashMap<>();
    
        /** * key : 当前节点 value : 父节点/当前节点 */
        private Map<String, Double> values = new HashMap<>();
    
        public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) 
        { 
            for (int i = 0; i < equations.size(); i++) 
            { 
                union(equations.get(i).get(0), equations.get(i).get(1), values[i]);
            }
            double[] result = new double[queries.size()];
            for (int i = 0; i < queries.size(); i++) 
            { 
                String e = queries.get(i).get(0);
                String q = queries.get(i).get(1);
                if (!(parents.containsKey(e) && parents.containsKey(q))) 
                { 
                    result[i] = -1;
                    continue;
                }
                if (e.equals(q)) 
                { 
                    result[i] = 1;
                    continue;
                }
                String r1 = root(e);
                String r2 = root(q);
                if (!r1.equals(r2)) 
                { 
                    // 如果两者不相等，说明两个节点是不连通的
                    result[i] = -1;
                    continue;
                }
                result[i] = pm(q) / pm(e);
            }
            return result;
        }
    
        private void union(String parent, String child, double value) 
        { 
            add(parent);
            add(child);
            String r1 = root(parent);
            String r2 = root(child);
            if (!r1.equals(r2)) 
            { 
                parents.put(r2, r1);
                values.put(r2, value * (pm(parent) / pm(child)));
            }
        }
    
        private void add(String x) 
        { 
            if (!parents.containsKey(x)) 
            { 
                parents.put(x, x);
                values.put(x, 1.0);
            }
        }
    
        /** * 找到x的根节点 */
        private String root(String x) 
        { 
            while (!parents.get(x).equals(x)) 
            { 
                x = parents.get(x);
            }
            return x;
        }
    
        /** * 循环的pm函数 */
        private double pm(String x) 
        { 
            double v = 1;
            while (!parents.get(x).equals(x)) 
            { 
                v *= values.get(x);
                x = parents.get(x);
            }
            return v;
        }
    
        // /**
        // * 递归的pm函数
        // * 
        // * @param x
        // * @return
        // */
        // private double pm(String x) 
        // { 
        // return parents.get(x).equals(x) ? 1 : values.get(x) * pm(parents.get(x));
        // }
    
        public static void main(String[] args) { 
    
        }
    }

# 参考： #

1.  [你真的知道并查集的构造过程吗？使用数学公式梳理一遍][Link 1]
2.  [C++ 带权值的并查集][C_]
3.  [小白都能看懂的解析:来自并查集的问候][Link 2]
4.  [带权并查集，非常好的带权并查集例题][Link 3]
5.  [先构造图再dfs的python实现][dfs_python]
6.  [记录三种方法][Link 4]
7.  [BFS一次搞定 时间100%][BFS_ _100]
8.  [Java 时间100%][Java _100]

[399.]: https://leetcode-cn.com/problems/evaluate-division/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/60c6b365a07249e2880aa470978d1e87.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221124/2d7db216b40641b5945cfa457c1aaa7e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221124/e38b709c570947668a0a344099f027f1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221124/4ae9b61564cb45be9d53b2e44c9d2315.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221124/d1b417aea9174bc48ebbd47a0d40528f.png
[Link 1]: https://leetcode-cn.com/problems/evaluate-division/solution/ni-zhen-de-zhi-dao-bing-cha-ji-de-gou-zao-guo-chen/
[C_]: https://leetcode-cn.com/problems/evaluate-division/solution/c-dai-quan-zhi-de-bing-cha-ji-by-wen-zhong-qiu-she/
[Link 2]: https://leetcode-cn.com/problems/evaluate-division/solution/xiao-bai-du-neng-kan-dong-de-jie-xi-lai-zi-bing-ch/
[Link 3]: https://leetcode-cn.com/problems/evaluate-division/solution/dai-quan-bing-cha-ji-fei-chang-hao-de-dai-quan-bin/
[dfs_python]: https://leetcode-cn.com/problems/evaluate-division/solution/xian-gou-zao-tu-zai-dfsde-pythonshi-xian-by-mai-ma/
[Link 4]: https://leetcode-cn.com/problems/evaluate-division/solution/ji-lu-san-chong-fang-fa-by-frank588/
[BFS_ _100]: https://leetcode-cn.com/problems/evaluate-division/solution/bfsyi-ci-gao-ding-shi-jian-100-by-tomwillow/
[Java _100]: https://leetcode-cn.com/problems/evaluate-division/solution/java-shi-jian-100-by-jiaxin-2/