8000 update the new better solution for "Fraction to Recurring Decimal" · nimishgupta/leetcode@846045c · GitHub
[go: up one dir, main page]
Skip to content

Commit 846045c

Browse files
haoelhaoel
committed
update the new better solution for "Fraction to Recurring Decimal"
1 parent c248472 commit 846045c

File tree

1 file changed

+28
-96
lines changed

1 file changed

+28
-96
lines changed

‎src/fractionToRecurringDecimal/fractionToRecurringDecimal.cpp

Lines changed: 28 additions & 96 deletions
Original file line numberDiff line numberDiff line change
@@ -22,8 +22,10 @@
2222
#include <iostream>
2323
#include <sstream>
2424
#include <string>
25+
#include <map>
2526
using namespace std;
2627

28+
2729
/*
2830
* Be careful the following cases:
2931
*
@@ -41,124 +43,54 @@ using namespace std;
4143
* > 1/17 = 0.(0588235294117647)
4244
*/
4345

44-
45-
// Notes:
46-
// > check 3 times repeated-decimail numbers
47-
// > using c-style string for performance
48-
bool checkRepeat(string &dec) {
49-
50-
size_t dot = dec.find('.') + 1;
51-
const char *p = dec.c_str() + dot ;
52-
53-
//for case: 0.000
54-
if (atoi(p) ==0 ) return false;
55-
56-
//check 3 times repeated string
57-
size_t len = dec.size();
58-
//static string s1, s2, s3;
59-
for(int i=2; i<=(len-dot)/3; i++) {
60-
int j=0;
61-
const char *p1 = dec.c_str()+len - i;
62-
const char *p2 = dec.c_str()+len - i*2;
63-
const char *p3 = dec.c_str()+len - i*3;
64-
for(; j<i; j++, p1++, p2++, p3++){
65-
if (*p1!=*p2 || *p1 != *p3){
66-
break;
67-
}
68-
}
69-
if ( i == j) {
70-
dec.erase(dec.end()-i*2, dec.end());
71-
dec.insert(dec.end()-i,'(');
72-
dec.push_back(')');
73-
return true;
74-
}
75-
}
76-
return false;
77-
}
78-
79-
/*
80-
* 0.16
81-
* -------
82-
*6 ) 1.00
83-
* 0
84-
* -
85-
* 1 0 <-- Remainder=1, mark 1 as seen at position=0.
86-
* - 6
87-
* ---
88-
* 40 <-- Remainder=4, mark 4 as seen at position=1.
89-
* - 36
90-
* ---
91-
* 4 <-- Remainder=4 was seen before at position=1, so the fractional part which is 16 starts repeating at position=1 => 1(6).
92-
*/
93-
9446
string fractionToDecimal(int numerator, int denominator) {
9547
string result;
9648
//deal with the `ZERO` cases
9749
if (denominator == 0){ return result; }
9850
if (numerator == 0) { return "0"; }
99-
51+
10052
//using long long type make sure there has no integer overflow
10153
long long n = numerator;
10254
long long d = denominator;
10355

10456
//deal with negtive cases
105-
int sign = 1;
106-
if ( n < 0 ) {
107-
n = -n;
108-
sign = -sign;
109-
}
110-
if ( d < 0 ) {
111-
d = -d;
112-
sign = -sign;
113-
}
114-
115-
if (sign < 0){
57+
bool sign = ((float)numerator/denominator >= 0);
58+
if ( n < 0 ){ n = -n; }
59+
if ( d < 0 ){ d = -d; }
60+
if (sign == false){
11661
result.push_back('-');
11762
}
11863

119-
//real work
120-
long long remainder = 0;
121-
long long division = 0;
122-
bool point = false;
123-
124-
while( n != 0 ) {
125-
126-
division = n / d;
127-
remainder = n % d;
128-
129-
if (division >=10){
130-
ostringstream oss;
131-
oss << division;
132-
result += oss.str();
133-
}else{
134-
result.push_back( division + '0' );
135-
}
64+
long long remainder = n % d;
65+
6D40 long long division = n / d;
66+
ostringstream oss;
67+
oss << division;
68+
result += oss.str();
69+
if (remainder == 0){
70+
return result;
71+
}
72+
//remainder has value, the result is a float
73+
result.push_back('.');
13674

137-
if ( point == false && remainder !=0 ){
138-
result.push_back('.');
139-
point = true;
140-
}
75+
//using a map to recorder all of reminders and it's position.
76+
//if the reminder appeared before, which means the repeated loop begin.
77+
//In C++11, it's better to use unordered_map
78+
map<long long, int> rec;
14179

142-
//deal with case only have one number repeated. e.g. 1/3 = 0.3333
143-
if ( point == true && n == remainder * 10 ) {
144-
result.insert(result.end()-1, '(');
80+
for (int pos=result.size(); remainder!=0; pos++, remainder=(remainder*10)%d ) {
81+
if (rec.find(remainder) != rec.end()) {
82+
result.insert(result.begin()+rec[remainder], '(');
14583
result.push_back(')');
146-
break;
84+
return result;
14785
}
148-
149-
//deal with the case which have multiple number repeated. e.g. 25/99 = 0.252525...
150-
if (checkRepeat(result) == true){
151-
break;
152-
}
153-
154-
155-
n = remainder * 10;
156-
86+
rec[remainder] = pos;
87+
result.push_back((remainder*10)/d + '0');
15788
}
15889

15990
return result;
16091
}
16192

93+
16294
void test(int num, int deno)
16395
{
16496
cout << "numerator: " << num << "\tdenominator: " << deno << "\tresult: " << fractionToDecimal(num, deno) << endl;

0 commit comments

Comments
 (0)
0