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);
}
}
网友评论