LeetCode--29.两数相除

解题思路：

1.获取信息：

给定两个整数，一个除数，一个被除数，要求返回商（商取整数）

限制条件：（1）不能使用乘法，除法和取余运算

（2）只能存储32位有符号整数

额外条件：（1）除数不等于0

（2）INT_MIN<=除数，被除数<=INT_MAX

2.分析题目：

（1）不能使用乘法，除法和取余运算

我们可以使用加法，减法，那么就可以想到快速乘算法

快速乘算法，就是使用加法来模拟乘法的哦，其中会用到右移运算符和quan'zh哦

（为了方便你理解我下面的各种方法，我打算一反常态，直接在这个环节讲解一下快速乘法是什么，还会配图哦，实在是很贴心，但我只会说一下基本原理，你可以思考一下该怎么和这道题结合起来）

（2）只能存储32为有符号整数，并且INT_MIN<=除数，被除数<=INT_MAX

所以我们要考虑一下溢出的问题了，那么我们想一下一个除法，该怎么丧心病狂地溢出呢？

你想一下，我们是求商对吧，在本题的条件下，一个除法的商是不会大于它的被除数的吧，因为都为整数嘛，那么我们可以知道，商一般不会溢出

那么造成溢出的情况就只有一些特殊的情况了，如下两种溢出

（1）原则上溢出：被除数等于INT_MIN，而除数等于-1，两者相除会大于INT_MAX，所以会溢出

（2）运算过程中溢出：因为使用了快速乘的算法，我们在加的过程中可能会造成溢出，（这个溢出也与我所用方法有关，因为我是使用二分查找法来查找一个合适的数来检验是否可以作为商，难免有时候会溢出）

这个时候就需要对溢出进行检验，及时止损，我用了以下两步来避免溢出

（1）第一步：我们知道INT_MAX<INT_MIN对吧，那么我们就将除数和被除数全部变为负数，用一个bool类型的变量来决定结果商的正负，那么就不容易溢出

如果你有疑惑，难道变成正数不行吗？其实也行，但是麻烦，在遇到，如：

被除数等于INT_MIN，除数大于1的情况，变成正数，肯定会溢出，而且进行处理也特别麻烦

（所以，我们在思考的时候，不要给自己增加太多的麻烦，你要做的是简化问题，而不是让这个问题变得更加麻烦，给自己脑袋增加负担哦）

（2）第二步：

我们知道在快速乘中会使用加法来模拟乘法，所以可以在加的过程中判断一下溢出

（我在这里想不到说什么可以讲得明白，我也不想长篇大论地来浪费你的精力，所以我会在下面的方法中结合代码来帮助你理解我会怎么避免溢出，可以期待一下，你现在也可以自己想一下，再到下面对答案哦）

3.示例查验：

示例1和示例2：都没啥太大帮助，也没有提示你什么（我其他题的这个环节是很精彩的，主要是这道题给我衬托得太没用了）

4.尝试编写代码：

（这道题你可能看过很多的题解了，你可能是百思不得其解的状态，所以我还是打算换一种方式来帮助你理解，我会用我初次看到这道题一直到我写出其他方法的过程来帮助你层层递进哦，可以期待一下，好了，下面就开始了，你要跟上咯）

（1）暴力法（这是我第一次写的办法，最后的结果是超时了，被打败了）

思路：除法的本质就是减法，乘法的本质就是加法

所以我们可以用除数一直去减被除数直到被除数小于0或者用除数一直相加直到等于被除数，最后得到的，进行减法的次数或者进行加法的次数就是商了

下面就是代码的实现，（但是我这个方法并没有通过，只是不想你思维跨度那么大，让你摸不着头脑而已，如果你也是这种方法没过，哈哈，那我们蛮有缘的嘛）

class Solution {
public:int divide(int dividend, int divisor) {if(dividend==0)return 0;//如果被除数为0，直接返回0if(dividend==INT_MIN){//如果被除数为INT_MINif(divisor==1)return INT_MIN;if(divisor==-1)return INT_MAX;}if(divisor==1)return dividend;//如果除数为1，返回被除数if(divisor==-1)return -dividend;//如果除数为1，返回被除数的相反数bool front=false;//分别记录除数和被除数的符号bool tail=false;if(dividend>0){front=true;dividend=-dividend;};//将被除数和除数全部变为负数if(divisor>0){tail=true;divisor=-divisor;}if(dividend>divisor)return 0;//（这里它们都是负数了，所以表示大小的关系不一样咯，别搞错了）如果被除数大于除数，就返回0int res=divisor;//相加的结果int num=1;//相加的次数if(dividend!=INT_MIN){//如果被除数不等于INT_MINwhile(res!=dividend-1&&res!=dividend+1&&res!=dividend){//一直相加步直到满足条件，退出循环res+=divisor;num++;}}else{//如果被除数等于INT_MINwhile(res!=dividend+1&&res!=dividend){//一直相加直到不满足条件，退出循环if(dividend-divisor>res)return front==tail?num:-num;res+=divisor;num++;}}return (front==tail)?num:-num;//返回商}
};

（2）二分查找法+快速乘（全部迭代法）

优化思路：我上面的暴力法超时了，我就在想有没有什么办法可以进行优化

主要的问题是，加法进行的次数太多了，而且进行加法的方式的效率也太低了

所以我就使用了二分查找法和快速乘的法方法来进行书写

思路：我们知道，在本题的条件下，商肯定是不会大于被除数的，那么我们就在1到被除数的大小这个范围使用二分法来查找商即可

我们用二分法查找到一个数来作为商，那我们需要对其进行检验吧？

我们就使用快速乘求出商（待检验的那个数）乘除数的结果来对其进行检验，无非就三种情况

（1）结果等于被除数，直接返回那个数（要考虑一下正负哦）即可

（2）结果小于被除数，说明那个数取小了，就需要在右边的区间取数

（3）结果大于被除数，说明那个数取大了，就需要在左边的区间取数

接下来说重头戏，快速乘怎么样在这道题里面实现

快速乘，我们写一个自定义函数，传入商（二分法选取的那个数）和除数，返回它们的乘积

要考虑商的二进制，因为要用到右移运算符>>嘛，那么我们就需要考虑各个位数上的权重，将正确的权重加到结果上去，再让商每次右移一位，直到商为0

（我知道，你肯定看不懂我说的啥意思，即使你看懂了我上面快速乘算法的基本原理，所以，你可以结合我下面的代码好好理解一下，我每行都会给出注释）

class Solution {
public:int divide(int dividend, int divisor) {if(dividend==0)return 0;//被除数如果为0，返回0if(dividend==INT_MIN){//如果被除数等于INT_MINif(divisor==-1)return INT_MAX;if(divisor==1)return INT_MIN;}bool sign=false;//一个bool类型的变量用来表示符号if(dividend>0){dividend=-dividend;sign=!sign;};//将除数和被除数全部变为负数if(divisor>0){divisor=-divisor;sign=!sign;};if(dividend>divisor)return 0;//（这里被除数和除数已经全部为负数了，所以比较关系不一样了）如果被除数大于除数，返回0int res=0;//用来储存商int begin=1;//二分查找法范围的下限int end;if(dividend==INT_MIN)end=INT_MAX;//二分查找法范围的上限else {end=-dividend;}while(begin<=end){//循环继续条件int mid=begin+((end>>2)-(begin>>2));//求出中值if(quick(mid,divisor,dividend)){//quick用来判断乘积大小，如果小于res=mid;if(mid==INT_MAX)return sign?-mid:mid;begin=mid+1;}else{//如果大于end=mid-1;}}return sign?-res:res;}
private:bool quick(int mid,int divisor,int dividend){//此时除数和被除数都为负数，所以比较条件，你要好好注意一下int res=0,add=divisor;//add是指权重哦while(mid){if(mid&1){//如果二进制的最后一位为1，那么就可以将这一位加到res中了，因为下一步就是右移一位，舍弃掉这个1if(res<dividend-add)return false;res+=add;}if(mid!=1){//这是在更新权重，配合着上面那个if语句进行正确的加法，比如，末尾一位是二的零次方，倒数第二位是二的一次方，依次类推if(add<dividend-add)return false;add+=add;}mid>>=1;}return true;}
};

（3）二分查找法+快速乘（全部迭代版）

就是把上面那个方法中用到递归的地方换成了迭代而已，根本思路没变，只是手法变了，我就不写思路咯

也不写注释了，考验一下你，哈哈

class Solution {
public:int divide(int dividend, int divisor) {if(dividend==0)return 0;if(dividend==INT_MIN){if(divisor==-1)return INT_MAX;if(divisor==1)return INT_MIN;}bool sign=false;if(dividend>0){dividend=-dividend;sign=!sign;};if(divisor>0){divisor=-divisor;sign=!sign;};if(dividend>divisor)return 0;int res=0;int begin=1;int end;if(dividend==INT_MIN)end=INT_MAX;else {end=-dividend;}res=reverse(begin,end,divisor,dividend,res,sign);return sign?-res:res;}
private:bool quick(int mid,int divisor,int dividend,int res,int add){if(mid<=0)return true;if(mid&1){if(res<dividend-add)return false;res+=add;}if(mid!=1){if(add<dividend-add)return false;add+=add;}mid>>=1;return quick(mid,divisor,dividend,res,add);}int reverse(int begin,int end,int divisor,int dividend,int res,bool sign){if(begin>end)return res;int mid=begin+((end>>1)-(begin>>1));if(quick(mid,divisor,dividend,0,divisor)){res=mid;if(mid==INT_MAX)return mid;begin=mid+1;}else{end=mid-1;}return reverse(begin,end,divisor,dividend,res,sign);}
};

（4）模拟二分查找法

优化思路：二分查找法已经很优秀了，那还可不可以更加优秀呢？

当然可以咯，众所周知，时间复杂度和空间复杂度是此消彼长的关系

那么，我们可不可以牺牲空间复杂度来成就时间复杂度呢？

于是，这个办法就诞生了

思路：我们通过用一个vector来模拟二分查找法

我们将商的二进制的各个位数对应的权重都存储在这个vector中，

我们根据被除数的二进制的各个权重来决定要存多少个位数进入vector中，

在逐个取出vector中的权重减去被除数，来得出商

（这个方法，我受到的启发是力扣的那道，数字转罗马数字那道题）

以下是完整代码，如果你没有看懂我的描述，你可以结合代码中的注释好好理解一下

class Solution {
public:int divide(int dividend, int divisor) {if(dividend==0)return 0;//被除数为0，返回0if(dividend==INT_MIN){//被除数为INT_MINif(divisor==-1)return INT_MAX;if(divisor==1)return INT_MIN;}bool sign=false;//一个符号用来记录正负if(dividend>0){dividend=-dividend;sign=!sign;};//将被除数和除数全变成负数if(divisor>0){divisor=-divisor;sign=!sign;};if(dividend>divisor)return 0;//（此时被除数和除数全部是负数）如果被除数大于除数，返回0int res=0;//商vector<int>table={divisor};//用来存储商的权重while(table.back()>=dividend-table.back())table.push_back(table.back()<<1);//根据被除数来决定商的权重for(int i=table.size()-1;i>=0;i--){if(table[i]>=dividend){res+=(1<<i);//通过商的权重来得出商dividend-=table[i];//被除数减去商的权重}}return sign?-res:res;}
};

以上就是这道题的解析，希望能够帮到你，给你提供便利而没有浪费你的时间和精力

我还是提一嘴，纸上得来终觉浅，绝知此事要躬行哦

晚安