发布于 

整数除法 | 笔记整理!

整数除法 | 笔记整理!

小知识点 | 总结

快速幂思路优化

加法优化

1
2
3
4
5
6
7
8
def quick_mul(x,y):
    ans=0
    while y:
        if y&1:
            ans+=x
        x+=x
        y>>=1
    return ans

幂乘优化 

1
2
3
4
5
6
7
8
def quick_pow(x,y):
    ans=0
    while y:
        if y&1:
            ans+=x
        x<<=1
        y>>=1
    return ans

整数二分 | 向下取整 -> 左闭右开区间思路

寻找后继 | 向上取整

1
2
3
4
5
6
7
8
9
10
def binary_search_right(nums,n,val):
    # 左闭右开区间
    l,r=0,n
    while l<r:
        mid=l+r>>1
        if nums[mid]>=val:
            r=mid
        else:
            l=mid+1
    return l

寻找前驱 | 向下取整

1
2
3
4
5
6
7
8
9
10
def binary_search_left(nums,n,val):
    # 左闭右开区间
    l,r=0,n
    while l<r:
        mid=(l+r+1)>>1
        if nums[mid]<=val:
            l=mid
        else:
            r=mid-1
    return l

特判 + 符号 | 二分 + 加法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
    def divide(self, a: int, b: int) -> int:
        
        # 快速幂优化
        def quick_mul(x,y):
            ans=0
            while y:
                if y&1:
                    ans+=x
                x+=x
                y>>=1
            return ans
        
        # 先进行特判
        INT_MIN,INT_MAX=-2**31,2**31-1
        if a==INT_MIN:
            if b==1:return a
            if b==-1:return INT_MAX
        # 二分实现 经典的左闭右开区间
        tag=1 if a*b>=0 else -1
        if a<0:a=-a
        if b<0:b=-b
        
        def binary_search_left(l,r):
            while l<r:
                mid=l+r+1>>1
                if quick_mul(mid,b)<=a:
                    l=mid
                else:
                    r=mid-1
            return l
        ans=binary_search_left(0,a)
        return ans*tag

模拟实现 | 但不符合题目要求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def divide(self,a: int, b: int) -> int:
        INT_MIN,INT_MAX=-2**31,2**31-1
        if a==INT_MIN:
            if b==1:return a
            if b==-1:return INT_MAX

        t=1 if a*b>=0 else -1
        m,n=str(abs(a)),str(abs(b))
        flag=['0']*len(m)
        def helper(x,y):
            r=0
            for i in range(len(m)):
                r=r*10+ord(x[i])-ord('0')
                if r<y:
                    flag[i]='0'
                else:
                    flag[i]=str(r//y)
                    r%=y
        helper(m,abs(b))
        return t*int(''.join(flag))
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

快来参与讨论吧