给定两个整数，被除数 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 位有符号整数，其数值范围是 [−231, 231 − 1]。本题中，如果除法结果溢出，则返回 231 − 1。
今天每一题，先理清思路
首先，除法的本质，从我们小时候刚开始学习除法的时候老师们最直接的说明是这样的：6 ÷ 2 = 3
表示6可以由3个2加起来组成。而这里的3，就是我们这题需要求得的数字。那么最直观的，换一个角度来做的话，我们可以让6来减去2，看能减去多少个，得到的结果也是同样的答案了。
写代码前的一点问题
按照正常思路，肯定是正数操作更顺手，不过我们知道
Integer.MAX_VALUE = 2147483647
Integer.MIN_VALUE = -2147483648
是的，负的值比正的多一个（按照我们一般理解的数字分为[负，零，正]这三个区间来理解的话）
所以我这里选择了都变为负数来处理。如果把-2147483648取绝对值变成正的话就是溢出。至于为什么是这个区间是另外一个话题了
另外一些一些特殊情况：
被除数如果是1的话则直接返回除数本身
除数是Integer.MIN_VALUE，被除数如果是-1的话，是溢出的情况原因就是上面说的
如果被除数是-1的话直接取反返回（这个一开始忘了写）
好了，代码
class Solution {
public int divide(int dividend, int divisor) {
if (divisor==1){
return dividend;
}
if(dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;
boolean flag = true;
if ((dividend > 0 && divisor < 0) ||(dividend < 0 && divisor > 0) ){
flag = false;
}
dividend = dividend > 0 ? -dividend : dividend;
divisor = divisor > 0 ? - divisor : divisor;
int res = 0;
while (dividend <= divisor){
dividend -= divisor;
res++;
}
return flag?res:-res;
}
}
跑一下看看
解答成功:
执行耗时:1146 ms,击败了7.76% 的Java用户
内存消耗:35.3 MB,击败了94.94% 的Java用户嚯，果然，直接硬刚的结果就是这样
再想想
举个栗子，拿100依次减3，这样我们需要减33次，有没有办法加速呢？有的，
- 我们可以第一次尝试减3 = 97 1个3
- 尝试减6 = 91 3个3
- 尝试减12 = 79 7个3
- 尝试减24 = 55 15个3
- 尝试减48 = 7 31个3
- 尝试减96 不够
- 再次尝试从3开始减 = 4 32个3
- 尝试减6 不够
- 再次尝试从3开始减 = 1 33个3
这是这样的思想来加速处理或者说，好像叫倍增？这个我不太确定。不过如果换个角度来看的话，比较像是二分法的逆向运用。
除了和二分法有点相关的之外，还有另外一个方法有点类似，哈希表中用来解决哈希冲突用到的平方探测法：当哈希结果发生冲突的时候以增量序列[1,4,9,16……]循环试探下一个地址，这些值分别是1的平方、2的平方、3的平方、4的平方。
扯得有点多了。回到代码，这样我们在现在的代码中while循环内再加一层尝试的逻辑
以及加亿点点比较一眼就能看出来的结果的分支判断
代码
class Solution {
public int divide(int dividend, int divisor) {
if (divisor==1){
return dividend;
}
if(dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;
if (divisor == Integer.MIN_VALUE){
return dividend> divisor?0:1;
}
if (divisor == -1){
return -dividend;
}
if (divisor == 2){
return dividend>>1;
}
if (divisor == -2){
return -dividend>>1;
}
boolean flag = true;
if ((dividend > 0 && divisor < 0) ||(dividend < 0 && divisor > 0) ){
flag = false;
}
dividend = dividend > 0 ? -dividend : dividend;
divisor = divisor > 0 ? - divisor : divisor;
int res = 0;
while (dividend <= divisor){
int tmpDivisor = divisor;
int tmpCount = 1;
while (dividend <= tmpDivisor && tmpDivisor<=0){
res += tmpCount;
dividend -= tmpDivisor;
tmpCount += tmpCount;
tmpDivisor += tmpDivisor;//会越界,所以上面还加了判负条件，不过可能还有问题
}
}
return flag?res:-res;
}
}
还有一点问题，这里tmpDivisor虽然为负数，再加自己一次的时候还是可能会越界变成小于Integer.MIN_VALUE然后导致变成一个正数。
所以还是加了一个tmpDivisor<=0的判断，不过感觉还是有点问题。 也许应该用 tmpDivisor>=-1073741824来判断？就是Integer.MIN_VALUE/2的值
最后跑下看下结果，看起来海星
执行耗时:1 ms,击败了100.00% 的Java用户
内存消耗:35.3 MB,击败了89.65% 的Java用户
发表评论