PHP | LeetCode

Задача: 166. Fraction to Recurring Decimal Сложность: medium Даны два целых числа, представляющих числитель и знаменатель дроби. Верните дробь в строковом формате. Если дробная часть повторяется, заключите повторяющуюся часть в скобки. Если возможны несколько ответов, верните любой из них. Гарантируется, что длина строки ответа будет меньше 10^4 для всех предоставленных входных данных. Пример:

Input: numerator = 1, denominator = 2
Output: "0.5"

👨‍💻 Алгоритм: 1⃣Использование хеш-таблицы для отслеживания остатков: Создайте хеш-таблицу для хранения соответствия между остатком от деления и его позицией в дробной части. Это поможет определить начало повторяющейся части. Для каждого нового остатка вычислите следующую цифру результата деления и проверьте, был ли такой остаток уже получен ранее. 2⃣Обработка нулевого остатка: Если в процессе деления остаток становится равным нулю, это означает, что дробная часть не повторяется и процесс можно завершать. 3⃣Учет особенностей: Будьте осторожны с крайними случаями, такими как отрицательные дроби или особо сложные случаи, например, деление −1 на −2147483648. В этих случаях следует корректно обрабатывать знаки и возможные переполнения. 😎 Решение:

class Solution {
    function fractionToDecimal($numerator, $denominator) {
        if ($numerator == 0) {
            return "0";
        }

        $fraction = "";
        if (($numerator < 0) xor ($denominator < 0)) {
            $fraction .= "-";
        }

        $dividend = abs($numerator);
        $divisor = abs($denominator);

        $fraction .= intval($dividend / $divisor);
        $remainder = $dividend % $divisor;
        if ($remainder == 0) {
            return $fraction;
        }

        $fraction .= ".";
        $lookup = [];
        while ($remainder != 0) {
            if (isset($lookup[$remainder])) {
                $pos = $lookup[$remainder];
                $fraction = substr($fraction, 0, $pos) . "(" . substr($fraction, $pos) . ")";
                break;
            }
            $lookup[$remainder] = strlen($fraction);
            $remainder *= 10;
            $fraction .= intval($remainder / $divisor);
            $remainder %= $divisor;
        }

        return $fraction;
    }
}

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