【Leetcode 29】 两数相除

题目描述

class Solution: def divide(self, dividend, divisor): sig = True if dividend*divisor > 0 else False # 判断二者相除是正or负 dividend, divisor= abs(dividend), abs(divisor) # 将被除数和除数都变成正数 count = 0 # 用来表示减去了多少个除数，也就是商为多少 while divisor <= dividend: # 当被除数小于除数的时候终止循环 dividend -= divisor count += 1 res = count if sig == True else -count # 给结果加上符号 return max(min(res, 2**31-1), -2**31)

方法二： 针对于第一种的缺陷, 我们应该想到让除数成倍的增长, 这样被除数进行的减法操作就会少很多.

class Solution: def divide(self, dividend, divisor): sig = True if dividend*divisor > 0 else False # 判断二者相除是正or负 dividend, divisor= abs(dividend), abs(divisor) # 将被除数和除数都变成正数 res = 0 # 用来表示减去了多少个除数，也就是商为多少 while divisor <= dividend: # 当被除数小于除数的时候终止循环 tmp_divisor, count = divisor, 1 # 倍增除数初始化 while tmp_divisor <= dividend: # 当倍增后的除数大于被除数重新，变成最开始的除数 dividend -= tmp_divisor res += count count += 1 # 更新除数扩大的倍数 tmp_divisor = divisor*count # 更新除数 res_value = res if sig == True else -res # 给结果加上符号 return max(min(res_value, 2**31-1), -2**31)

方法三：该方法是对方法二的优化, 因为方法二中还是用到了乘法，所以我们可以用移位运算来代替乘法运算, 每次移动一位相当于扩大了两倍, 这个时候大家应该能感觉出来方法三比方法二的计算速度可能会更快一些(因为方法二是除数扩大倍数是1倍1倍的增加, 而方法三中除数扩大的倍数是两倍两倍的增加).

class Solution: def divide(self, dividend, divisor): sig = True if dividend*divisor > 0 else False # 判断二者相除是正or负 dividend, divisor= abs(dividend), abs(divisor) # 将被除数和除数都变成正数 res = 0 # 用来表示减去了多少个除数（减去除数的次数），也就是商为多少 while divisor <= dividend: # 当被除数小于除数的时候终止循环 tmp_divisor, count = divisor, 1 # 倍增除数初始化 while tmp_divisor <= dividend: # 当倍增后的除数大于被除数重新，变成最开始的除数 dividend -= tmp_divisor res += count count <<= 1 # 向左移动一位 tmp_divisor <<= 1 # 更新除数(将除数扩大两倍) res_value = res if sig == True else -res # 给结果加上符号 return max(min(res_value, 2**31-1), -2**31)

方法四：python的作弊法，用//

class Solution: def divide(self, dividend, divisor): sig = False if dividend * divisor < 0 else True # 判断二者相除是正or负 dividend, divisor = abs(dividend), abs(divisor) tmp = dividend // divisor res_value = tmp if sig == True else -tmp return min(max(res_value, -2**31), 2**31 - 1)

class Solution: def divide(self, dividend: int, divisor: int) -> int: a, b, r, t = abs(dividend), abs(divisor), 0, 1 while a >= b or t > 1: if a >= b: r += t; a -= b; t += t; b += b else: t >>= 1; b >>= 1 return min((-r, r)[dividend ^ divisor >= 0], (1 << 31) - 1)

参考链接​​​ https://leetcode-cn.com/problems/divide-two-integers/solution/python-5-xing-by-knifezhu/

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。