166. Fraction to Recurring Decimal

发表于 | 分类于 | 阅读次数
字数统计 1,636 | 阅读时长 7

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

Hint:
No scary math, just apply elementary math knowledge.Still remember how to perform a long division ?
Try a long division on 4 / 9, the repeating part is obvious.Now try 4 / 333. Do you see a pattern ?
Be wary of edge cases!List out as many test cases as you can think of and test your code thoroughly.

题意：

　　给定两个整数表示一个分数的分子和分母，返回字符串格式的分数。
　　如果小数部分是重复的，把重复部分写在括号中构成字符串。
　　提示：
　　　　只需要运用初等数学知识，要运用进行长除法。
　　　　尝试长除法的4 / 9，重复的部分是明显的。现在试4 / 333，能看长除法模式。

思路：

　　有以下几种情况:

  1. 如果可以直接除尽, 那么最好, 直接返回
  2. 如果不能直接除尽, 那么先取整数, 再计算小数. 计算小数部分时就是每次取商, 又可分为能除尽, 和循环小数
  3. 如果能除尽那么当最后可以整除的时候返回结果
  4. 比较麻烦的是循环小数. 我们需要将每次的被除数和当前商的位置用一个hash表存起来, 这样当某次发现相同的被除数时说明出现了循环, 那么就加在第一次出现这个被除数的商的位置加括号，并且在做运算的时候可能会越界, 因此我们要将除数和被除数都以long类型存储, 并且在运算之前将符号先提取出来。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
	string fractionToDecimal(int numerator, int denominator) {
		if (numerator == 0) return "0";
		long num1 = fabs(numerator), num2 = fabs(denominator);
		int flag = (numerator>0 ^ denominator>0) ? 1 : 0;
		string ans = (flag ? "-" : "") + to_string(num1 / num2);
		if (num1%num2 == 0) return ans;
		unordered_map<int, int> hash;
		num1 = num1%num2;
		ans += ".";
		while (!hash.count(num1))
		{
			hash[num1] = ans.size();
			num1 *= 10;
			ans += to_string(num1 / num2);
			if (num1 % num2 == 0) return ans;
			num1 = num1%num2;
		}
		ans.insert(hash[num1], 1, '(');
		ans += ')';
		return ans;
	}
};

扩展：

　　计算机原码、补码、反码知识。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/*是int是4个字节表示,也就是32位.最高位是符号位,取值范围是：- 2 ^ 31-- - 2 ^ 31 - 1
		
	k位的二进制整数可以表示的状态共2^k种，所以，负数有2^(k-1)个。int型占4个字节，有32位，所以负数有2^31个，最小的负数就是-2^31=-2147483648了。

	二进制数,
	正数的反码和补码就是它自己，或说正数没有反码和补码。

	负数有反码和补码。
	负数反码，符号位搁置不动，其它位，把原码 1 变0， 原码0 变1。
	负数补码，等于反码加 1。

	负数的补码为取反加1，由于10000000，最高位为1，可知是负数，先减一，为01111111，再取反10000000，得到128，所以原数为-128

	在32位操作系统中，由于是二进制，其能最大存储的数据是1111111111111111111111111111111
	所需知识点:
	1：在计算机中整数的存储
	1.1：整数位正数时，以原码形式存储；为负数时以补码形式存储。
	1.2：正数的补码，原码，反码是一样的；
	负数的反码是将除符号位以外的其他位全部取反得到（例：原码1000 0001，其反码为1111 1110）；
	负数的补码是将这个负数的反码加1 得到（例：原码1000 0001，其反码为1111 1110，其补码为1111 1111）。
	1.3：已知一个原码A的补码B，要求得这个原码A，只需要求得这个已知的补码B的补码C，这个补码的补码C就是已知的补码的原码A。
	(例：已知原码A的补码B为：1111 1111，B的反码为：1000 0000，B的补码为：1000 0001)。
	1.4:32位的二进制数用16进制表示方法：将32位的二进制数的每相邻4位作为一个二进制数，计算出值，再用1位16进制数表示。
	（例：1111  1111   1111   1111   1111   1111   1111   1111就可以表示为 f f f f    f f f f,因为二进制数1111是15,16进制的15表示为 f ）。
	最小值：
	0x8000 0000为带符号整型数的最小值。用二进制表示为1000  0000  0000  0000    0000  0000  0000  0000；
	因为是带符号型所以最后面的1是符号位，而且这个二进制数只是原码A的补码B，因为符号位是1，表示负数，所以需要求得它B的补码C才能知道这个数的值是多大。它的反码为1111  1111   1111   1111     1111   1111   1111   1111，
	它的补码C是反码加一，进一位，为：1   1000   0000   0000   0000   0000      0000   0000   0000   0000；
	这个补码C就是原来二进制数的原码，
	它的大小是2的31次方，即2147483648，所以这个数的值是-2147483648。是带符号整形的最小值。不带符号整型的最小值是0

	若果0x8000 0000是一个无符号型整数，那么它表示为二进制数为：1000   0000   0000   0000      0000   0000   0000   0000。
	没有符号位，直接得它的值为2的31次方，为2147483648。
	最大值：
	0xFFFF  FFFF为不带符号整型的最大值，用二进制表示为：1111   1111   1111   1111        1111   1111   1111   1111
	它的大小是2的32次方减1，得到4294967296 - 1 = 4294967295。是不带符号整型的最大值。带符号整型的最大值在后面详述。

	若果0xFFFF  FFFF是一个带符号整型，那么它表示为二进制数为：1111   1111   1111   1111      1111   1111   1111   1111
	最后一位数1是符号位，这个二进制数是负数，需要求得它的补码才能知道它的值，它是某一个数的原码A的补码B。
	可以求得它的反码为1000   0000   0000   0000       0000   0000   0000   0000   ，
	反码加1得到它的补码为：1000   0000   0000   0000      0000   0000   0000   0001。
	求得它的值为-1。

	0x7FFF  FFFF是带符号整型的最大值，它用二进制数表示为：0111   1111   1111   1111     1111   1111   1111   1111。
	它的最后一位是符号位0，所以是正数，它的原码，反码，补码都是一样的。
	它的值为2的32次方减1，为：2147483647。是带符号整型的最大值。
	*/