29. 两数相除
难度:中等
给定两个整数,被除数 dividend
和除数 divisor
。将两数相除,要求不使用乘法、除法和 mod 运算符。
返回被除数 dividend
除以除数 divisor
得到的商。
整数除法的结果应当截去(truncate
)其小数部分,例如:truncate(8.345) = 8
以及 truncate(-2.7335) = -2
示例 1:
输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = truncate(3.33333..) = truncate(3) = 3
示例 2:
输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = truncate(-2.33333..) = -2
提示:
- 被除数和除数均为 32 位有符号整数。
- 除数不为 0。
- 假设我们的环境只能存储 32 位有符号整数,其数值范围是 [−2^31, 2^31 − 1]。本题中,如果除法结果溢出,则返回 2^31 − 1。
解法一:递归法(小学都会用的除法)
首先,我们需要先把几种特殊情况进行处理:
(1)当被除数为0或者除数为1时,直接 return 被除数。
(2)当被除数为Integer.MAX_VALUE时,如果除数为-1,那么得到的结果就会越界。
Integer的范围是 -2147483648~2147483647 ,若出现上述情况,结果为 2147483648,会超出Integer的范围,题目说越界的返回 Integer.MAX_VALUE。
算法思想:
下来我们对我们的算法进行分析,我们是利用一种递归的思想:
如果被除数比除数大,那么结果最小为1,然后我们让除数翻一倍,然后再去比较,如果被除数还是比除数大,那么结果翻一倍;除数再翻一倍,然后再去比较,如果被除数还是比除数大,那么结果再翻一倍。直到 被除数<除数 ,那么就继续递归 ,将被除数=被除数-除数
,
除数= 原先的除数
,然后上一层的递归结果+这一次的递归结果。
其中 被除数<除数是递归的出口。
举个栗子:11 除以 3 。
首先11比3 大,那么结果result最小为1,然后让3翻倍得到6,再去和11比较,11>6,那么结果result翻倍为2;再让6去翻倍得到12,再去和11比较,11<12,这次不满足条件了,说明答案就在2和4之间,本次递归结果为2;那么我们让11-6 = 5,拿着5再和3去计算商。
首先5比3大,那么那么结果result最小为1,然后让3翻倍得到6,再去和5比较,5<6,不满足条件,本次递归结果为1;那么我们让5-3 = 2,拿着2在和3去计算商。
因为2<3,不能再除法了,那么本次递归结果为0;
最后我们只要把每一次递归的结果都加起来就是最终结果了。
那么我们只要将结果的正负先拿出来,直接用被除数和除数的绝对值去进行上述计算,最后再把正负号填上就是最终结果。
算法设计就是这样,但是我们还是会发现,
一些特殊情况依然会出问题:
(1)如果被除数或者除数是Integer.MIN_VALUE
,我们给它取绝对值,就会越界,得到0。
然后就奇思妙想,那么如果我们把被除数和除数都换为负数,就不会出现越界情况了。
(2)还有一些边界的判断,如果我们的被除数为Integer.MIN_VALUE
,那么我们再计算过程中,可能会出现两个很大的负数相加,最后结果越界,会把两个负数之后变成正数,这样就会进入死循环。于是我们需要加入一些边界判断就ok了。
代码:
class Solution {
public int divide(int dividend, int divisor) {
if(dividend == 0 || divisor == 1) {
return dividend;
}
if(divisor == -1) {
if(dividend == Integer.MIN_VALUE) {
return Integer.MAX_VALUE;
}else {
return -dividend;
}
}
int sign = (dividend^divisor)>=0?1:-1;
int a = (dividend<0)?dividend:-dividend;
int b = (divisor<0)?divisor:-divisor;
int result = div(a, b);
return sign>0?result:-result;
}
/**
* 递归计算a/b的值,a和b都是负整数
* @param a 被除数
* @param b 除数
* @return 商
*/
public int div(int a,int b) {
if(a > b) return 0;
int temp = b;
int result = 1;
while(a< temp + temp && (temp + temp < 0)) {
temp = temp + temp;
result = result + result;
}
return result+div(a-temp, b);
}
}
网友评论