题目

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

If it is overflow, return MAX_INT.

题意理解

实现除法运算，不能使用乘法，除法，模运算

解题思路

需要注意的：

1。先对异常情况处理，除数是0的，结果大于INT_MAX的。

2。都转化为正数进行处理

这一步需要注意：转化后有可能结果大于INT_MAX，比如被除数是INT_MIN的。那么可以把转化后的结果声明为long long等，第二个办法就是先做一步把被除数减去除数的运算，排除异常的影响。

3。转化后，可以逐渐递减，直到小于0，然后计数递减次数来当做结果。这个方法复杂度过高。

另一个方法类似于位运算，每次减去的数都加倍，直到大于被除数，然后再从1开始翻倍递减，中间计数时需要注意累加和翻倍。

Code

第一个超时，第二第三都能AC

class Solution1 {
   //不用乘除，模运算，求解除法public:    int divide(int dividend, int divisor) {        if(divisor==0) return INT_MAX;        if(dividend==0) return 0;        bool sign=1;        int count=0;//用于计数        if(dividend<0&&divisor>0||dividend>0&&divisor<0)            sign=0;         //(下面的处理忘了处理最小值转化为最大值时会溢出的情况：-2147483648         if(dividend==INT_MIN||divisor==INT_MIN)         {             if(dividend==INT_MIN&&divisor==INT_MIN) return 1;             if(divisor==INT_MIN) return 0;             //被除数是最小值，除数不是             if(divisor<0)             {                 dividend=dividend-divisor;//降低dividend（由于都是整数，降低之后肯定不溢出）                 count++;             }             else if(divisor>0)             {                dividend=dividend+divisor;//降低dividend（由于都是整数，降低之后肯定不溢出）                count++;              }         }        if(dividend<0) dividend=-dividend;        if(divisor<0) divisor=-divisor;//都转化为正的来处理        while(dividend>=divisor)        {            dividend=dividend-divisor;            count++;            if(count==INT_MAX) return INT_MAX;//(这种情况是-2147483648 -1，理应得到2147483648，但是超出范围了，应为2147483647)        }        if(sign) return count;        else return -count;    }};//这个解法太慢了！！！//采用二分法思想class Solution2 {
   //不用乘除，模运算，求解除法public:    int divide(int dividend, int divisor) {        if(divisor==0) return INT_MAX;        if(dividend==0) return 0;        bool sign=1;        unsigned int count=0;//用于计数        int Sum=0;        if(dividend<0&&divisor>0||dividend>0&&divisor<0)            sign=0;         //(下面的处理忘了处理最小值转化为最大值时会溢出的情况：-2147483648         if(dividend==INT_MIN||divisor==INT_MIN)         {             if(dividend==INT_MIN&&divisor==INT_MIN) return 1;             if(divisor==INT_MIN) return 0;             //被除数是最小值，除数不是             if(divisor<0)             {                 dividend=dividend-divisor;//降低dividend（由于都是整数，降低之后肯定不溢出）                 count++;             }             else if(divisor>0)             {                dividend=dividend+divisor;//降低dividend（由于都是整数，降低之后肯定不溢出）                count++;              }         }        if(dividend<0) dividend=-dividend;        if(divisor<0) divisor=-divisor;//都转化为正的来处理        unsigned int count_last=Caldeivide(dividend,divisor);        if(count_last+count>INT_MAX&&sign)//同号的，最后结果是大于INT_MAX的需要进行异常处理             count=INT_MAX;//异常处理        else //异号的，需要对结果是-2147483648的进行异常处理，但是前面声明的变量是unsigned int，所以不需要再处理了            count=count_last+count;        if(sign) return count;        else return -count;    }private:    int Caldeivide(int dividend,int divisor)//都是正的，无溢出的情况处理    {        int count=0;        while(dividend>=divisor)        {            int count_1=1;            int Sum=divisor;            while(dividend>=Sum)            {                dividend=dividend-Sum;                count=count_1+count;                unsigned int sum1=Sum+Sum;                if(sum1<=dividend && sum1<=INT_MAX)                {                    count_1=count_1+count_1;                    Sum=sum1;//每次2倍速率增加                }                else                    break;            }        }       return count;     }};class Solution {
   //不用乘除，模运算，求解除法public:    int divide(int dividend, int divisor) {        if(!divisor||(dividend==INT_MIN&&divisor==-1)) return INT_MAX;//两种异常        int sign=((dividend<0)^(divisor<0))?-1:1;        int res=0;        int long dvd=labs(dividend);        int long dvs=labs(divisor);        while(dvd>=dvs)        {            long long temp=dvs,multiple=1;            while(dvd>=(temp<<1))            {                temp=temp<<1;                multiple<<=1;            }             dvd-=temp;             res+=multiple;        }      return sign==1?res:-res;        return 0;    }};

转载地址：http://nexvi.baihongyu.com/

你可能感兴趣的文章