972. Equal Rational Numbers

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.](https://en.wikipedia.org/wiki/0.999...)]
"1." represents the number 1, which is formed correctly: (IntegerPart) = "1" and (NonRepeatingPart) = "".

Note:

  1. Each part consists only of digits.
  2. The <IntegerPart> will not begin with 2 or more zeros.  (There is no other restriction on the digits of each part.)
  3. 1 <= <IntegerPart>.length <= 4
  4. 0 <= <NonRepeatingPart>.length <= 4
  5. 1 <= <RepeatingPart>.length <= 4

这道题让判断两个有理数是否相等,这里的有理数是用字符串表示的,分为三个部分,整数部分,不重复部分,和重复部分,其中重复部分是用括号装起来的,参考题目中的例子不难理解。其实这道题蛮难想的,因为大多数人应该都会思维定势的尝试去比较两个字符串是否相等,但实际上最好的解法是将它们转为 Double 型的,再直接比较是否相等。由于字符串中括号的存在,不能直接转为 Double 型,所以要先找出左括号的位置,然后把前面的整数和不重复的小数部分一起提取出来,然后取出重复部分,重复 20 次再加到前面提取出来的字符串,此时调用内置函数 stod 将字符串转为双精度浮点型,若没有括号,则直接转为 Double,在主函数中比较即可,参见代码如下:

class Solution {
public:
    bool isRationalEqual(string S, string T) {
        return helper(S) == helper(T);
    }
    double helper(string S) {
        auto i = S.find('(');
        if (i != string::npos) {
            string base = S.substr(0, i);
            string rep = S.substr(i + 1, (int)S.length() - i - 2);
            for (int k = 0; k < 20; ++k) base += rep;
            return stod(base);
        }
        return stod(S);
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/972

参考资料:

https://leetcode.com/problems/equal-rational-numbers/

https://leetcode.com/problems/equal-rational-numbers/discuss/214205/Java-Math-explained

https://leetcode.com/problems/equal-rational-numbers/discuss/214203/JavaC%2B%2BPython-Easy-Cheat

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

×

Help us with donation