梅西网页设计作业,焦作seo推广,佛山品牌网站建设报价,石家庄工程官网文章目录 1. 题目2. 思路及代码实现详解#xff08;Python#xff09;2.1 位运算与二分查找 1. 题目
给你两个整数#xff0c;被除数 d i v i d e n d dividend dividend 和除数 d i v i s o r divisor divisor。将两数相除#xff0c;要求 不使用 乘法、除法和取余运算… 文章目录 1. 题目2. 思路及代码实现详解Python2.1 位运算与二分查找 1. 题目
给你两个整数被除数 d i v i d e n d dividend dividend 和除数 d i v i s o r divisor divisor。将两数相除要求 不使用 乘法、除法和取余运算。
整数除法应该向零截断也就是截去 t r u n c a t e truncate truncate其小数部分。例如 8.345 8.345 8.345 将被截断为 8 8 8 − 2.7335 -2.7335 −2.7335 将被截断至 − 2 -2 −2。
返回被除数 d i v i d e n d dividend dividend 除以除数 d i v i s o r divisor divisor 得到的 商 。 注意假设我们的环境只能存储 32 32 32 位 有符号整数其数值范围是 [ − 2 31 , 2 31 − 1 ] [−2^{31}, 2^{31} − 1] [−231,231−1] 。本题中如果商 严格大于 2 31 − 1 2^{31} − 1 231−1 则返回 2 31 − 1 2^{31} − 1 231−1 如果商 严格小于 − 2 31 -2^{31} −231 则返回 − 2 31 -2^{31} −231 。 示例 1:
输入: d i v i d e n d 10 , d i v i s o r 3 dividend 10, divisor 3 dividend10,divisor3 输出: 3 3 3 解释: 10 / 3 3.33333.. 10/3 3.33333.. 10/33.33333..向零截断后得到 3 3 3。
示例 2:
输入: d i v i d e n d 7 , d i v i s o r − 3 dividend 7, divisor -3 dividend7,divisor−3 输出: − 2 -2 −2 解释: 7 / − 3 − 2.33333.. 7/-3 -2.33333.. 7/−3−2.33333.. 向零截断后得到 − 2 -2 −2。 提示 − 2 31 d i v i d e n d , d i v i s o r 2 31 − 1 -2^{31} dividend, divisor 2^{31} - 1 −231dividend,divisor231−1 d i v i s o r ≠ 0 divisor \neq 0 divisor0
2. 思路及代码实现详解Python
由于题目规定了「只能存储 32 32 32 位整数」因此不能使用任何 64 64 64 位整数尽管这会极大增加我们编码难度。对于可能造成溢出的问题在编码之前需要先对于溢出或者容易出错的边界情况进行讨论即在某一边界上继续进行操作后会溢出这个边界取决于我们会采取何种操作
当被除数为 32 32 32 位有符号整数的最小值 − 2 31 −2^{31} −231 时 如果除数为 1 1 1那么我们可以直接返回答案 − 2 31 −2^{31} −231如果除数为 − 1 −1 −1那么答案为 2 31 2^{31} 231这时结果产生了溢出。此时我们需要返回 2 31 − 1 2^{31}-1 231−1 当除数为 32 32 32 位有符号整数的最小值 − 2 31 −2^{31} −231 时 如果被除数同样为 − 2 31 −2^{31} −231那么我们可以直接返回答案 1 1 1对于其余的情况我们返回答案 0 0 0因为得到的商不大于 1 1 1 时截断小数部分得到 0 0 0。 当被除数为 0 0 0 时不论除数是多少都直接返回答案 0 0 0。
对于其他的一般情况根据除数和被除数的符号我们需要考虑 4 4 4 种不同的符号组合。因此为了方便编码我们可以将被除数或者除数取相反数使得它们符号相同。
如果将被除数和除数都变为正数那么可能会导致溢出。例如当被除数为 − 2 31 −2^{31} −231 时它的相反数 2 31 2^{31} 231 产生了溢出。如果将被除数和除数都变为负数这样在取相反数时就不会有溢出的问题而结果溢出也只有 ( − 2 31 ) / ( − 1 ) (-2^{31})/(-1) (−231)/(−1) 这种情况。
如果我们恰好只将被除数和除数中的一个变为了正数那么在返回答案之前我们需要对答案也取相反数。
2.1 位运算与二分查找
上面的讨论考虑了数值溢出的问题以及几种可以直接返回结果的特殊情况。我们记被除数为 X X X除数为 Y Y Y且此时两者都被我们转为负数我们要求的是 X / Y X/Y X/Y 的结果 Z Z Z显然 Z Z Z 的值一定为整数或 0 0 0。
因为 Y Y Y 为负值随着 Z Z Z 增大乘积减小容易得到 Z × Y ≥ X ( Z 1 ) × Y Z\times Y\geq X\gt (Z1)\times Y Z×Y≥X(Z1)×Y因此我们求商就是找到最大的使得 Z × Y X Z\times Y\gt X Z×YX 成立的 Z Z Z。而由于不能使用乘法运算就需要用到快速乘的算法。其实就是通过二分查找和位移运算来实现所谓的 乘法但其本质是加法的快速运算和判断。
具体的代码如下判断不等式的次数为 O ( l o g C ) O(logC) O(logC)而判断函数的搜索范围是 32 32 32 位整数的全部范围最差情况下也要 O ( l o g C ) O(logC) O(logC) 的判断次数因此总的时间复杂度为 O ( l o g 2 C ) O(log^2C) O(log2C)而空间复杂度为 O ( 1 ) O(1) O(1)仅存储若干的上下界信息。
class Solution:def divide(self, dividend: int, divisor: int) - int:INT_MIN, INT_MAX -2**31, 2**31 - 1# 考虑被除数为最小值的情况if dividend INT_MIN:if divisor 1:return INT_MINif divisor -1:return INT_MAX# 考虑除数为最小值的情况if divisor INT_MIN:return 1 if dividend INT_MIN else 0# 考虑被除数为 0 的情况if dividend 0:return 0# 一般情况使用二分查找# 将所有的正数取相反数这样就只需要考虑一种情况rev Falseif dividend 0:dividend -dividendrev not revif divisor 0:divisor -divisorrev not rev# 快速乘def quickAdd(y: int, z: int, x: int) - bool:# x 和 y 是负数z 是正数# 需要判断 z * y x 是否成立result, add 0, ywhile z 0:if (z 1) 1: # 需要保证 result add xif result x - add:return Falseresult addif z ! 1:# 需要保证 add add xif add x - add:return Falseadd add# 不能使用除法退位z 1return Trueleft, right, ans 1, INT_MAX, 0while left right:# 注意溢出并且不能使用除法mid left ((right - left) 1)check quickAdd(divisor, mid, dividend)if check:ans mid# 注意溢出if mid INT_MAX:breakleft mid 1else:right mid - 1return -ans if rev else ans执行用时45 ms 消耗内存16.45 MB
题解来源力扣官方题解
