{"id":4615,"date":"2019-01-05T23:15:16","date_gmt":"2019-01-06T07:15:16","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4615"},"modified":"2019-01-12T00:54:44","modified_gmt":"2019-01-12T08:54:44","slug":"leetcode-972-equal-rational-numbers","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/math\/leetcode-972-equal-rational-numbers\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 972. Equal Rational Numbers"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-4-3 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 972. Equal Rational Numbers - \u5237\u9898\u627e\u5de5\u4f5c EP239\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/PAsHEeaB-xA?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>\n<\/div><\/figure>\n\n\n\n<p>Given two strings&nbsp;<code>S<\/code>&nbsp;and&nbsp;<code>T<\/code>, each of which represents a non-negative rational number, return&nbsp;<strong>True<\/strong>&nbsp;if and only if they represent the same number. The strings may use parentheses to denote the repeating part of the rational number.<\/p>\n\n\n\n<p>In general a rational number can be represented using up to&nbsp;three parts: an&nbsp;<em>integer part<\/em>, a&nbsp;<em>non-repeating part,<\/em>&nbsp;and a&nbsp;<em>repeating part<\/em>. The number will be represented&nbsp;in one of the following three ways:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>&lt;IntegerPart&gt;<\/code>&nbsp;(e.g. 0, 12, 123)<\/li><li><code>&lt;IntegerPart&gt;&lt;.&gt;&lt;NonRepeatingPart&gt;<\/code>&nbsp;&nbsp;(e.g. 0.5, 1., 2.12, 2.0001)<\/li><li><code>&lt;IntegerPart&gt;&lt;.&gt;&lt;NonRepeatingPart&gt;&lt;(&gt;&lt;RepeatingPart&gt;&lt;)&gt;<\/code>&nbsp;(e.g. 0.1(6), 0.9(9), 0.00(1212))<\/li><\/ul>\n\n\n\n<p>The repeating portion of a decimal expansion is conventionally denoted within a pair of round brackets.&nbsp; For example:<\/p>\n\n\n\n<p>1 \/ 6 = 0.16666666&#8230; = 0.1(6) = 0.1666(6) = 0.166(66)<\/p>\n\n\n\n<p>Both 0.1(6) or 0.1666(6) or 0.166(66) are correct representations of 1 \/ 6.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted crayon:false\"><strong>Input: <\/strong>S = \"0.(52)\", T = \"0.5(25)\"\n<strong>Output: <\/strong>true\n<strong>Explanation:\n<\/strong>Because \"0.(52)\" represents 0.52525252..., and \"0.5(25)\" represents 0.52525252525..... , the strings represent the same number.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted crayon:false\"><strong>Input: <\/strong>S = \"0.1666(6)\", T = \"0.166(66)\"\n<strong>Output: <\/strong>true\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted crayon:false\"><strong>Input: <\/strong>S = \"0.9(9)\", T = \"1.\"\n<strong>Output: <\/strong>true\n<strong>Explanation: <\/strong>\n\"0.9(9)\" represents 0.999999999... repeated forever, which equals 1.  [<a href=\"https:\/\/en.wikipedia.org\/wiki\/0.999...\" target=\"_blank\" rel=\"noreferrer noopener\">See this link for an explanation.<\/a>]\n\"1.\" represents the number 1, which is formed correctly: (IntegerPart) = \"1\" and (NonRepeatingPart) = \"\".<\/pre>\n\n\n\n<p><strong>Note:<\/strong><\/p>\n\n\n\n<ol class=\"wp-block-list\"><li>Each part consists only of digits.<\/li><li>The&nbsp;<code>&lt;IntegerPart&gt;<\/code>&nbsp;will&nbsp;not begin with 2 or more zeros.&nbsp; (There is no other restriction on the digits of each part.)<\/li><li><code>1 &lt;= &lt;IntegerPart&gt;.length &lt;= 4<\/code><\/li><li><code>0 &lt;= &lt;NonRepeatingPart&gt;.length &lt;= 4<\/code><\/li><li><code>1 &lt;= &lt;RepeatingPart&gt;.length &lt;= 4<\/code><\/li><\/ol>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution1:\u00a0Expend\u00a0the\u00a0string<\/strong><\/h2>\n\n\n\n<p>Extend the string to 16+ more digits and covert it to double.<\/p>\n\n\n\n<p>0.9(9) =&gt; 0.99999999999999 <br>0.(52) =&gt; 0.525252525252525<br>0.5(25) =&gt; 0.5252525252525<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua, running time: 4 ms\nclass Solution {\npublic:\n  bool isRationalEqual(string S, string T) {\n    auto convert = [](string s) {\n      \/\/ 0.1234(567)\n      \/\/ 01234567890\n      \/\/ i = 1, p = 6\n      auto i = s.find('.');\n      auto p = s.find('(');\n      if (p != string::npos) {\n        string r = s.substr(p + 1, s.length() - p - 2);\n        s = s.substr(0, p);\n        while (s.length() < 16)\n          s += r;\n      }\n      return stod(s);\n    };    \n    return abs(convert(S) - convert(T)) < 1e-10;\n  }\n};\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"python\">\nclass Solution:\n  def isRationalEqual(self, S, T):\n    def convert(s):\n      i = s.find('.')\n      p = s.find('(')\n      if p >= 0:\n        r = s[p+1:-1]\n        s = s[0:p]\n        while len(s) < 16:\n          s += r\n      return float(s)\n    return abs(convert(S) - convert(T)) < 1e-10\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\">Solution 2: Convert to a friction number<\/h2>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua, running time: 24 ms.\nclass Friction {\npublic:\n  Friction(long n = 0, long d = 1) {\n    long g = __gcd(n, d);\n    n_ = n \/ g;\n    d_ = d \/ g;\n  }\n  \n  Friction operator+(const Friction& o) const {\n    return Friction(n_ * o.d_ + d_ * o.n_, d_ * o.d_);\n  }\n  \n  bool operator==(const Friction& o) const {\n    return this->n_ * o.d_ == this->d_ * o.n_;\n  }\nprivate:\n  long n_;\n  long d_;\n};\n\n\nclass Solution {\npublic:\n  bool isRationalEqual(string S, string T) {\n    auto convert = [](string s) {      \n      std::regex re(\"(\\\\d+)\\\\.?(\\\\d+)?(\\\\((\\\\d+)\\\\))?\");\n      std::smatch matches;\n      std::regex_match(s, matches, re);\n      string int_part = matches[1].str();\n      string nr_part = matches[2].str();\n      string r_part = matches[4].str();\n      \n      Friction f(stoi(int_part), 1);\n      const int base = pow(10, nr_part.length());\n      if (nr_part.length())\n        f = f + Friction(stoi(nr_part), base);\n      if (r_part.length())\n        f = f + Friction(stoi(r_part), (pow(10, r_part.length()) - 1)  * base);\n      \n      return f;\n    };\n    return convert(S) == convert(T);\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given two strings&nbsp;S&nbsp;and&nbsp;T, each of which represents a non-negative rational number, return&nbsp;True&nbsp;if and only if they represent the same number. The strings may use parentheses&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[49],"tags":[217,31,4],"class_list":["post-4615","post","type-post","status-publish","format-standard","hentry","category-math","tag-hard","tag-math","tag-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4615","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=4615"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4615\/revisions"}],"predecessor-version":[{"id":4625,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4615\/revisions\/4625"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4615"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4615"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4615"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}