来源:力扣(LeetCode)
实现 strStr() 函数。 给定两个整数,被除数 dividend 和除数 divisor。将两数相除,要求不使用乘法、除法和 mod 运算符。
返回被除数 dividend 除以除数 divisor 得到的商。
整数除法的结果应当截去(truncate)其小数部分,例如:truncate(8.345) = 8 以及 truncate(-2.7335) = -2
示例 1:
示例 2:
提示:
由于不能用除法、乘法和%运算,也就是说可以用减法,除法就是求出被除数
由多少个除数
加起来的结果集,那我们反过来用减法,每次被除数
减去除数
,记录减的次数,直到被除数
小于除数
,减了多少次就是商
由于忽略了被除数
是2^31
,除数
是1
或者-1
的情况,AC后速度超级慢,已经算超时了,故这种方式不行
为避免运算过程中出现超过32位限制,将入参全部转为负数运算,运算结果再根据入参符号判断正负(超限则返回Integer.MAX_VALUE)
题目要求不能使用除法,循环减则效率太低,那么可以采用位移实现除法操作(不了解位移请自行百度),因为位移只能实现除以2^0,2^1...2^n的操作,而divisor值可能落于2^(n-1)与2^n之间,所以需要循环(实现dividend除以2^(n-1)与2^n之间某个数的操作)来使dividend位移结果不断逼近divisor,直至得出最终结果,以下给出具体运算说明
将dividend右移n位,n符合dividend>>n的绝对值小于divisor绝对值,dividend>>(n-1)的绝对值大于divisor绝对值,则dividend除以divisor大于2^(n-1),小于2^n(自己代入数值进行验证,此处不予证明)。那么divisor乘以2^(n-1)小于dividend,乘以2^n大于dividend,divisor乘以2^(n-1)为当前循环最接近dividend的值。将dividend与divisor乘以2^(n-1)的差(相当于除法中的余数)重新赋值给dividend,重复计算dividend与divisor的最接近结果,直至最终dividend绝对值小于divisor绝对值,累加多次循环得出最终结果
这道题限制了简单的解题方式,实在想不到的好的办法,看到别人用二分,倍增乘法,还有用位移的,感叹计算机的神奇和自己的不足