找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 11159|回复: 19
收起左侧

[米群网刷题小分队] [Leetcode] 新题 Fraction to Recurring Decimal

  [复制链接]
发表于 12-16-2014 11:26 AM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 cpcs 于 12-16-2014 12:29 PM 编辑

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

For example,

  • Given numerator = 1, denominator = 2, return "0.5".
  • Given numerator = 2, denominator = 1, return "2".
  • Given numerator = 2, denominator = 3, return "0.(6)".

Credits:
Special thanks to @Shangrila for adding this problem and creating all test cases.


分析: 这题数据很牛,但是不极端。 我的意思是:

(1)牛的意思是: 分子,分母出现了正负数,以及负数最小值,所以如果都变成正数,会溢出,需要long long

(2)不极端的意思是: 循环节不会太长。因为确实可以构造出寻环节是接近分母那么长的数。 例如 1/1999999943 有兴趣的可以试试,无论用什么办法存余数,空间是不够的,就算空间够,输出那么多位时间也是不够的。

思路: 就是模拟我们手算做除法的过程。我们就是用分子除以分母,然后保存前一次的余数,每次把余数*10,再除以分母,保存商,再保存余数……如此往复。当余数为0的时候,就除尽了。当余数在之前出现的时候,我们就找到了一个寻环节。所以我们需要一个结构保存这个余数在什么时候出现。余数两次出现的之间部分的商,就是一个寻环节。

时间复杂度: 显然这个时间复杂度取决于寻环节的长度……寻环节的长度,根据抽屉原理,余数最多有分母那么多种,所以循环节的长度可以达到分母。所以时间复杂度和空间复杂度都是O(分母),这还是很大的。这也决定了,我们不能一次性开一个分母那么大的数组。因为存余数出现的最直接的办法是用一个数组have[0..分母 - 1]来记录该余数什么时候出现的,起初都设置为-1来表示没出现过,但这太大了。就算寻环节没那么长,我们也需要那么长的数组。所以这个题记录余数出现位置的时候,需要用map或者hash,我就用c++的unordered_map了。

其余就是输出格式上的处理了。

代码:

  1. class Solution {
  2. public:
  3.     string fractionToDecimal(int numerator, int denominator) {
  4.         ostringstream out;
  5.         long long Numerator = numerator, Denominator = denominator;
  6.         if (Denominator < 0) {
  7.             Denominator = -Denominator;
  8.             Numerator = -Numerator;
  9.             
  10.         }
  11.         if (Numerator < 0) {
  12.              Numerator = -Numerator;
  13.              out << "-";
  14.         }
  15.         out << (Numerator / Denominator);
  16.         long long remainder = Numerator % Denominator;
  17.         if (remainder == 0) {
  18.             return out.str();
  19.         }
  20.         out<< ".";
  21.         vector<int> save;
  22.         unordered_map<int,int> have;
  23.         for (int i = 0; remainder && (have.find(remainder) == have.end()); ++i) {
  24.             have[remainder] = i;
  25.             remainder *= 10;
  26.             save.push_back(remainder / Denominator);
  27.             remainder %= Denominator;
  28.         }
  29.         if (remainder) {
  30.             for (int j = 0; j < have[remainder]; ++j) {
  31.                 out << save[j];
  32.             }
  33.             out << "(";
  34.             for (int j = have[remainder]; j < save.size(); ++j) {
  35.                 out << save[j];
  36.             }
  37.             out << ")";
  38.         }
  39.         else {
  40.             for (int j = 0; j < save.size(); ++j) {
  41.                 out << save[j];
  42.          
  43.             }
  44.         }
  45.         return out.str();
  46.         
  47.     }
  48. };
复制代码


点评

补充下 remainder在map里可以是int 因为余数达不到最大绝对值的整数, 但是因为reminder要*10,所以map的key用int 而reminder还应该用long long。另外,save里面的数字是0-9,所以可以用int  发表于 12-16-2014 01:20 PM

本帖被以下淘专辑推荐:

我们始终相信IT会持续改造甚至创新传统行业,我们始终全面看好咱们的CS专业!

84

主题

32

精华

1278

积分

顶级会员

Rank: 6Rank: 6

积分
1278

活跃会员热心会员最佳新人精华帖之王

发表于 12-16-2014 12:34 PM | 显示全部楼层
赞,这题我面gg和fb都遇到过。。。
回复 支持 反对

使用道具 举报

 楼主| 发表于 12-16-2014 01:17 PM | 显示全部楼层
-_- 发表于 12-16-2014 12:34 PM
赞,这题我面gg和fb都遇到过。。。

面试 分子分母没那么变态吧。。。
我们始终相信IT会持续改造甚至创新传统行业,我们始终全面看好咱们的CS专业!
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表