重庆八大员证书查询网站,网站建设图片属性设置,中国城乡建设部官方网站,中核集团电子商城剑指Offer通关
力扣搜索LCR即为剑指Offer的所有题目。
LCR 001. 两数相除
快速乘
解析#xff1a;
题目规定只能用32位整数#xff0c;所以取值范围在-2^31 ~ 2^31 - 1 之间。这里的特殊情况为什么不考虑被除数和除数为最大值#xff1f;因为后面会将所有的数都转为负数…剑指Offer通关
力扣搜索LCR即为剑指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, ans0;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;}
}
