题目描述
Given two strings S
and T
, each of which represents a non-negative rational number, return True if and only if they represent the same number. The strings may use parentheses to denote the repeating part of the rational number.
In general a rational number can be represented using up to three parts: an integer part, a non-repeating part, and a repeating part. The number will be represented in one of the following three ways:
<IntegerPart>
(e.g. 0, 12, 123)<IntegerPart><.><NonRepeatingPart>
(e.g. 0.5, 1., 2.12, 2.0001)<IntegerPart><.><NonRepeatingPart><(><RepeatingPart><)>
(e.g. 0.1(6), 0.9(9), 0.00(1212))
The repeating portion of a decimal expansion is conventionally denoted within a pair of round brackets. For example:
1 / 6 = 0.16666666… = 0.1(6) = 0.1666(6) = 0.166(66)
Both 0.1(6) or 0.1666(6) or 0.166(66) are correct representations of 1 / 6.
Example 1:
Input: S = "0.(52)", T = "0.5(25)"
Output: true
Explanation:
Because "0.(52)" represents 0.52525252..., and "0.5(25)" represents 0.52525252525..... , the strings represent the same number.
Example 2:
Input: S = "0.1666(6)", T = "0.166(66)"
Output: true
Example 3:
Input: S = "0.9(9)", T = "1."
Output: true
Explanation:
"0.9(9)" represents 0.999999999... repeated forever, which equals 1. [See this link for an explanation.]
"1." represents the number 1, which is formed correctly: (IntegerPart) = "1" and (NonRepeatingPart) = "".
Note:
-
**
-
Each part consists only of digits.
- The
<IntegerPart>
will not begin with 2 or more zeros. (There is no other restriction on the digits of each part.) 1 <= <IntegerPart>.length <= 4
0 <= <NonRepeatingPart>.length <= 4
1 <= <RepeatingPart>.length <= 4
题意:给定两个字符串 S
和T
,每个字符串代表一个非负有理数,只有当它们表示相同的数字时才返回 true;否则,返回 false。字符串中可以使用括号来表示有理数的重复部分。
算法1
题解:我们知道任何有理数都可以表示分数,我们观察到数字长度不会超过12,所以我们直接采用转化成分数来比较即可。我们依次来看三个部分:
-
整数部分,整数部分假设为$x_1$,那么转化成分数就是$\frac{x_1}{1}$
-
小数非重复部分,假设为$x_2$,长度为$k$,那么转化成分数就是$\frac{x_2}{10^k}$
-
小数重复部分,假设为$x_3$,长度为$t$,那么转化成分数就是$\frac{x_3}{10^k(10^t-1)}$
首先假设循环小数为0.12(34),那么$k=2,t=2$,0.00(34)有如下表达:
$$
0.00(34) = \frac{1}{10^k} * 0.(34)\\
0.(34) = 0.3434343434…\\
=0.34 + 0.0034 + 0.000034 + …\\
=0.34 * (1 + \frac{1}{10^t} + \frac{1}{10^{2t}} + …)等比数列+极限\\
=0.34 * (\frac{1}{10^t - 1})\\
$$
我们可以通过GCD
函数来进行通分和化简,最后判断两个分数是否完全相同即可。
class Solution {
public:
typedef long long LL;
int pow_of_10[5] = {1,10,100,1000,10000};
struct frac{
LL up,down;
frac(){}
frac(LL up,LL down):up(up),down(down){}
};
LL gcd(LL x,LL y)
{
if(y == 0) return x;
return gcd(y,x % y);
}
struct frac add(struct frac frac1,struct frac frac2)
{
LL up = frac1.up * frac2.down + frac1.down * frac2.up;
LL down = frac1.down * frac2.down;
LL cd = gcd(up,down);
return frac(up / cd,down/cd);
}
struct frac cal(string &s)
{
int n = s.length();
string s_int = "",s_non = "",s_rep = "";
int i = 0;
for(i = 0 ; i < n && s[i] !='.' ; i ++)
s_int += s[i];
i ++;
for(; i < n && s[i] !='(' ; i ++)
s_non += s[i];
i ++;
for(; i < n && s[i] != ')' ; i ++)
s_rep += s[i];
struct frac frac_int,frac_non,frac_rep,temp1;
frac_int = frac(stoi(s_int),1);
if(s_non == "") frac_non = frac(0,1);
else frac_non = frac(stoi(s_non),pow_of_10[s_non.length()]);
if(s_rep == "") frac_rep = frac(0,1);
else frac_rep = frac(stoi(s_rep),pow_of_10[s_non.length()] * (pow_of_10[s_rep.length()] - 1));
temp1 = add(frac_int,frac_non);
return add(temp1,frac_rep);
}
bool isRationalEqual(string S, string T) {
struct frac fc1 = cal(S),fc2 = cal(T);
return fc1.up == fc2.up && fc1.down == fc2.down;
}
};