LCR 001. 两数相除

剑指Offer通关

LCR 001. 两数相除

快速乘

解析：

题目规定只能用32位整数，所以取值范围在-2^31 ~ 2^31 - 1 之间。这里的特殊情况为什么不考虑被除数和除数为最大值？因为后面会将所有的数都转为负数，所以考虑复数的最小值就是在考虑最大值。后面都转为负数了，就和正常的一样了。先考虑所有的特殊情况- 如果被除数为最小值-2^31:- 如果除数为1，则商为最小值-2^31- 如果除数为-1，则商为2^31, 此时溢出，所以应该返回2^31 - 1- 如果除数为最小值-2^31:- 如果被除数为最小值-2^31，那么商为1- 如果被除数为其他值，商为0其余情况，会有除数为正负、被除数为正负四种情况，处理起来比较麻烦。所以考虑将他们全转为正数或负数。这里考虑当有值为-2^31时，转为正数会变成2^31溢出，所以需要全转为负数(实际和全为正数是一样的。)再往后就是正常情况。设被除数为X 除数为Y 且X Y均为负数，商为Z，则满足Y * Z <= X <= Y * (Z + 1)所以可以在0-MAX之间二分Z，得到满足Y * Z <= X 的最大的Z。由于不能用除法，所以二分在找mid时是left + (right - left) >> 1 实现的。而且需要计算Y * Z的值，这里也不能用乘法，所以需要用到快速乘的方法。

class Solution {public int divide(int a, int b) {if(a == Integer.MIN_VALUE){if(b == 1) return Integer.MIN_VALUE;else if(b == -1) return Integer.MAX_VALUE;}if(b == Integer.MIN_VALUE){if(a == Integer.MIN_VALUE) return 1;else return 0;}boolean rev = false;if(a > 0){a = -a;rev = !rev;}if(b > 0){b = -b;rev = !rev;}int l = 1, r = Integer.MAX_VALUE, ans=0;while(l <= r){int mid = l + ((r-l) >> 1);if(quickAdd(b, mid, a)){   //小于等于ans = mid;// 注意溢出if (mid == Integer.MAX_VALUE) {break;}l = mid + 1;}else r = mid-1;// System.out.println("l=" + l + " r=" + r + " mid=" + mid);}return rev ? -ans : ans;    //如果需要取反就取反}// 快速乘public static boolean quickAdd(int y, int z, int x) {// x 和 y 是负数，z 是正数// 需要判断 z * y >= x 是否成立int result = 0, add = y;while (z != 0) {if ((z & 1) != 0) {// 需要保证 result + add >= xif (result < x - add) {return false;}result += add;}if (z != 1) {// 需要保证 add + add >= xif (add < x - add) {return false;}add += add;}// 不能使用除法z >>= 1;}return true;}
}