关于算法:每日一题相等的有理数

39次阅读

共计 1416 个字符，预计需要花费 4 分钟才能阅读完成。

关键词：数学

题目起源：972. 相等的有理数 – 力扣（Leetcode）

 T 数学

给定两个字符串 s 和 t，每个字符串代表一个非负有理数，只有当它们示意雷同的数字时才返回 true。字符串中能够应用括号来示意有理数的重复部分。

有理数 最多能够用三个局部来示意：整数局部 \<IntegerPart>、小数非重复部分 \<NonRepeatingPart> 和小数重复部分 \<(>\<RepeatingPart><)>。数字能够用以下三种办法之一来示意：

```
<IntegerPart>
```
例：0 ,12 和 123
```
<IntegerPart><.><NonRepeatingPart>
```
例：0.5 , 1. , 2.12 和 123.0001

<IntegerPart><.><NonRepeatingPart><(><RepeatingPart><)>

例：0.1(6)，1.(9)，123.00(1212)

十进制开展的重复部分通常在一对圆括号内示意。例如：

1 / 6 = 0.16666666... = 0.1(6) = 0.1666(6) = 0.166(66)

输出：s = "0.(52)", t = "0.5(25)"
输入：true
解释：因为 "0.(52)" 代表 0.52525252...，而 "0.5(25)" 代表 0.52525252525.....，则这两个字符串示意雷同的数字。

输出：s = "0.1666(6)", t = "0.166(66)"
输入：true

输出：s = "0.9(9)", t = "1."
输入：true
解释："0.9(9)" 代表 0.999999999... 永远反复，等于 1。"1." 示意数字 1，其格局正确：(IntegerPart) = "1" 且 (NonRepeatingPart) = ""。

因为字符串所代表的值不会超过 1e4，故可间接将字符串所示意的值求进去，而后进行比拟。

非重复部分局部容易解决，本题的关键在于如何解决重复部分。以 xxx.yyy(zzz) 为例，剖析如何解决 (zzz) 的理论值。设有 a 个 x，b 个 z，则 (zzz) 的理论值为 0.zzz zzz zzz .../10^a，如何求0.zzz zzz zzz ... 呢？

0.zzz zzz zzz ...= zzz×（10^(-b)+10^(-2b)+…）=zzz/(10^b)（等比数列求和）。

于是，(zzz)的理论值为zzz/10^a/10^b。

对于 C 和 C ++ 而言，xxx.yyy和 zzz 都能够间接应用 sscanf 来读，故只须要确定 a 和 b 即可。

bool isRationalEqual(string s, string t) {
  // 误差限
  const double E = 1e-12;
  // 将非负有理数字符串转换成数值
  auto val = [&](const string &e) {
      double res;
      // 非重复部分的值
      sscanf(e.c_str(), "%lf", &res);
      // 重复部分
      if (e.back() == ')') {
          double r;
          int i = e.size() - 2, p = 1;
          // 找到左括号的地位
          while (e[i] != '(')i--, p *= 10;
          // 重复部分的值
          sscanf(e.c_str() + i + 1, "%lf", &r);
          r = r / (p - 1);
          // 找到小数点的地位
          p = 1;
          while (e[--i] != '.')
              p *= 10;
          res += r /p;
      }
      return res;
  };
  return fabs(val(s) - val(t)) < E;