相等的有理数
难度:
标签:
题目描述
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.
A rational number can be represented using up to three parts: <IntegerPart>, <NonRepeatingPart>, and a <RepeatingPart>. The number will be represented in one of the following three ways:
<IntegerPart>- For example,
12,0, and123.
- For example,
<IntegerPart><.><NonRepeatingPart>- For example,
0.5,1.,2.12, and123.0001.
- For example,
<IntegerPart><.><NonRepeatingPart><(><RepeatingPart><)>- For example,
0.1(6),1.(9),123.00(1212).
- For example,
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).
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) = "".
Constraints:
- Each part consists only of digits.
- The
<IntegerPart>does not have leading zeros (except for the zero itself). 1 <= <IntegerPart>.length <= 40 <= <NonRepeatingPart>.length <= 41 <= <RepeatingPart>.length <= 4
代码结果
运行时间: 30 ms, 内存: 16.1 MB
/*
* The problem requires us to compare two strings that represent rational numbers,
* possibly with repeating decimal parts, and determine if they represent the same number.
* The approach involves converting these rational numbers to their decimal representations
* and comparing these representations using Java Stream API.
*/
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class RationalNumberComparisonStream {
public boolean isRationalEqual(String s, String t) {
return convertToDecimal(s).equals(convertToDecimal(t));
}
private String convertToDecimal(String s) {
if (!s.contains("(")) {
return s;
}
String[] parts = s.split("[.()]");
String integerPart = parts[0];
String nonRepeatingPart = parts.length > 1 ? parts[1] : "";
String repeatingPart = parts.length == 3 ? parts[2] : "";
String repeatedSequence = IntStream.range(0, 20)
.mapToObj(i -> repeatingPart)
.collect(Collectors.joining());
return integerPart + "." + nonRepeatingPart + repeatedSequence;
}
}
解释
方法:
题解的思路是将给定的有理数字符串转换为精确的数学表示形式，使用 Python 的分数模块。这种转换处理了整数部分、非重复小数部分和重复小数部分。首先，根据小数点划分整数和小数部分。如果存在括号，则进一步将非重复和重复小数部分区分开来。对于非重复小数部分，直接将其转换为相应的分数。对于重复小数部分，根据无限循环小数的数学性质转换为分数。最后，比较两个数的分数表示是否相等。
时间复杂度:
O(log(max(a, b)))
空间复杂度:
O(1)
代码细节讲解
🦆
在处理有理数字符串时，如何确保转换的准确性，尤其是当小数部分和重复小数部分非常长时？
▷🦆
在解析和转换有理数时，如果有理数的格式不符合预期（例如缺失括号或多余的字符），题解中的方法如何应对这种情况？
▷🦆
为什么在转换重复小数部分时使用的分数公式是 `Fraction(int(r), (10**len(r) - 1) * 10**len(n))`？这个公式背后的数学原理是什么？
▷