Сложность: hard
Даны две строки s и t, каждая из которых представляет собой неотрицательное рациональное число. Вернуть true тогда и только тогда, когда они представляют одно и то же число. Строки могут использовать скобки для обозначения повторяющейся части рационального числа.
Рациональное число может быть представлено с использованием до трех частей: <ЦелаяЧасть>, <НеповторяющаясяЧасть> и <ПовторяющаясяЧасть>. Число будет представлено одним из следующих трех способов:
<ЦелаяЧасть>
Например, 12, 0 и 123.
<ЦелаяЧасть><.><НеповторяющаясяЧасть>
Например, 0.5, 1., 2.12 и 123.0001.
<ЦелаяЧасть><.><НеповторяющаясяЧасть><(><ПовторяющаясяЧасть><)>
Например, 0.1(6), 1.(9), 123.00(1212).
Повторяющаяся часть десятичного разложения обозначается в круглых скобках. Например:
1/6 = 0.16666666... = 0.1(6) = 0.1666(6) = 0.166(66).
Пример:
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.
👨💻 Алгоритм:
1⃣Преобразование дроби. Определите и изолируйте повторяющуюся часть дроби. Преобразуйте строку, представляющую число, в выражение вида S=x/(10^k-1), где x — повторяющаяся часть, а k — её длина.
2⃣Вычисление геометрической суммы. Преобразуйте повторяющуюся часть в сумму вида S=x*(r/(1-r)), где r = 10^(-k). Найдите значение дроби для повторяющейся части, используя формулу геометрической прогрессии.
3⃣Обработка неповторяющейся части. Определите значение неповторяющейся части дроби как обычное число. Объедините результаты для повторяющейся и неповторяющейся частей для получения итогового значения.
😎 Решение:
class Solution {
func isRationalEqual(_ S: String, _ T: String) -> Bool {
let f1 = convert(S)
let f2 = convert(T)
return f1.n == f2.n && f1.d == f2.d
}
func convert(_ S: String) -> Fraction {
var state = 0
var ans = Fraction(0, 1)
var decimal_size = 0
for part in S.split(whereSeparator: { ".()".contains($0) }) {
state += 1
if part.isEmpty { continue }
let x = Int64(part) ?? 0
let sz = part.count
if state == 1 {
ans.iadd(Fraction(x, 1))
} else if state == 2 {
ans.iadd(Fraction(x, Int64(pow(10.0, Double(sz)))))
decimal_size = sz
} else {
var denom = Int64(pow(10.0, Double(decimal_size)))
denom *= Int64(pow(10.0, Double(sz))) - 1
ans.iadd(Fraction(x, denom))
}
}
return ans
}
}
class Fraction {
var n: Int64
var d: Int64
init(_ n: Int64, _ d: Int64) {
let g = Fraction.gcd(n, d)
self.n = n / g
self.d = d / g
}
func iadd(_ other: Fraction) {
let numerator = self.n * other.d + self.d * other.n
let denominator = self.d * other.d
let g = Fraction.gcd(numerator, denominator)
self.n = numerator / g
self.d = denominator / g
}
static func gcd(_ x: Int64, _ y: Int64) -> Int64 {
return x != 0 ? gcd(y % x, x) : y
}
}Ставь 👍 и забирай 📚 Базу знаний