程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> [LeetCode] Fraction to Recurring Decimal

[LeetCode] Fraction to Recurring Decimal

編輯:C++入門知識

[LeetCode] Fraction to Recurring Decimal


 

Fraction to Recurring Decimal


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)".

    題目意思:

    將分數轉化成循環小數。大體思想是:用兩個map分別記錄商及其位置和余數及其位置,若出現了重復的余數,則表示此余數對應位置的商位開始循環。這道題非常多的陷阱。弄了我好久,代碼如下所示

     

    class Solution {
    public:
    	string fractionToDecimal(int numerator, int denominator) {
    		string result = "";
    		long long numberatorL = (long long)numerator;
    		long long denominatorL = (long long)denominator;
    		if (numberatorL * denominatorL < 0){		//注意負數的情況
    			result += "-";
    			numberatorL = -numberatorL;
    		}
    		long long quotient = numberatorL / denominatorL;	//商
    		result += intToStr(quotient);
    		long long remainder = numberatorL % denominatorL;	//余數
    		if (remainder != 0){
    			result += '.';
    			int position = -1;
    			int repeatStartPosition = -1;		//循環起始位
    			map positionToQuotient;	//位置到商,從某個位置開始為循環小數
    			map remainderToPosition;	//余數到位置
    			remainderToPosition.insert(map::value_type(remainder, position));
    			position++;
    			while (remainder != 0){
    				remainder *= 10;
    				quotient = remainder / denominatorL;
    				remainder = remainder % denominatorL;
    				positionToQuotient.insert(map::value_type(position, quotient));
    				map::iterator it = remainderToPosition.find(remainder);
    				if (it != remainderToPosition.end()){	//若余數已經存在過
    					repeatStartPosition = it->second + 1;
    					break;
    				}
    				remainderToPosition.insert(map::value_type(remainder, position));
    				position++;
    			}
    			for (map::iterator it = positionToQuotient.begin(); it != positionToQuotient.end(); it++){
    				if (it->first == repeatStartPosition){
    					result += "(";
    				}
    				result += intToStr(it->second);
    			}
    			if (repeatStartPosition >= 0){
    				result += ")";
    			}
    		}
    		return result;
    	}
    
    private:
    	string intToStr(long long number){
    		string result = "";
    		do{
    			result = (char)(number % 10 + '0') + result;
    			number /= 10;
    		} while (number != 0);
    		return result;
    	}
    };


     

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved