剑指Offer|day1 LCR 001. 两数相除

LCR 001. 两数相除

输入：a = 15, b = 2
输出：7
解释：15/2 = truncate(7.5) = 7

法1：转为负数计算

分析：不能使用乘号和除号，只能使用减法。比如计算15/2（15是被除数，2是除数），就是15不停地减2，当减去7个2后余数是1，此时不能减去更多的2，因此15/2的商为7。

这个解法存在一个问题。当被除数很大除数很小，比如$(2^{31}-1)/1$，减1操作需要执行$2^{31}-1$次，需要很长时间。

将上述解法稍作调整。当被除数大于除数的时候，继续比较判断被除数是否大于除数的2倍，如果是，则继续判断被除数是否大于除数的4倍、8倍等。如果被除数最多大于除数的$2^k$倍，那么将被除数减去除数的$2^k$倍，然后将剩余的被除数重复前面的步骤。每次将除数翻倍，因此优化后的时间复杂度为$O(logn)$

看15/2讨论计算过程。15大于2,15也大于4，15大于8，但15小于16。于是先将15-8=7,由于减去的8是除数的4倍，所以这部分的商为4，结果加4；看7/2，7大于2,7大于4,7小于8，所以7-4=3，减去的4是除数的2倍，所以这部分的商为2，结果加2；看3/2，3大于2，3小于4，所以3-2=1，减去的2是除数的1倍，所以这部分的商为1，结果加1；最后的1比除数小，不能再减去除数了，所以结果为4+2+1=7。

上述讨论的是正整数，对于负数可都转为正数，算好之后再调整正负号。例如-15/2，先算15/2得到7，结果再加上符号。

将负数转换成正数存在一个问题，对于32位正数，最小整数$-2^{31}$，最大的整数是$2^{31}-1$。因此最小整数转成正数$2^{31}$会溢出。由于将任意正数转换为负数不会溢出，因此可以先将正数都转换成负数，再计算商，再调整商的正负号。

最后讨论可能的溢出。由于是整数的除法，并且除数不为0，因此商的绝对值一定小于或等于被除数的绝对值。因此，int型整数的除法只有一种情况会导致溢出，即$(-2^{31})/(-1)$。这是因为最大的正数为$2^{31}-1$，$2^{31}$超出了正数的范围。

• 时间复杂度：O(log a)
• 空间复杂度：O(1)

var divide = function(a, b){// 解决溢出问题if(a === -(2**31) && b === -1) return 2**31-1;let negative = 2; // 计数变符号操作次数// 将a和b都变为负数if(a > 0){negative--;a = -a;}if(b > 0){negative--;b = -b;}let result = divideCore(a, b);return negative === 1 ? -result : result; // negative为1的话，就说明只有1个数是正数，所以结果要加负号}function divideCore(a, b) {let result = 0;// 当 a 小于等于 b 时，继续除法运算// (-15)/(-2)while (a <= b) {let value = b;let quotient = 1;// 通过倍增值和商来加速减法运算while (value >= -(2**30) && a <= value + value) {quotient += quotient;value += value;}result += quotient;a -= value;}return result;
}

来看divideCore函数，假设计算divideCore(-15, -2) 。

符合a <= b,value=-2,quotient=1,

​ value没有溢出&a也是符合条件的，quotient=2，value=-4；quotient=4，value=-8；不符合a <= value + value,跳出循环。

​ result=4,a=-15-(-8)=-7；

计算(-7)/(-2)。符合a <= b,value=-2,quotient=1,

​ value没有溢出&a也是符合条件的，quotient=2，value=-4；不符合a <= value + value,跳出循环。

​ result=4+2=6,a=-7-(-4)=-3；

计算(-3)/(-2)。符合a <= b,value=-2,quotient=1,

​ value没有溢出&a也是符合条件的，不符合a <= value + value,跳出循环。

​ result=6+1=7,a=-3-(-2)=-1；此时a=-1，b=-2，a>b跳出循环。

法2：转为正数计算

分析：和法1一样，这里是将所有数转为正数计算。其他基本一致

• 时间复杂度：O(log a)
• 空间复杂度：O(1)

var divide = function(a, b) {// 解决溢出问题if (a === -(2 ** 31) && b === -1) return 2 ** 31 - 1;// 判断符号let sign = (a > 0) ^ (b > 0);  // ^异或：同号0，异号1// 取正值a = a > 0 ? a : -a;b = b > 0 ? b : -b;let result = 0;// 进行除法计算while (a >= b) {let value = b;let k = 1;// 优化：倍增b，直到 value 加倍大于awhile (a >= (value + value)) {value += value;  // b 值加倍k += k;  // k 值也加倍}// 扣除当前的倍数，增加结果a -= value;result += k;}// 返回结果，根据符号判断return sign ? -result : result;
};