LeetCode 972. Equal Rational Numbers
原题链接
困难
作者:
JasonSun
,
2020-01-23 13:26:13
,
所有人可见
,
阅读 496
Algorithm
- Let $I(x),N(x),R(x)$ denote the integer part, non-repetitive-part, and repetitive-part of a rational number $x$, where $I(x),N(x),R(x)\in\mathbb{Z}\cup\emptyset.$ Then we have $$x=I(x)+\mathbb{I}_{N(x)\neq\emptyset}\cdot10^{-\text{digit}(N(x))}\cdot N(x)+\mathbb{I}_{R(x)\neq\emptyset}\cdot R(x)\cdot\frac{10^{-\text{digit}(R(x))}}{1-10^{-\text{digit}(R(x))}}\cdot10^{-\text{digit}(N(x))},$$ where $\mathbb{I}$ is the indicator function.
- Hence, we need to implement a function
eval
that evaluates the formula above.
Code
class Solution {
public:
bool isRationalEqual(string S, string T) {
struct rational_t {
int integer_part;
optional<string> non_repeating_part;
optional<string> repeating_part;
};
auto parse_rational = [&](string input, int pos = 0) {
auto peek = [&]() -> optional<char> {
if (pos == size(input))
return {};
else
return input[pos];
};
auto read = [&]() -> char {
return input[pos++];
};
auto next_int = [&](int acc = 0) -> int {
while (peek() and isdigit(*peek()))
acc = (10 * acc) + read() - '0';
return acc;
};
auto next_number_as_string = [&](std::string acc = {}) -> string {
while (peek() and isdigit(*peek()))
acc.push_back(read());
return acc;
};
const auto result = [&](rational_t self = {}) {
if (peek() and isdigit(peek().value()))
self.integer_part = next_int();
if (peek() and peek().value() == '.') {
read();
if (peek() and isdigit(peek().value()))
self.non_repeating_part = next_number_as_string();
}
if (peek() and peek().value() == '(') {
read();
self.repeating_part = next_number_as_string();
read();
}
return self;
}();
return result;
};
auto parse_num_string = [&](const string & str) {
int acc = 0;
for (const auto x : str)
acc = (acc * 10) + x - '0';
return acc;
};
auto eval = [&](const rational_t& rational) {
const auto [integer, non_repetitive, repetitive] = rational;
const auto result = [&](double acc = 0.0) {
acc += integer;
const auto n = int{size(non_repetitive.value_or(std::string{}))};
const auto m = int{size(repetitive.value_or(std::string{}))};
const auto factor = pow(10.0, -n);
if (non_repetitive)
acc += double(parse_num_string(non_repetitive.value())) * pow(10.0, -n);
if (repetitive)
acc += factor * double(parse_num_string(repetitive.value())) * pow(10.0, -m) / (1 - pow(10.0, -m));
return acc;
}();
return result;
};
const auto solution = [&] {
const auto n1 = parse_rational(S);
const auto n2 = parse_rational(T);
return std::abs(eval(n1) - eval(n2)) < 1e-8;
}();
return solution;
}
};