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;}
};

以上就是這道題的解析，希望能夠幫到你，給你提供便利而沒有浪費你的時間和精力

我還是提一嘴，紙上得來終覺淺，絕知此事要躬行哦?

晚安