Задача: 972. Equal Rational Numbers
Сложность: 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 {
    function isRationalEqual($S, $T) {
        $f1 = $this->convert($S);
        $f2 = $this->convert($T);
        return $f1->n == $f2->n && $f1->d == $f2->d;
    }

    function convert($S) {
        $state = 0;
        $ans = new Fraction(0, 1);
        $decimal_size = 0;

        $parts = preg_split('/[.()]/', $S);

        foreach ($parts as $part) {
            $state++;
            if ($part === "") continue;
            $x = intval($part);
            $sz = strlen($part);

            if ($state == 1) {
                $ans->iadd(new Fraction($x, 1));
            } elseif ($state == 2) {
                $ans->iadd(new Fraction($x, pow(10, $sz)));
                $decimal_size = $sz;
            } else {
                $denom = pow(10, $decimal_size);
                $denom *= pow(10, $sz) - 1;
                $ans->iadd(new Fraction($x, $denom));
            }
        }
        return $ans;
    }
}

class Fraction {
    public $n, $d;

    function __construct($n, $d) {
        $g = $this->gcd($n, $d);
        $this->n = $n / $g;
        $this->d = $d / $g;
    }

    function iadd($other) {
        $numerator = $this->n * $other->d + $this->d * $other->n;
        $denominator = $this->d * $other->d;
        $g = $this->gcd($numerator, $denominator);
        $this->n = $numerator / $g;
        $this->d = $denominator / $g;
    }

    function gcd($x, $y) {
        return $x != 0 ? $this->gcd($y % $x, $x) : $y;
    }
}

Ставь 👍 и забирай 📚 Базу знаний