leetcode面试准备:Divide Two Integers

1 题目

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

If it is overflow, return MAX_INT.

接口: public int divide(int dividend, int divisor)

2 思路

题意

不用乘、除、mod 做一个除法运算。

解

直接用除数去一个一个加，直到被除数被超过的话，会超时。

解决办法：每次将被除数增加1倍，同时将count也增加一倍，如果超过了被除数，那么用被除数减去当前和再继续本操作。

复杂度: O(n)

3 代码

public int divide(int dividend, int divisor) {
// 处理负数
int xor = dividend ^ divisor;
int signal = xor >= 0 ? 1 : -1;
// 正常逻辑
long count = 0;
long num = Math.abs((long) dividend), div = Math.abs((long) divisor);
long tmp = div;
while (num >= tmp) {
long countTmp = 1;
while (num >= tmp) {
tmp = tmp << 1;
countTmp = countTmp << 1;
}
count += countTmp >> 1;
tmp = tmp >> 1;
num = num - tmp;
tmp = div;
}
// 处理溢出的特殊用例{-2147483648, -1}
long res =  count * signal;
return  res > Integer.MAX_VALUE ? Integer.MAX_VALUE : (int)res;
}

4 总结

数学思维，考智商。