Решения 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”