Leetcode 29.两数相除 By Python

2021-06-17 16:04

阅读：703

标签：要求 etc type self lin line lse object 简洁

给定两个整数，被除数 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就好了，这样的时间复杂度是$O(dividend)$，遗憾的是这样是过不了的。所以要另辟蹊径，用位运算。

$dividend = quotient*divisor + remainder$

解法：

枚举$i$（降序）找到使得$divisor $能够比$

dividend$小的，规定一个暂时变量tmp，更新tmp

不断更新$tmp + (divisor 比\(dividend$小的位置$i$，并记录下来

代码

class Solution(object):
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        if dividend == 0: return 0
        if divisor == 0: return

        sign = -1 if ((dividend  2 ** 31 - 1:
            return 2 ** 31 - 1
        else:
            return quotient

Leetcode 29.两数相除 By Python

标签：要求 etc type self lin line lse object 简洁

原文地址：https://www.cnblogs.com/MartinLwx/p/9721010.html

上一篇：小学生绞尽脑汁也学不会的python(面对对象-----类与类之间的关系)

下一篇：Java，IntelliJ idea 环境配置，Hello World

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：Leetcode 29.两数相除 By Python
文章链接：http://soscw.com/essay/95108.html

亲，登录后才可以留言！

Leetcode 29.两数相除 By Python

评论

热门文章

推荐文章

最新文章

置顶文章