題目描述
解題思路：
1.本題不允許采用除法直接計(jì)算。所以我們可以采用加法逼近的方法 。也就是把多少個(gè)除數(shù)相加以后最近接被除數(shù) 則得到的多少個(gè)除數(shù)的這個(gè)數(shù)字就是相除后的商舉例來說，例如 23/3=7 這個(gè)除法我們就是讓 3+3+3+ 。。。。。+3 N個(gè)3相加得到不大于23且最接近23 的的數(shù)字時(shí)候，這個(gè)時(shí)候需要用到的數(shù)字N就是商，這里我們可以看到3X7=21 3X8=24 即商為7 即7個(gè)3累加的時(shí)候最接近23且 余數(shù)2 。
2.如何找到數(shù)字N呢,如果采用一個(gè)循環(huán)不停地做3的累加直到最近接被除數(shù)為止的話這樣可以得到答案但是需要循環(huán) 23/3次復(fù)雜度為O（N）顯然計(jì)算速度太慢。有沒有更快的辦法的呢？可以采用類似折半查找的辦法，這里我們可以用翻倍逼近的辦法來做如下操作。用被除數(shù)不斷地乘上2做數(shù)字的翻倍的操作直到超過被除數(shù)后 ，然后對剩下的余數(shù)做類似操作 ，直至得到的余數(shù)小于被除數(shù)或者為0 回到例子來說 23/3 :
a . 3翻倍：3?2=6 余數(shù)17
b. 再次翻倍 6?2=12 ; 余數(shù)11
c. 再次翻倍128?2=24 此時(shí)24 大于23 了 返回b 此時(shí)3×2^2 余數(shù)為11 加權(quán)值p=2
d 用11/3繼續(xù)上述操作直至余數(shù)小于3 此時(shí)為3×2^1 余數(shù)為5 加權(quán)值p=1，
5/3 繼續(xù)上述操作直至余數(shù)小于3 此時(shí)為3*2^0 余數(shù)為2 此時(shí)循環(huán)結(jié)束 加權(quán)值p=0 每一步得到一個(gè)每一位數(shù)的權(quán)值序列：【2,1,0】
最后商的數(shù)字為2^2 + 2^1 + 2^0 = 4+2+1 =7
具體代碼為
def divide(self, dividend, divisor):
"""
:type dividend: int
:type divisor: int
:rtype: int
"""
sign = -1 if (divisor>0)^(dividend>0) else 1
if abs(dividend)<abs(divisor) : return 0
if abs(dividend)== abs(divisor) :return sign
#r 是余數(shù) ，n是除數(shù) bit記錄每一個(gè)加權(quán)位指數(shù)位數(shù)例如
# 23/3 23=3*2^2+3*2^1 +3*2^0 =21 最后余2 商為2^2+2^1+2^0 = 7 3*7=21 余數(shù)2
def recurvediv(r,n,bit):
if r<n :return
i = 0
divsor = n
maxval = 0
while(divsor<=r):
if divsor <=r:
i+=1
maxval = divsor
divsor<<=1
r = r-maxval
bit.append(i)
recurvediv(r,n,bit)
res = []
result = 0
recurvediv(abs(dividend),abs(divisor),res)
for i in res:
result += 2**(i-1)
result*=sign
if result >=-1*2**31 and result <=2**31-1:
return result
else:
return 2**31-1
總結(jié)
采用翻倍的辦法后計(jì)算的循環(huán)的次數(shù)可以N= lg(N/2)+lg(N/4) +.....+lg(1)~O(lg(N)*lg(N))顯然比單個(gè)累加要好很多,本算法采用遞歸最大遞歸嵌套層數(shù)為lg(N/2)所以如果計(jì)算數(shù)字較大應(yīng)考慮遞歸超限制問題?？梢粚⑦f歸改為迭代。
