166. Fraction to Recurring Decimal

LeetCode medium оригинал: C# #csharp #hash-table #leetcode #math #medium #string

LeetCode Static

Даны два целых числа, представляющих числитель и знаменатель дроби. Верните дробь в строковом формате.

Если дробная часть повторяется, заключите повторяющуюся часть в скобки.

Если возможны несколько ответов, верните любой из них.

Гарантируется, что длина строки ответа будет меньше 10^4 для всех предоставленных входных данных.

Пример:

Input: numerator = 1, denominator = 2

Output: "0.5"

C# решение

сопоставлено/оригинал

public class Solution {
    public string FractionToDecimal(int numerator, int denominator) {
        if (numerator == 0) {
            return "0";
        }
        StringBuilder fraction = new StringBuilder();
        if (numerator < 0 ^ denominator < 0) {
            fraction.Append("-");
        }
        long dividend = Math.Abs((long)numerator);
        long divisor = Math.Abs((long)denominator);
        fraction.Append(dividend / divisor);
        long remainder = dividend % divisor;
        if (remainder == 0) {
            return fraction.ToString();
        }
        fraction.Append(".");
        Dictionary<long, int> map = new Dictionary<long, int>();
        while (remainder != 0) {
            if (map.ContainsKey(remainder)) {
                fraction.Insert(map[remainder], "(");
                fraction.Append(")");
                break;
            }
            map[remainder] = fraction.Length;
            remainder *= 10;
            fraction.Append(remainder / divisor);
            remainder %= divisor;
        }
        return fraction.ToString();
    }
}

C++ решение

auto-draft, проверить перед отправкой

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public string FractionToDecimal(int numerator, int denominator) {
        if (numerator == 0) {
            return "0";
        }
        StringBuilder fraction = new StringBuilder();
        if (numerator < 0 ^ denominator < 0) {
            fraction.Append("-");
        }
        long dividend = abs((long)numerator);
        long divisor = abs((long)denominator);
        fraction.Append(dividend / divisor);
        long remainder = dividend % divisor;
        if (remainder == 0) {
            return fraction.ToString();
        }
        fraction.Append(".");
        unordered_map<long, int> map = new unordered_map<long, int>();
        while (remainder != 0) {
            if (map.count(remainder)) {
                fraction.Insert(map[remainder], "(");
                fraction.Append(")");
                break;
            }
            map[remainder] = fraction.size();
            remainder *= 10;
            fraction.Append(remainder / divisor);
            remainder %= divisor;
        }
        return fraction.ToString();
    }
}

Java решение

сопоставлено/оригинал

class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0) {
            return "0";
        }
        StringBuilder fraction = new StringBuilder();
       
        if ((numerator < 0) ^ (denominator < 0)) {
            fraction.append("-");
        }
       
        long dividend = Math.abs(Long.valueOf(numerator));
        long divisor = Math.abs(Long.valueOf(denominator));
        fraction.append(String.valueOf(dividend / divisor));
        long remainder = dividend % divisor;
        if (remainder == 0) {
            return fraction.toString();
        }
        fraction.append(".");
        Map<Long, Integer> map = new HashMap<>();
        while (remainder != 0) {
            if (map.containsKey(remainder)) {
                fraction.insert(map.get(remainder), "(");
                fraction.append(")");
                break;
            }
            map.put(remainder, fraction.length());
            remainder *= 10;
            fraction.append(String.valueOf(remainder / divisor));
            remainder %= divisor;
        }
        return fraction.toString();
    }
}

JavaScript решение

сопоставлено/оригинал

var fractionToDecimal = function (numerator, denominator) {
    if (numerator === 0) {
        return "0";
    }
    var fraction = [];
    if ((numerator < 0) ^ (denominator < 0)) {
        fraction.push("-");
    }
   
    var dividend = Math.abs(numerator);
    var divisor = Math.abs(denominator);
    fraction.push(Math.floor(dividend / divisor).toString());
    var remainder = dividend % divisor;
    if (remainder === 0) {
        return fraction.join("");
    }
    fraction.push(".");
    var map = {};
    while (remainder !== 0) {
        if (remainder in map) {
            fraction.splice(map[remainder], 0, "(");
            fraction.push(")");
            break;
        }
        map[remainder] = fraction.length;
        remainder *= 10;
        fraction.push(Math.floor(remainder / divisor).toString());
        remainder %= divisor;
    }
    return fraction.join("");
};

Python решение

сопоставлено/оригинал

class Solution:
    def fractionToDecimal(self, numerator: int, denominator: int) -> str:
        if numerator == 0:
            return "0"

        fraction = []
        if (numerator < 0) != (denominator < 0):
            fraction.append("-")

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

        fraction.append(str(dividend // divisor))
        remainder = dividend % divisor
        if remainder == 0:
            return "".join(fraction)

        fraction.append(".")
        lookup = {}
        while remainder != 0:
            if remainder in lookup:
                fraction.insert(lookup[remainder], "(")
                fraction.append(")")
                break

            lookup[remainder] = len(fraction)
            remainder *= 10
            fraction.append(str(remainder // divisor))
            remainder %= divisor

        return "".join(fraction)

Go решение

сопоставлено/оригинал

func fractionToDecimal(numerator int, denominator int) string {
    if numerator == 0 {
        return "0"
    }
    var fraction []string
    if (numerator < 0) != (denominator < 0) {
        fraction = append(fraction, "-")
    }
    dividend := absInt(numerator)
    divisor := absInt(denominator)
    fraction = append(fraction, strconv.Itoa(dividend/divisor))
    remainder := dividend % divisor
    if remainder == 0 {
        return strings.Join(fraction, "")
    }
    fraction = append(fraction, ".")
    valMap := make(map[int]int)
    for remainder != 0 {
        if pos, ok := valMap[remainder]; ok {
            fraction = append(
                fraction[:pos],
                append([]string{"("}, append(fraction[pos:], ")")...)...)
            break
        }
        valMap[remainder] = len(fraction)
        remainder *= 10
        fraction = append(fraction, strconv.Itoa(remainder/divisor))
        remainder %= divisor
    }
    return strings.Join(fraction, "")
}

func absInt(val int) int {
    if val < 0 {
        return -val
    }
    return val
}

Algorithm

1️⃣

Использование хеш-таблицы для отслеживания остатков:

Создайте хеш-таблицу для хранения соответствия между остатком от деления и его позицией в дробной части. Это поможет определить начало повторяющейся части.

Для каждого нового остатка вычислите следующую цифру результата деления и проверьте, был ли такой остаток уже получен ранее.

2️⃣

Обработка нулевого остатка:

Если в процессе деления остаток становится равным нулю, это означает, что дробная часть не повторяется и процесс можно завершать.

3️⃣

Учет особенностей:

Будьте осторожны с крайними случаями, такими как отрицательные дроби или особо сложные случаи, например, деление −1 на −

. В этих случаях следует корректно обрабатывать знаки и возможные переполнения.

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.