29. 两数相除

29. 两数相除

给定两个整数,被除数 dividend 和除数 divisor。将两数相除,要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

示例 1:

输入: dividend = 10, divisor = 3

输出: 3

示例 2:

输入: dividend = 7, divisor = -3

输出: -2

说明:

被除数和除数均为 32 位有符号整数。

除数不为 0。

假设我们的环境只能存储 32 位有符号整数,其数值范围是 [−231,  231 − 1]。本题中,如果除法结果溢出,则返回 231 − 1。

解题思路:

        如果按照常规的 循环减去 除数 divisor 会产生时间溢出, 换个思路每相减一次 除数 divisor 就 加上自己 第二次相减 就变成 - 2*divisor 第三次就变成 - 3*divisor 当最后一次 相减的余数 小于 n*divisor,再开始一个新循环 从 n*divisor ~ 0,查找 相减余数 的 值

代码:

class Solution:

    def divide(self, dividend, divisor):

        """

        :type dividend: int

        :type divisor: int

        :rtype: int

        """

        min = (2**31)

        isActive = True

        if (divisor<0 and dividend>0) or (divisor>0 and dividend<0):

            isActive = False

        dividend = abs(dividend)

        divisor = abs(divisor)

        i = 0

        j = 1

        divisor_j = divisor

        result = dividend

        while result >= divisor_j:

            result = result-divisor_j

            divisor_j += divisor

            i+=j

            j+=1

        while result >= divisor:

            result = result-divisor

            divisor_j += divisor

            i+=1

        if not isActive:

            i = -i

        if i < -min:

            return i-1

        if i > min-1:

            return i-1

        return i


©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容