精选文章 Fraction to Recurring Decimal

Fraction to Recurring Decimal

作者:Czy_whlg 时间: 2019-11-05 04:12:42
Czy_whlg 2019-11-05 04:12:42

Fraction to Recurring Decimal1 

Example 3:

Input: numerator = 2, denominator = 3
Output: "0.(6)"

1. 解析

题目大意,将分数转换为循环小数,不是很难,关键点就在于如何查找循环的部分

2. 分析

任何有理数都将分为两部分,整数部分和小数部分,故可以将分数分开进行处理

1) 求解整数部分,若当前分子numerator整除分母denominator,即无小数部分,直接返回numerator / denominator

2) 若当前存在小数部分,即不整除,单独求解小数部分,为了方便查找当前小数部分是否为循环小数,利用hashtable进行存储除数和其对应的小数位置,若当前分子numerator不为0:

①若hashtable不存在当前分子numerator,在hashtable中记录下该位置;

②hashtable存在当前分子numerator,则该位置即为循环开始位置,进行处理后直接返回即可;

class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) { 
        bool signal = false;
        if ( (numerator == 0) || (numerator < 0 && denominator < 0) || 
             (numerator > 0 && denominator > 0) )
            signal = true; //正数
        string res = signal ? "" : "-";
        map repeat;
        long long long_numerator = abs((long long)numerator);
        long long long_denominator = abs((long long)denominator);
        if (long_numerator % long_denominator == 0) 
            return res + to_string(long_numerator / long_denominator);
        
        res += to_string(long_numerator / long_denominator) + "."; //整数部分
        long_numerator %= long_denominator;
        
        string str = "";  //小数部分
        int pos = 0;
        while (long_numerator != 0){
            long_numerator *= 10;
            if (repeat.count(long_numerator)){ //找到循环部分
                str.insert(repeat[long_numerator], "(");
                str += ")";
                break;
            }
            else{
                repeat[long_numerator] = pos;
            }
            pos++;
            str += to_string(long_numerator / long_denominator);
            long_numerator %= long_denominator;
        }
        return  res + str;
    }
};

 [1]https://www.cnblogs.com/grandyang/p/4238577.html

 

勿删,copyright占位
分享文章到微博
分享文章到朋友圈

上一篇:redis——内存概述

下一篇:springboot集成graphql(一)

CSDN

CSDN

中国开发者社区CSDN (Chinese Software Developer Network) 创立于1999年,致力为中国开发者提供知识传播、在线学习、职业发展等全生命周期服务。