最近工作上的事情比较多,一直没有时间做题。趁着间隙,赶紧补一下。两数相除虽然中等难度,但涉及很多细节和基础知识,值得好好分析一下。其中涉及一些思路,如果没有相关知识,很难解出该题。
两数相除
给定两个整数,被除数 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 位有符号整数,其数值范围是 [−2^31, 2^31 − 1]。本题中,如果除法结果溢出,则返回 2^31 − 1。
思路
分析
溢出问题
看完本题后,首先能考虑到的是溢出问题,溢出的可能性在两个位置:
- 被除数和除数的结果溢出
- 在计算的过程中,加法是否会导致结果溢出
对于第一种情况,最小值比最大值的范围要广,将被除数和除数分别带入最小值、最大值,发现只有一种情况会导致溢出,对这种情况需要提前做判断:
对于第二种情况,需要在写代码过程中时刻关注,核心思路为可以用差值来判断能否继续加数据。
统一符号
被除数和除数有正有负,为方便计算,可以将符号统一,计算出结果后,视情况对结果取反。
因为负值的范围比正值大,所以统一为负值最合适。当然负值的大小比较与正值相反,需要关注这点。
快速计算
经过统一符号后,被除数和除数的位置如下图所示:
正常方案
将-3不断相加,直到到达-10右侧,离-10最近的位置即为商。相加的结果不能位于-10左侧,这意味商的值多增加了1。
该方案最容易理解,但容易超时,如果被除数为最小值,除数为-1,则需要加2^31 − 1次。
快速乘
用加法模拟乘法运算,有什么更加快速的方法吗?可以使用快速乘算法。
如Y*Z=5*11= 5*(1011)=2^3*5*1+2^2*5*0+2^1*5*1+2^0*5*1=8*5*1+4*5*0+2*5**1+1*5*1=55
即根据Z的位数,每次将Y+=Y,如果当前位为1,则加最新的Y值,如果为0,则不加。
使用该算法,可以使用加法,快速计算出两个数值相乘的结果。
使用该方案,便为二分法计算提供了理论基础。
当然,除了快速乘之外,还有快速幂,大家有兴趣的话可以自行查看。
代码
代码位置为:https://github.com/shidawuhen/asap/blob/master/controller/algorithm/29-divide-two-integers.go
1 | /** |