首页 / LUA / 399. Evaluate Division

399. Evaluate Division

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了399. Evaluate Division，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2959字，纯文字阅读大概需要5分钟。

内容图文

Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0.

Example:
Given a / b = 2.0, b / c = 3.0. 
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? . 
return [6.0, 0.5, -1.0, 1.0, -1.0 ].

The input is: vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries , where equations.size() == values.size(), and the values are positive. This represents the equations. Return vector<double>.

According to the example above:

equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ]. 
The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.

Graph, DFS

(1) Build the map, the key is dividend, the value is also a map whose key is divisor and value is its parameter. For example, a / b = 2.0, the map entry is <"a", <"b", 2.0>>. To make searching and calculation easier, we also put b / a = 0.5 into the map.
(2) for each query, use DFS to search divisors recursively

1.hashmap 建图

2. dfs 递归搜索

public class Solution {
    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
        double[] res = new double[queries.length];
        HashMap<String, HashMap<String, Double>> map = new HashMap<String, HashMap<String, Double>>();
        for (int i=0; i<equations.length; i++) {
            String[] equation = equations[i];
            double value = values[i];
            if (!map.containsKey(equation[0])) {
                map.put(equation[0], new HashMap<String, Double>());
                map.get(equation[0]).put(equation[0], 1.0);
            }
            if (!map.containsKey(equation[1])) {
                map.put(equation[1], new HashMap<String, Double>());
                map.get(equation[1]).put(equation[1], 1.0);
            }
            map.get(equation[0]).put(equation[1], value);
            map.get(equation[1]).put(equation[0], 1/value);
        }

        for (int j=0; j<queries.length; j++) {
            res[j] = -1.0; //initialize
            dfs(map, queries[j][0], queries[j][1], new HashSet<String>(), res, j, 1.0);
        }
        return res;
    }
    
    public void dfs(HashMap<String, HashMap<String, Double>> map, String src, String dest, HashSet<String> visited, double[] res, int index, double pathVal) {
        if (!map.containsKey(src) || !map.containsKey(dest)) {
            res[index] = -1.0;
            return;
        }
        if (visited.contains(src)) return;
        HashMap<String, Double> srcNb = map.get(src);
        if (srcNb.containsKey(dest)) {
            res[index] = pathVal * srcNb.get(dest);
            return;
        }
        visited.add(src);
        for (Map.Entry<String, Double> entry : srcNb.entrySet()) {
            String neibor = entry.getKey();
            dfs(map, neibor, dest, visited, res, index, pathVal*entry.getValue());
        }
        visited.remove(src);
    }
}

 

原文：http://www.cnblogs.com/apanda009/p/7162117.html

内容总结

以上是互联网集市为您收集整理的399. Evaluate Division全部内容，希望文章能够帮你解决399. Evaluate Division所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1091131.html

来源：【匿名】