Skip to content

Latest commit

 

History

History
179 lines (110 loc) · 4.55 KB

0972._Equal_Rational_Numbers.md

File metadata and controls

179 lines (110 loc) · 4.55 KB

972. Equal Rational Numbers

难度: Hard

刷题内容

原题连接

内容描述

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

解题方案

思路 1 - 时间复杂度: O(len(S) + len(T))- 空间复杂度: O(1)******

float 的有效位数大约是 6 到 7 个十进制数，例如 0.1234567，1234.567 都是有效的。但超出有效位数的浮点数，在赋值给浮点类型时，会四舍五入。 因此 0.999999999999 就成了 1 了。

来自彭东锋

solution来自[C++/Python] Easy Cheat

class Solution:
    def isRationalEqual(self, S, T):
        """
        :type S: str
        :type T: str
        :rtype: bool
        """
        def helper(s):
            i = s.find('(')
            if i >= 0:
                s = s[:i] + s[i + 1:-1] * 20
            return float(s[:20])
        return helper(S) == helper(T)

其实比较人性化是写成这样

class Solution:
    def isRationalEqual(self, S, T):
        """
        :type S: str
        :type T: str
        :rtype: bool
        """
        def helper(s):
            i = s.find('(')
            if i >= 0:
                s = s[:i] + s[i + 1:-1] * 20
            return float(s[:20])
        return abs(helper(S) - helper(T)) < 10 ** (-8)

思路 2 - O(len(S) + len(T))- 空间复杂度: O(1)******

no cheat，完全靠模拟算

参考solution

from fractions import Fraction

class Solution(object):
    def isRationalEqual(self, S, T):
        """
        :type S: str
        :type T: str
        :rtype: bool
        """
        def convert(s):
            idx = s.find('.')
            if idx == -1:
                return Fraction(int(s), 1)
        
            res = Fraction(int(s[:idx]), 1)
            s = s[idx+1:]
            
            idx = s.find('(')
            if idx == -1:
                if len(s) > 0: # 保证int函数的input字符串非空
                    res += Fraction(int(s), 10 ** len(s))
                return res
            if idx > 0:  # 保证int函数的input字符串非空
                res += Fraction(int(s[:idx]), 10 ** idx)
            s = s[idx+1:-1]
            # r = 1 / 10 ** len(s)
            # (1 - r) / r = (1 - 1 / 10 ** len(s)) / (1 / 10 ** len(s))
            # 因为Fraction 里面都要放rational numbers，所以我们化简一下, 得：
            # (1 - r) / r = 10 ** len(s) - 1
            # 记住 repeat 部分前面可能已经还有多余的小数，也要除掉，即 10 ** idx 部分
            res += Fraction(int(s), 10 ** idx * (10 ** len(s) - 1))
            return res
        
        return convert(S) == convert(T)