LeetCode29-两数相除

题目描述

给定两个整数 dividend - 被除数和 divisor - 除数，在不使用乘法、除法和取余的前提下求两个数的商，商要靠 0 取整。其中：-2^31 < dividend, divisor < 2^31 - 1，且 divisor != 0。

示例：

输入: dividend = 10, divisor = 3
输出: result = 3

输入: dividend = 7, divisor = -3
输出: -2

思路

不使用乘法、除法和取余，那就只能使用加减法了。商的本质就是看被除数中包含多少倍的除数，所以最终只要看多少个除数加起来的和小于且最接近被除数，这个个数就是最终的答案。

思路一
这是我最开始的思路，不停的从 dividend 中减去 divisor 并累加次数，直到 dividend < divisor，此时的累计次数就是结果。不过这种方式效率太低，会超时。

思路二
在思路一的基础上进行改进，改用累加和与 dividend 比较。思路一中每次只增加一倍的 divisor，当被除数很大的时候，操作次数也会非常多。那能不能每次多处理一些呢？比如第一次 1 * divisor，累加 1，第二次 2 * divisor，累加 2，直到 tempSum + n * divisor > dividend，即被除数小于 n 倍的除数的时候，再将被除数与 n 倍的除数之间的差拿出来，按照思路一的方式去算。答案是肯定的，使用这种方式可以通过。

思路三
思路二中每次只增加一倍的 divisor，效率还是有点低，比如当 dividend=100_000_00，divisor=3的时候，依次算 3 + 6 + 9 + 12 + 15 + … + (n * 3) <? dividend，是比思路一要开一些，但是也是非常的慢。那试试引入幂增呢？每一次不是增加一倍的 divisor，而是将当前的累加和直接翻倍，再比较和 dividend 的大小，这时上面的运算变成：3, 6, 12, 24, 48, 96, 192…，速度比思路二要快得多。这种思路叫做“快速乘”。

代码实现

思路二中的累加方式（类快速乘思路，可通过）：

func divide2(dividend int, divisor int) int {
        if divisor == 0 {
                panic("Bad parameter")
        }

        sign := 1
        if dividend >= 0 && divisor < 0 || dividend <= 0 && divisor > 0 {
                sign = -1
        }

        d1 := int(math.Abs(float64(dividend)))
        d2 := int(math.Abs(float64(divisor)))

        sum := 0
        times := 1
        result := 0
        for (sum + times*d2) <= d1 {
                sum += times * d2
                result += times
                times++
        }

        if sum < d1 {
                for sum+d2 <= d1 {
                        sum += d2
                        result++
                }
        }

        result = sign * result
        if result > math.MaxInt32 {
                return math.MaxInt32
        } else if result < math.MinInt32 {
                return math.MinInt32
        } else {
                return result
        }
}

思路三快速乘：

func divide3(dividend int, divisor int) int {
        if divisor == 0 {
                panic("Bad parameter")
        }

        sign := 1
        if dividend >= 0 && divisor < 0 || dividend <= 0 && divisor > 0 {
                sign = -1
        }

        d1 := int(math.Abs(float64(dividend)))
        d2 := int(math.Abs(float64(divisor)))

        result := 0
        for d2 <= d1 {
                tempSum := d2
                multiple := 1
                for 2 * tempSum <= d1 {
                        tempSum *= 2
                        multiple *= 2
                }
                d1 -= tempSum
                result += multiple
        }

        result *= sign
        if result > math.MaxInt32 {
                return math.MaxInt32
        } else if result < math.MinInt32 {
                return math.MinInt32
        } else {
                return result
        }
}