{"id":8877,"date":"2021-11-28T14:20:23","date_gmt":"2021-11-28T22:20:23","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8877"},"modified":"2021-11-28T14:20:41","modified_gmt":"2021-11-28T22:20:41","slug":"leetcode-166-fraction-to-recurring-decimal","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-166-fraction-to-recurring-decimal\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 166. Fraction to Recurring Decimal"},"content":{"rendered":"\n<p>Given two integers representing the&nbsp;<code>numerator<\/code>&nbsp;and&nbsp;<code>denominator<\/code>&nbsp;of a fraction, return&nbsp;<em>the fraction in string format<\/em>.<\/p>\n\n\n\n<p>If the fractional part is repeating, enclose the repeating part in parentheses.<\/p>\n\n\n\n<p>If multiple answers are possible, return&nbsp;<strong>any of them<\/strong>.<\/p>\n\n\n\n<p>It is&nbsp;<strong>guaranteed<\/strong>&nbsp;that the length of the answer string is less than&nbsp;<code>10<sup>4<\/sup><\/code>&nbsp;for all the given inputs.<\/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> numerator = 1, denominator = 2\n<strong>Output:<\/strong> \"0.5\"\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> numerator = 2, denominator = 1\n<strong>Output:<\/strong> \"2\"\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> numerator = 2, denominator = 3\n<strong>Output:<\/strong> \"0.(6)\"\n<\/pre>\n\n\n\n<p><strong>Example 4:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> numerator = 4, denominator = 333\n<strong>Output:<\/strong> \"0.(012)\"\n<\/pre>\n\n\n\n<p><strong>Example 5:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> numerator = 1, denominator = 5\n<strong>Output:<\/strong> \"0.2\"\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>-2<sup>31<\/sup>&nbsp;&lt;=&nbsp;numerator, denominator &lt;= 2<sup>31<\/sup>&nbsp;- 1<\/code><\/li><li><code>denominator != 0<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Hashtable<\/strong><\/h2>\n\n\n\n<p>Time complexity: O(?)<\/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\nclass Solution {\npublic:\n  string fractionToDecimal(int numerator, int denominator) {\n    stringstream ss,ss2;\n\n    long long n = numerator;\n    long long d = denominator;\n\n    if ( n > 0 && d < 0 || n < 0 &#038;&#038; d > 0) {\n      ss << \"-\";\n      n = abs(n);\n      d = abs(d);\n    }\n\n    ss << (n \/ d);\n\n    long long r = n % d;\n\n    bool loop = false;\n    int count = 0;\n    int loop_start;\n\n    if (r) {   \n      n = r;\n      ss << \".\";\n      unordered_map<int, int> rs;\n      rs[r] = 0;\n\n      while (r) {\n        n = n*10;\n        r = n % d;\n        ss2 << (n \/ d);\n        n = r;\n        if (r &#038;&#038; rs.count(r)) {\n          loop = true;\n          loop_start = rs[r];\n          break;\n        }\n        rs[r] = ++count;\n      }\n\n      if (loop) {\n        auto s2 = ss2.str();\n        ss << s2.substr(0, loop_start) << \"(\" << s2.substr(loop_start) << \")\";\n      } else  {\n        ss << ss2.str();\n      }\n    }\n\n    return ss.str();\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given two integers representing the&nbsp;numerator&nbsp;and&nbsp;denominator&nbsp;of a fraction, return&nbsp;the fraction in string format. If the fractional part is repeating, enclose the repeating part in parentheses. If&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[70],"tags":[650,177,4],"class_list":["post-8877","post","type-post","status-publish","format-standard","hentry","category-hashtable","tag-hasthable","tag-medium","tag-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8877","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=8877"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8877\/revisions"}],"predecessor-version":[{"id":8879,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8877\/revisions\/8879"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8877"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8877"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8877"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}