当前访客身份:游客 [ 登录  | 注册加入尚学堂]
直播

flamen

拥有积分:3
这家伙太懒,还没有签名!

博客分类

笔记中心

课题中心

提问中心

答题中心

解答题中心

LeetCode Divide Two Integers

flamen 发表于 1年前 (2015-12-29 11:00:41)  |  评论(0)  |  阅读次数(435)| 0 人收藏此文章,   我要收藏   

LeetCode解题之Divide Two Integers


原题

实现两个int型数字的除法,不可以使用乘法、除法和模操作。

注意点:

  • 如果结果溢出int类型,返回MAX_INT
  • 注意负数情况

例子:

输入: dividend = 5, divisor = -1
输出: -5

解题思路

可以先把符号抽取出来,只考虑两个正数相除的情况。除法其实就是被减数不断减去减数的操作,但直接不断进行减法会超时,应尽量减去大的数字,通过位移操作来快速找到比被减数小一些的减数的倍数current。不断减去且缩小current。溢出只可能是向上溢出,通过min操作进行过滤。

AC源码

class Solution(object):
    def divide(self, dividend, divisor):
        """ :type dividend: int :type divisor: int :rtype: int """
        MAX_INT = 2147483647
        sign = 1
        if dividend >= 0 and divisor < 0 or dividend <= 0 and divisor > 0:
            sign = -1
        dividend = abs(dividend)
        divisor = abs(divisor)

        result = 0
        current = divisor
        currentResult = 1
        while current <= dividend:
            current <<= 1
            currentResult <<= 1
        while divisor <= dividend:
            current >>= 1
            currentResult >>= 1
            if current <= dividend:
                dividend -= current
                result += currentResult
        return min(sign * result, MAX_INT)


if __name__ == "__main__":
    assert Solution().divide(5, -1) == -5
    assert Solution().divide(10, 2) == 5

欢迎查看我的Github来获得相关源码。

分享到:0
关注微信,跟着我们扩展技术视野。每天推送IT新技术文章,每周聚焦一门新技术。微信二维码如下:
微信公众账号:尚学堂(微信号:bjsxt-java)
声明:博客文章版权属于原创作者,受法律保护。如果侵犯了您的权利,请联系管理员,我们将及时删除!
(邮箱:webmaster#sxt.cn(#换为@))
北京总部地址:北京市海淀区西三旗桥东建材城西路85号神州科技园B座三层尚学堂 咨询电话:400-009-1906 010-56233821
Copyright 2007-2015 北京尚学堂科技有限公司 京ICP备13018289号-1 京公网安备11010802015183