Рубрики
Без рубрики

Решение: Разделите два целых числа (вер. 2)

Это является частью серии пояснений решения LeetCode (индекс). Если вам понравилось это решение или Фу … помечены алгоритмами, JavaScript, Java, Python.

Решения LeetCode (161 часть серии)

Это является частью серии объяснений решения LeetCode ( index ). Если вам понравилось это решение или нашел его полезным, Пожалуйста, как этот пост и/или УПОТАТЬ Мое решение пост на форумах LeetCode Отказ

Примечание : Это моя вторая версия решения для этой проблемы. Некоторые сомневались ли или нет побитовые сдвиги, используемые в первой версии Следует подсчитать как умножение/разделение, поэтому это альтернативное решение, использующее преимущества алгебраических качеств логарифмов.

Проблема лецкода № 29 (средний): разделите два целых числа

Описание:

( Перейти к : Идея решения Код : JavaScript | Python |. Java |. C ++

Учитывая два целых числа дивиденды и дивизор Разделите два целых числа без использования умножения, разделения и оператора мода.

Верните комистку после разделения дивиденд по дивизор Отказ

Целочисленное разделение должно усечиться к нулю, что означает терять свою дробную часть. Например, урезать (8.345) и урезать (-2.7335) = -2 .

Примечание:

  • Предположим, мы имеем дело с окружающей средой, которая может хранить только целые числа в рамках 32-битного подписанного целочисленного диапазона: [-2 ^ 31, 2 ^ 31 - 1] Отказ Для этой проблемы, предположим, что ваша функция возвращает 2 ^ 31 - 1 Когда результат разделения переполняется.

Примеры:

Вход:
Выход: 3
Объяснение:
Вход:
Выход: -2
Объяснение:
Вход:
Выход: 0
Вход:
Выход: 1

Ограничения:

  • -2 ^ 31, делитель ^ 31 - 1
  • дивизор

Идея:

( Перейти к : Описание проблемы Код : JavaScript | Python |. Java |. C ++

Для тех, кто считает, что побитовые сдвиги будут слишком близки к умножению/разделению, мы можем вместо этого использовать правила Логарифмы в наше преимущество:

  if:  exp(log(c) = c                   // Logarithmic rule #1
  if:  log(a / b) = log(a) - log(b)     // Logarithmic rule #2

then:  a / b = exp(log(a / b))          // From rule #1
       a / b = exp(log(a) - log(b))     // From rule #2

       (if m and n are > 0)

Поскольку нам придется использовать абсолютные значения A и B , мы должны определить некоторые краевые случаи для решения разницы в более низких и верхних ограничениях, размещенных на 32-битный Целое число (не прибегая к использованию длинного переменного хранения), а также один край, продиктованный инструкциями.

Наконец, мы также должны применить пол () к результату, чтобы обрезать десятичное время, прежде чем мы Вернуть АНС , вспоминая, чтобы приспособиться к признакам ввода.

Реализация:

Питона обрабатывает номера больше, чем 32-битный внутренне, даже для их log () и exp () Функции, поэтому мы можем пропустить все, кроме обязанности по краям.

Код JavaScript:

( Перейти к : Описание проблемы Идея решения

var divide = function(A, B) {
    let ans = 0
    if (B === -2147483648) return A === B
    if (A === -2147483648)
        if (B === 1) return -2147483648
        else if (B === -1) return 2147483647
        else A += Math.abs(B), ans++
    ans += Math.floor(Math.exp(Math.log(Math.abs(A)) - Math.log(Math.abs(B))))
    return A > 0 === B > 0 ? ans : -ans
};

Код Python:

( Перейти к : Описание проблемы Идея решения

class Solution:
    def divide(self, A: int, B: int) -> int:
        if A == 0: return 0
        if A == -2147483648 and B == -1: return 2147483647
        ans = math.floor(math.exp(math.log(abs(A)) - math.log(abs(B))))
        return ans if (A > 0) == (B > 0) else -ans

Java код:

( Перейти к : Описание проблемы Идея решения

class Solution {
    public int divide(int A, int B) {
        int ans = 0;
        if (B == -2147483648) return A == B ? 1 : 0;
        if (A == -2147483648) {
            if (B == 1) return -2147483648;
            if (B == -1) return 2147483647;
            A += Math.abs(B);
            ans++;
        }
        ans += Math.floor(Math.exp(Math.log(Math.abs(A)) - Math.log(Math.abs(B))));
        return A > 0 == B > 0 ? ans : -ans;
    }
}

C ++ код:

( Перейти к : Описание проблемы Идея решения

class Solution {
public:
    int divide(int A, int B) {
        int ans = 0;
        if (B == -2147483648) return A == B;
        if (A == -2147483648)
            if (B == 1) return -2147483648;
            else if (B == -1) return 2147483647;
            else A += abs(B), ans++;
        ans += floor(exp(log(abs(A)) - log(abs(B))));
        return A > 0 == B > 0 ? ans : -ans;
    }
};

Решения LeetCode (161 часть серии)

Оригинал: “https://dev.to/seanpgallivan/solution-divide-two-integers-ver-2-26pp”