即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

leetcode 29. Divide Two Integers

编程语言 luming_xml 17℃ 0评论

题目:

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

If it is overflow, return MAX_INT.

public class Solution {
   public int divide(int dividend, int divisor) {  
        int sign = 1;  
        if(dividend<0) sign = -sign;  
        if(divisor<0) sign = -sign;  
        long temp = Math.abs((long)dividend);  
        long temp2 = Math.abs((long)divisor);  
        long c = 1;  
        while(temp>temp2){  
            temp2 = temp2<<1;  
            c = c<<1;  
        }  
        long res = 0;  
        while(temp>=Math.abs((long)divisor)){  
            while(temp>=temp2){  
                temp-=temp2;  
                res+=c;  
            }  
            temp2 = temp2>>1;  
            c=c>>1;  
        }  
        if(sign>0) 
           { if(res>Integer.MAX_VALUE)
                return Integer.MAX_VALUE;
             else return (int)res;
           }
        else return (int)-res;  

    }  
}

思路是:

     30/5=5*2*2/5 + 5*2/5

    26/5=5*2*2/5+5*1/5

      

回想除法的最朴素思想:

即,当   被除数>除数  一直拿被除数减去除数,能减去除数的次数为两数相除的结果。

根据这个思想,我们很容易写出伪代码:

while(被除数>除数)

被除数  -=  除数

res ++

最终的res为我们所要的结果。

但是,我们考虑最坏情况:当被除数是Integer.MAX_VALUE,除数是1,那么刚刚的代码就要做(2^31-1)次,即2147483647次减法,结果是超时.







那么有一个做法就是通过左移操作减少减法的次数,但事实上循环的次数并没有减少。

左移操作一次相当于乘以2,那么左移N次就相当于乘以2^N。

在这道题上,我们每次减去2^(N) * 除数,再将上述res每次加上 1<<2^N次方,就能大大缩减做减法的次数。

左移操作也解决了题目要求不能使用乘法的限制。

这个N就可以通过内循环左移比较来判断。



转载请注明:CodingBlog » leetcode 29. Divide Two Integers

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情