[LeetCode] 166. Fraction to Recurring Decimal

轉自LeetCode

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

<Solution>
這題是要將分數改寫成小數，如果有循環的部分，就用個括號表示

想法如下

• 先將分子分母都取絕對值，並轉成 long 來計算

• 判斷有沒有正負號

• 是否整除，是的話就回傳答案

• 計算餘數，同時間用一個 hash map 記錄出現過的餘數，以及其對應的位置。一旦餘數重複了，就把對應的位置用括號括起來，然後回傳答案

code如下(參考資料)

	class Solution {
	public:
	string fractionToDecimal(int numerator, int denominator) {
	if(numerator == 0) {
	return "0";
	}
	const long nume = abs(static_cast<long>(numerator));
	const long deno = abs(static_cast<long>(denominator));
	const long quo = nume / deno;
	long rem = nume % deno;
	string quoPart = ((numerator < 0) ^ (denominator < 0)) ? "-" : "";
	quoPart += to_string(quo);
	if(rem == 0) {
	return quoPart;
	}
	//>> rem part
	quoPart += ".";
	string remPart = "";
	unordered_map<long, int> map;
	int pos = 0;
	while(rem != 0) {
	if(map.find(rem) != map.end()) {
	remPart.insert(map[rem], "(");
	remPart += ")";
	break;
	}
	map[rem] = pos++;
	rem *= 10;
	remPart += to_string(rem / deno);
	rem %= deno;
	}
	return quoPart + remPart;
	}
	};

view raw fractionToRecurringDecimal.cpp hosted with ❤ by GitHub