澳门至尊网站-首页

您的位置:澳门至尊网站 > 黑客安全 > 两数相除

两数相除

2019-11-21 23:31

近一个月一直在写业务,空闲时间刷刷leetcode,刷题过程中遇到了一道比较有意思的题目,和大家分享。

leetcode笔记:Divide Two Integers

一. 题目描述

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

二. 题目分析

题目的意思简单明了,就是要求不使用乘法、除法和取余mod,输入两个整数,输出除法操作的结果。

出去乘除法,剩下的只有加减法和位运算,这是不难想到的,而直接使用减法,对被除数逐次减去除数大小的值,记录被减次数,肯定是可以得出和除法操作一样的结果,但该方法比较傻瓜,且会超时,时间复杂度为O(n)。

使用位运算可以做到O(logn)的复杂度,但要一步想到具体操作却也不那么简单,首先,我们知道任何一个整数都可以表示成以2的幂为底的一组基的线性组合,即num = flag0 * 2^0 + flag1 * 2^1 + flag2 * 2^2 + ... + flagn * 2^n 其中,flag0, flag1, flag2, ..., flagn 取值为0 & 1

基于以上事实,如果令:dividend / divisor = num,则有:

dividend = divisor * num = divisor * (flag0 * 2^0 + flag1 * 2^1 + flag2 * 2^2 + ... + flagn * 2^n)

对于除数,使用移位操作<<使其每次翻倍,从而减少减法求商的次数。以下是步骤:

当被除数大于除数时,对除数乘2(代码中使用变量step用于记录每次除数乘2),直到step大于被除数为止。记录移位操作的次数i。 如果被除数大于除数,那么被除数减去step。直到被除数小于除数。保存结果。 输出结果result。

注:

byte:128~127 (1Byte)
short :32768~32767 (2Bytes)
int:-2147483648~2147483647 (4Bytes)
long:-9223372036854774808~9223372036854774807 (8Bytes)

三. 示例代码

class Solution {
public:
    int divide(int dividend, int divisor) {
        if (dividend == 0 || divisor == 0) return 0;
        if (dividend == INT_MIN && divisor == -1) return INT_MAX; // 溢出
        bool negative = (dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0);
        long positiveDividend = abs(long(dividend));
        long positiveDivisor = abs(long(divisor));
        long result = 0;

        while (positiveDividend >= positiveDivisor) // 被除数大于除数
        {
            long step = positiveDivisor;
            for (int i = 0; positiveDividend >= step; ++i, step <<= 1)
            {
                positiveDividend = positiveDividend - step;
                result += 1 << i;
            }
        }
        return negative ? -result : result;
    }
};

四. 小结

使用位运算来解决此类问题,是挺容易想到的,但是具体如何操作又是另外一回事。

Two Integers 一. 题目描述 Divide two integers without using multiplication, division and mod operator. If it is overflow, return MAX_INT. 二. 题目分析...

 

题目描述:

给定两个整数,被除数 dividend 和除数 divisor。将两数相除,要求不使用乘法、除法和 mod 运算符。返回被除数 dividend 除以除数 divisor 得到的商。

示例 1:

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

示例 2:

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

说明:

  • 被除数和除数均为 32 位有符号整数。
  • 除数不为 0。
  • 假设我们的环境只能存储 32 位有符号整数,其数值范围是 [−2**31,  2**31 − 1]。本题中,如果除法结果溢出,则返回 2**31 − 1。

 

第一反应是这道题还是挺简单的,用减法实现除法不就好了,python刷题实现甚至可以直接使用range()来实现除法,需要注意的点如下:

1.提前判断结果的正负号

2.结果在[-2**31,2**31-1]中,要判断结果是否移除

3.使用range()来计算除法时,一旦除法可以整除我们要对结果+1,因为len(range(3,7,3))的结果是2,len(range(3,9,3))的结果也是2

 

代码如下:

class Solution(object):
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        below = 1
        if dividend < 0 < divisor or divisor < 0 < dividend:
            below = -1

        dividend,  divisor = abs(dividend),  abs(divisor)
        if dividend < divisor:
            return 0
        elif divisor == 1:
            result = dividend * below
            if result >= 2**31-1:
                return 2**31-1
            return result


        result = len(range(divisor, dividend, divisor))
        if (result+1) * divisor == dividend:
            result += 1 
        return result * below

自己写了好多case来测试都是没问题的,代码提交到leetcode,悲剧了。。。内存错误,看来是内存超了。问题出在核心语句len(range(divisor, dividend, divisor))上,怎么既能保证目前代码的简洁性又能降低内存使用呢。我解决办法是使用xrange代替range,简单的说range返回的对象是个list,会开辟一个很大的空间,而xrange不同,返回的是生成器,所以对内存的使用得到了直接的优化。重新提交,果然通过了。

 

最终代码如下:

class Solution(object):
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        below = 1
        if dividend < 0 < divisor or divisor < 0 < dividend:
            below = -1

        dividend,  divisor = abs(dividend),  abs(divisor)
        if dividend < divisor:
            return 0
        elif divisor == 1:
            result = dividend * below
            if result >= 2**31-1:
                return 2**31-1
            return result


        result = len(xrange(divisor, dividend, divisor))
        if (result+1) * divisor == dividend:
            result += 1 
        return result * below

 

希望对大家有所帮助~

本文由澳门至尊网站发布于黑客安全,转载请注明出处:两数相除

关键词: