29.两数相除
class Solution:
def divide(self, dividend: int, divisor: int) -> int:
sign = 1 if dividend>0 and divisor>0 or dividend<0 and divisor<0 else -1#结果的符号
dividend = dividend if dividend > 0 else -dividend
divisor = divisor if divisor > 0 else -divisor
#两数转化为正数进行计算
ans = 0
while dividend >= divisor:#当被除数大于除数,循环进行
cur = divisor
multiple = 1
while cur + cur < dividend:#找到不大于当前被除数的最大x(x=2的n次方)
cur += cur#divisor*x,每次乘二
multiple += multiple#x,每次乘二
dividend -= cur#找到后减去当前值
ans += multiple#结果加上当前的最大x
ans = ans if sign == 1 else -ans
#处理溢出
ans = ans if ans <= 2147483647 else 2147483647
ans = ans if ans >= -2147483648 else 2147483648
return ans
这个题想了很久,但做出来还是不明白和二分查找的联系在哪里
大佬的解释
@144.0.33 二分查找算法的英文翻译是:binary search algorithm,也可以翻译为二进制搜索,是一种时间复杂度为O(logn)的查找算法,二分查找虽然思想简单,但是应用范围极广(具体可以*上看看),核心思想是每次将有序数组分为一半,则k次操作之后就是原数组的n/2^k个元素,直到这个值变为1,就查找到了那个元素。
对于本题,则是以上思想的逆运算,是从1开始,不断变为二倍的搜索,直到满足要求,因此本题也是考察二分查找思想的运用。
本方法的时间复杂度应该是O(logn * logn),内外while循环都是logn
菜鸡的感悟
对一个算法,不仅要记住,会用,更应该深入地理解这个算法的思想。这道题的对二分查找逆向的思想就很重要。
更加详细的算法及分析请移步leetcode