{"id":1066,"date":"2017-12-01T22:23:54","date_gmt":"2017-12-02T06:23:54","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=1066"},"modified":"2020-09-27T14:35:24","modified_gmt":"2020-09-27T21:35:24","slug":"leetcode-399-evaluate-division","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/graph\/leetcode-399-evaluate-division\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 399. Evaluate Division"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 399. Evaluate Division - \u5237\u9898\u627e\u5de5\u4f5c EP120\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/UwpvInpgFmo?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<p>\u9898\u76ee\u5927\u610f\uff1a\u7ed9\u4f60\u4e00\u4e9b\u542b\u6709\u53d8\u91cf\u540d\u7684\u5206\u5f0f\u7684\u503c\uff0c\u8ba9\u4f60\u8ba1\u7b97\u53e6\u5916\u4e00\u4e9b\u5206\u5f0f\u7684\u503c\uff0c\u5982\u679c\u4e0d\u80fd\u8ba1\u7b97\u8fd4\u56de-1\u3002<\/p>\n<p><strong>Problem:<\/strong><\/p>\n<p>Equations are given in the format\u00a0<code>A \/ B = k<\/code>, where\u00a0<code>A<\/code>\u00a0and\u00a0<code>B<\/code>\u00a0are variables represented as strings, and\u00a0<code>k<\/code>\u00a0is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return\u00a0<code>-1.0<\/code>.<\/p>\n<p><b>Example:<\/b><br \/>\nGiven\u00a0<code>a \/ b = 2.0, b \/ c = 3.0.<\/code><br \/>\nqueries are:\u00a0<code>a \/ c = ?, b \/ a = ?, a \/ e = ?, a \/ a = ?, x \/ x = ? .<\/code><br \/>\nreturn\u00a0<code>[6.0, 0.5, -1.0, 1.0, -1.0 ].<\/code><\/p>\n<p>The input is:\u00a0<code>vector&lt;pair&lt;string, string&gt;&gt; equations, vector&lt;double&gt;&amp; values, vector&lt;pair&lt;string, string&gt;&gt; queries\u00a0<\/code>, where\u00a0<code>equations.size() == values.size()<\/code>, and the values are positive. This represents the equations. Return\u00a0<code>vector&lt;double&gt;<\/code>.<\/p>\n<p>According to the example above:<\/p>\n<pre class=\"\">equations = [ [\"a\", \"b\"], [\"b\", \"c\"] ],\nvalues = [2.0, 3.0],\nqueries = [ [\"a\", \"c\"], [\"b\", \"a\"], [\"a\", \"e\"], [\"a\", \"a\"], [\"x\", \"x\"] ].<\/pre>\n<p>The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.<\/p>\n<p><ins class=\"adsbygoogle\" style=\"display: block; text-align: center;\" data-ad-layout=\"in-article\" data-ad-format=\"fluid\" data-ad-client=\"ca-pub-2404451723245401\" data-ad-slot=\"7983117522\">\u00a0<\/ins><\/p>\n<p><a href=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/12\/399-ep120.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-1072\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/12\/399-ep120.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/12\/399-ep120.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/12\/399-ep120-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/12\/399-ep120-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/p>\n<h1><strong>Solution 1: DFS<\/strong><\/h1>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\n\/\/ Runtime: 3 ms\nclass Solution {\npublic:\n    vector&lt;double&gt; calcEquation(vector&lt;pair&lt;string, string&gt;&gt; equations, vector&lt;double&gt;&amp; values, vector&lt;pair&lt;string, string&gt;&gt; queries) {\n        \/\/ g[A][B] = k -&gt; A \/ B = k\n        unordered_map&lt;string, unordered_map&lt;string, double&gt;&gt; g;        \n        for (int i = 0; i &lt; equations.size(); ++i) {\n            const string&amp; A = equations[i].first;\n            const string&amp; B = equations[i].second;\n            const double k = values[i];\n            g[A][B] = k;\n            g[B][A] = 1.0 \/ k;\n        }\n        \n        vector&lt;double&gt; ans;\n        for (const auto&amp; pair : queries) {\n            const string&amp; X = pair.first;\n            const string&amp; Y = pair.second;\n            if (!g.count(X) || !g.count(Y)) {\n                ans.push_back(-1.0);\n                continue;\n            }\n            unordered_set&lt;string&gt; visited;            \n            ans.push_back(divide(X, Y, g, visited));\n        }\n        return ans;\n    }\nprivate:\n    \/\/ get result of A \/ B\n    double divide(const string&amp; A, const string&amp; B, \n                  unordered_map&lt;string, unordered_map&lt;string, double&gt;&gt;&amp; g,\n                  unordered_set&lt;string&gt;&amp; visited) {        \n        if (A == B) return 1.0;\n        visited.insert(A);\n        for (const auto&amp; pair : g[A]) {\n            const string&amp; C = pair.first;\n            if (visited.count(C)) continue;\n            double d = divide(C, B, g, visited); \/\/ d = C \/ B\n            \/\/ A \/ B = C \/ B * A \/ C\n            if (d &gt; 0) return d * g[A][C];\n        }        \n        return -1.0;\n    }\n};<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Java<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:java decode:true \">\/\/ Updated: 2020\/9\/27\n\/\/ Author: Huahua\n\/\/ Running time: 1 ms\nclass Solution {\n  private Map&lt;String, HashMap&lt;String, Double&gt;&gt; g = new HashMap&lt;&gt;();\n  \n  public double[] calcEquation(List&lt;List&lt;String&gt;&gt; equations, double[] values, List&lt;List&lt;String&gt;&gt; queries) {\n    for (int i = 0; i &lt; equations.size(); ++i) {\n      String x = equations.get(i).get(0);\n      String y = equations.get(i).get(1);\n      double k = values[i];\n      g.computeIfAbsent(x, l -&gt; new HashMap&lt;String, Double&gt;()).put(y, k);\n      g.computeIfAbsent(y, l -&gt; new HashMap&lt;String, Double&gt;()).put(x, 1.0 \/ k);\n    }\n    \n    double[] ans = new double[queries.size()];\n    \n    for (int i = 0; i &lt; queries.size(); ++i) {      \n      String x = queries.get(i).get(0);\n      String y = queries.get(i).get(1);\n      if (!g.containsKey(x) || !g.containsKey(y)) {\n        ans[i] = -1.0;\n      } else {        \n        ans[i] = divide(x, y, new HashSet&lt;String&gt;());\n      }\n    }    \n    return ans;\n  }\n  \n  private double divide(String x, String y, Set&lt;String&gt; visited) {\n    if (x.equals(y)) return 1.0;\n    visited.add(x);\n    if (!g.containsKey(x)) return -1.0;\n    for (String n : g.get(x).keySet()) {\n      if (visited.contains(n)) continue;\n      visited.add(n);\n      double d = divide(n, y, visited);\n      if (d &gt; 0) return d * g.get(x).get(n);\n    }\n    return -1.0;\n  }\n}<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:default decode:true \">\"\"\"\nAuthor: Huahua\nRunning time: 32 ms (beats 100%)\n\"\"\"\nclass Solution:\n  def calcEquation(self, equations, values, queries):\n    def divide(x, y, visited):\n      if x == y: return 1.0\n      visited.add(x)\n      for n in g[x]:\n        if n in visited: continue\n        visited.add(n)\n        d = divide(n, y, visited)\n        if d &gt; 0: return d * g[x][n]\n      return -1.0\n    \n    g = collections.defaultdict(dict)\n    for (x, y), v in zip(equations, values):      \n      g[x][y] = v\n      g[y][x] = 1.0 \/ v\n    \n    ans = [divide(x, y, set()) if x in g and y in g else -1 for x, y in queries]\n    return ans<\/pre>\n<\/div><\/div>\n<p><script async=\"\" src=\"https:\/\/pagead2.googlesyndication.com\/pagead\/js\/adsbygoogle.js\"><\/script><br \/>\n<ins class=\"adsbygoogle\" style=\"display: block;\" data-ad-format=\"fluid\" data-ad-layout-key=\"-fb+5w+4e-db+86\" data-ad-client=\"ca-pub-2404451723245401\" data-ad-slot=\"2162692788\"><\/ins><br \/>\n<script><br \/>\n     (adsbygoogle = window.adsbygoogle || []).push({});<br \/>\n<\/script><\/p>\n<h1><strong>Solution 2:\u00a0Union Find<\/strong><\/h1>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\n\/\/ Runtime: 3 ms\nclass Solution {\npublic:\n  vector&lt;double&gt; calcEquation(const vector&lt;pair&lt;string, string&gt;&gt;&amp; equations, vector&lt;double&gt;&amp; values, const vector&lt;pair&lt;string, string&gt;&gt;&amp; queries) {\n  \/\/ parents[\"A\"] = {\"B\", 2.0} -&gt; A = 2.0 * B\n  \/\/ parents[\"B\"] = {\"C\", 3.0} -&gt; B = 3.0 * C\n  unordered_map&lt;string, pair&lt;string, double&gt;&gt; parents;\n\n  for (int i = 0; i &lt; equations.size(); ++i) {\n    const string&amp; A = equations[i].first;\n    const string&amp; B = equations[i].second;\n    const double k = values[i];\n    \/\/ Neighter is in the forrest\n    if (!parents.count(A) &amp;&amp; !parents.count(B)) {\n      parents[A] = {B, k};\n      parents[B] = {B, 1.0};\n    } else if (!parents.count(A)) {\n      parents[A] = {B, k};\n    } else if (!parents.count(B)) {\n      parents[B] = {A, 1.0 \/ k};\n    } else {\n      auto&amp; rA = find(A, parents);\n      auto&amp; rB = find(B, parents);      \n      parents[rA.first] = {rB.first, k \/ rA.second * rB.second};\n    }    \n  }\n\n  vector&lt;double&gt; ans;\n  for (const auto&amp; pair : queries) {\n    const string&amp; X = pair.first;\n    const string&amp; Y = pair.second;\n    if (!parents.count(X) || !parents.count(Y)) {\n      ans.push_back(-1.0);\n      continue;\n    }\n    auto&amp; rX = find(X, parents); \/\/ {rX, X \/ rX}\n    auto&amp; rY = find(Y, parents); \/\/ {rY, Y \/ rY}\n    if (rX.first != rY.first)\n      ans.push_back(-1.0);\n    else \/\/ X \/ Y = (X \/ rX \/ (Y \/ rY))\n      ans.push_back(rX.second \/ rY.second);\n  }\n  return ans;\n}\nprivate:\n  pair&lt;string, double&gt;&amp; find(const string&amp; C, unordered_map&lt;string, pair&lt;string, double&gt;&gt;&amp; parents) {\n    if (C != parents[C].first) {\n      const auto&amp; p = find(parents[C].first, parents);\n      parents[C].first = p.first;\n      parents[C].second *= p.second;\n    }\n    return parents[C];\n  }\n};<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Java<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:java decode:true \">\/\/ Updated: 9\/27\/2020\n\/\/ Author: Huahua\n\/\/ Running time: 3 ms\nclass Solution {\n  class Node {\n    public String parent;\n    public double ratio;\n    public Node(String parent, double ratio) {\n      this.parent = parent;\n      this.ratio = ratio;\n    }\n  }\n  \n  class UnionFindSet {\n    private Map&lt;String, Node&gt; parents = new HashMap&lt;&gt;();\n    \n    public Node find(String s) {\n      if (!parents.containsKey(s)) return null;\n      Node n = parents.get(s);\n      if (!n.parent.equals(s)) {\n        Node p = find(n.parent);\n        n.parent = p.parent;\n        n.ratio *= p.ratio;\n      }\n      return n;\n    }\n    \n    public void union(String A, String B, double ratio) {\n      boolean hasA = parents.containsKey(A);\n      boolean hasB = parents.containsKey(B);\n      if (!hasA &amp;&amp; !hasB) {\n        parents.put(A, new Node(B, ratio));\n        parents.put(B, new Node(B, 1.0));\n      } else if (!hasA) {\n        parents.put(A, new Node(B, ratio));\n      } else if (!hasB) {\n        parents.put(B, new Node(A, 1.0 \/ ratio));      \n      } else {\n        Node rA = find(A);\n        Node rB = find(B);\n        parents.put(rA.parent, \n          new Node(rB.parent, ratio \/ rA.ratio * rB.ratio));        \n      }\n    }\n  }\n  \n  public double[] calcEquation(List&lt;List&lt;String&gt;&gt; equations, double[] values, List&lt;List&lt;String&gt;&gt; queries)  {\n    UnionFindSet u = new UnionFindSet();\n    \n    for (int i = 0; i &lt; equations.size(); ++i)\n      u.union(equations.get(i).get(0), equations.get(i).get(1), values[i]);\n    \n    double[] ans = new double[queries.size()];\n    \n    for (int i = 0; i &lt; queries.size(); ++i) {      \n      Node rx = u.find(queries.get(i).get(0));\n      Node ry = u.find(queries.get(i).get(1));\n      if (rx == null || ry == null || !rx.parent.equals(ry.parent))\n        ans[i] = -1.0;\n      else\n        ans[i] = rx.ratio \/ ry.ratio;\n    }\n    return ans;\n  }\n}<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:default decode:true \">\"\"\"\nAuthor: Huahua\nRunning time: 32 ms (beats 100%)\n\"\"\"\nclass Solution:\n  def calcEquation(self, equations, values, queries):\n    def find(x):\n      if x != U[x][0]:\n        px, pv = find(U[x][0])\n        U[x] = (px, U[x][1] * pv)\n      return U[x]\n    \n    def divide(x, y):\n      rx, vx = find(x)\n      ry, vy = find(y)\n      if rx != ry: return -1.0\n      return vx \/ vy\n    \n    U = {}\n    for (x, y), v in zip(equations, values):      \n      if x not in U and y not in U:\n        U[x] = (y, v)\n        U[y] = (y, 1.0)\n      elif x not in U:\n        U[x] = (y, v)\n      elif y not in U:\n        U[y] = (x, 1.0 \/ v)\n      else:\n        rx, vx = find(x)\n        ry, vy = find(y)\n        U[rx] = (ry, v \/ vx * vy)\n    \n    ans = [divide(x, y) if x in U and y in U else -1 for x, y in queries]\n    return ans\n<\/pre>\n<\/div><\/div>\n<p><strong>Related Problems:<\/strong><\/p>\n<ul>\n<li><a href=\"http:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-684-redundant-connection\/\">[\u89e3\u9898\u62a5\u544a] LeetCode 684. Redundant Connection<\/a><\/li>\n<li><a href=\"http:\/\/zxi.mytechroad.com\/blog\/graph\/leetcode-547-friend-circles\/\">[\u89e3\u9898\u62a5\u544a] LeetCode 547. Friend Circles<\/a><\/li>\n<li><a href=\"http:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-737-sentence-similarity-ii\/\">[\u89e3\u9898\u62a5\u544a] LeetCode 737. Sentence Similarity II<\/a><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>\u9898\u76ee\u5927\u610f\uff1a\u7ed9\u4f60\u4e00\u4e9b\u542b\u6709\u53d8\u91cf\u540d\u7684\u5206\u5f0f\u7684\u503c\uff0c\u8ba9\u4f60\u8ba1\u7b97\u53e6\u5916\u4e00\u4e9b\u5206\u5f0f\u7684\u503c\uff0c\u5982\u679c\u4e0d\u80fd\u8ba1\u7b97\u8fd4\u56de-1\u3002 Problem: Equations are given in the format\u00a0A \/ B = k, where\u00a0A\u00a0and\u00a0B\u00a0are variables represented as strings, and\u00a0k\u00a0is a real number (floating point number). Given&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[76],"tags":[33,77,217,113],"class_list":["post-1066","post","type-post","status-publish","format-standard","hentry","category-graph","tag-dfs","tag-graph","tag-hard","tag-union-find","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1066","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=1066"}],"version-history":[{"count":25,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1066\/revisions"}],"predecessor-version":[{"id":7437,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1066\/revisions\/7437"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=1066"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=1066"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=1066"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}