给定两个整数,被除数 dividend 和除数 divisor。将两数相除,要求不使用乘法、除法和 mod 运算符。
返回被除数 dividend 除以除数 divisor 得到的商。示例 1:
输入: dividend = 10, divisor = 3
输出: 3
示例 2:
输入: dividend = 7, divisor = -3
输出: -2
说明:
被除数和除数均为 32 位有符号整数。
除数不为 0。
假设我们的环境只能存储 32 位有符号整数,其数值范围是 [−231, 231 − 1]。本题中,如果除法结果溢出,则返回 231 − 1。
这个题胜率这么低,其实关键还是因为范围界限的判断影响的。只要不越界,其实除法并不难。另外需要注意的还有一点,就是关于时间限制。我之前有一版提交就是超出时间限制导致的问题。这里的优化点在于通过位运算+更加优秀的算法,总之就是减少运算次数
class Solution {
public int divide(int dividend, int divisor) {
if(dividend==0){
return 0;
}
long AbsDividend = Math.abs((long)dividend);
long AbsDivisor = Math.abs((long)divisor);
long ans = 0;
for(int i = 31; i >= 0; i--) {
//比较dividend是否大于divisor的(1<<i)次方,不要将dividend与(divisor<<i)比较,而是用 (dividend>>i)与divisor比较,
//效果一样,但是可以避免因(divisor<<i)操作可能导致的溢出,如果溢出则会可能dividend本身小于divisor,但是溢出导致dividend大于divisor
if((AbsDividend >> i) >= AbsDivisor) {
ans = ans+(1<<i);
AbsDividend = AbsDividend-(AbsDivisor<<i);
}
}
int c = dividend^divisor;
if(c>=0){
if(Math.abs(ans)>=Integer.MAX_VALUE){
return Integer.MAX_VALUE;
}
return (int)ans;
}else{
return -(int)ans;
}
}
}
网友评论