LeetCode29 Medium Быстрое деление без знака деления

Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания

Ссылка на сайт

трудность

Medium

описывать

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

Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.

Return the quotient after dividing dividend by divisor.

The integer division should truncate toward zero.

Пример 1:

Input: dividend = 10, divisor = 3
Output: 3

Пример 2:

Input: dividend = 7, divisor = -3
Output: -2

Уведомление:

И делитель, и делимое находятся в диапазоне 32-битного целого числа.
Делитель не 0
Возвраты для случаев выхода за пределы поля $2^{31}-1$

Both dividend and divisor will be 32-bit signed integers.
The divisor will never be 0.
Предположим, мы имеем дело со средой, которая может хранить целые числа только в диапазоне 32-битных целых чисел со знаком: [− $2^{31}$ , $2^{31}$ − 1].Для решения этой задачи предположим, что ваша функция возвращает $2^{31}$ − 1, когда результат деления переполняется.

отвечать

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

Насилие

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

Другой момент, который более настораживает, это ситуация, когда подсказка может выйти за границы, давайте проанализируем ее, на самом деле есть только одна возможность выйти за границы. Это $-2^{31}$ Делим на -1, получаем $2^{31}$ , а максимальный диапазон положительных чисел для 32-битного int равен $2^{31}-1$ , поэтому мы должны обратить внимание на этот вопрос. К счастью, для Python int не имеет области видимости, поэтому вы можете игнорировать эту проблему и судить о результате нужно только в конце, но для таких языков, как C++ и Java, вам нужно судить об этом случае.

Подведем итог описанному выше процессу: сначала мы можем преобразовать делитель и делимое в положительные числа, а затем использовать флаг, чтобы записать, имеют ли они одинаковый знак. После вычисления результата нужно судить, выходит ли диапазон результата за пределы, и если выходит, возвращать $2^{31}-1$ .

код показывает, как показано ниже:

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        # 判断是否同号
        flag = (dividend > 0 and divisor > 0) or (dividend < 0 and divisor < 0)
        ret = 0
        # 全部赋值为正
        dividend, divisor = abs(dividend), abs(divisor)
        
        start = 0
        # 模拟除法
        while start + divisor <= dividend:
            start += divisor
            ret += 1
            
        # 防止越界，注意只有正数才有可能越界
        return min(ret, (1 << 31) - 1) if flag else -ret

Этот код, конечно, не проблема, но если вы действительно отправите его таким образом, время ожидания определенно истечет. Причина тоже очень проста, когда делитель очень маленький, например 1, то количество наших петель и есть размер делимого. Когда мы даем большие дивиденды, тайм-аут очевиден.

бинарная оптимизация

Алгоритм, описанный далее, очень важен и является основой многих быстрых идемпотентных алгоритмов.Поскольку эта задача не является операцией возведения в степень, ее нельзя назвать алгоритмом быстрого возведения в степень, и какое-то время у него нет хорошего названия, потому что она по существу проходит через Бинарные операции оптимизированы, поэтому это называется бинарной оптимизацией.

Прежде чем объяснять алгоритм, давайте проанализируем причины плохого случая. Причина тайм-аута в том, что делимое может быть очень маленьким, например, 1. В настоящее время нам требуется очень много времени, чтобы вычитать по одному. Поэтому естественно подумать, а можем ли мы каждый раз вычитать не одну единицу, а несколько единиц, и, наконец, складывать эти вычитаемые величины, будет ли это быстрее, чем вычитать по одной? Но есть еще детали, которых мы не знаем, как мы определяем сумму, которую следует вычитать каждый раз? Что мне делать, если я обнаружу, что сокращения недостаточно?

Чтобы ответить на поставленный выше вопрос, вам нужно иметь относительно глубокое понимание двоичного кода. Давайте прямо сейчас поставим вопрос и посмотрим на бинарное объяснение деления. Возьмем простой пример, например, 15/3 = 5. Мы знаем, что 15 равно 5 троек, умноженных вместе, поэтому мы пишем их все в двоичном формате. Двоичное число 15 — это 1111, двоичное число 3 — 0011, а двоичное число 5 — 0101. Давайте сосредоточимся на двоичном числе 5.

Двоичный код 5 записывается как 0101, и если его расширить, то он будет 2^2 + 2^0 = 4 + 1 , то есть мы можем рассматривать 15 как (2^2+2^0)*3 , эта формула записывается как (0*2^3+1*2^2+0*2^1+1*2^0)*3=15 . То есть мы можем рассматривать дивиденды как сумму нескольких полномочий 2, умноженных на дивизор, что превращает проблему разделения в проблему с добавлением. Аналогичным образом, мы преобразуем расчету раствора в двоичном выражении циварки раствора. С двоичным выражением, конечный фактор - не что иное, как суммирование и накопление.

Наконец, давайте проанализируем, почему его можно оптимизировать. Поскольку заголовок был ограничен, делитель и делимое находятся в диапазоне 32-битных целых чисел. Другими словами, имеется не более 32 двоичных битов, поэтому количество наших циклов не более 32 раз. Путем бинарной оптимизации ставим исходный O(n) проблема, понизил до $O(\log n)$ , разница между ними более чем на порядок и конечно гораздо быстрее.

Мы можем получить ответ, записав приведенную выше идею в код:

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        # 前面处理和之前一样
        flag = (dividend > 0 and divisor > 0) or (dividend < 0 and divisor < 0)
        ret = 0
        dividend, divisor = abs(dividend), abs(divisor)
        
        # 预处理二进制数组
        binary = [0 for _ in range(33)]
        # 第0位即2的零次方乘上除数，所以就是除数本身
        binary[0] = divisor
        for i in range(1, 33):
            # 后面每一位是前面一位的两倍，因为二进制
            # << 是位运算左移操作，等价于*2，但是速度更快
            binary[i] = binary[i-1] << 1
            
        for i in range(32, -1, -1):
            if binary[i] <= dividend:
                dividend -= binary[i]
                # 答案加上2^i
                ret += (1 << i)
        return min(ret, (1 << 31) - 1) if flag else -ret

Этот код не длинный и не использует никаких специальных алгоритмов, это не что иное, как использование бинарника. Но новичкам, не знакомым с двоичным кодом, может быть немного сложно полностью разобраться, что тоже нормально. Я надеюсь, что все могут успокоиться и хорошо понять это. Если вы действительно этого не понимаете, это не имеет значения. В будущем быстрый идемпотентный алгоритм я встречу его снова.

На сегодняшней статье все, если вы чувствуете, что что-то приобрели, пожалуйста, следуйте ей.Отсканируйте код и обратите вниманиеЧто ж, твое маленькое усилие много значит для меня.