本文主要是介绍【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 -= divisorcount += 1res = 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_divisorres += countcount += 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_divisorres += 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 // divisorres_value = tmp if sig == True else -tmpreturn min(max(res_value, -2**31), 2**31 - 1)
方法五：python 5行代码
class Solution:def divide(self, dividend: int, divisor: int) -> int:a, b, r, t = abs(dividend), abs(divisor), 0, 1while a >= b or t > 1:if a >= b: r += t; a -= b; t += t; b += belse: t >>= 1; b >>= 1return min((-r, r)[dividend ^ divisor >= 0], (1 << 31) - 1)
参考链接
https://leetcode-cn.com/problems/divide-two-integers/solution/chu-fa-dao-jian-fa-de-zhuan-hua-by-h_n/
https://leetcode-cn.com/problems/divide-two-integers/solution/python-5-xing-by-knifezhu/
这篇关于【Leetcode 29】 两数相除的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
