lc29-两数相除

三月 07, 2022 2047

29.两数相除

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2

示例 1:
输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = truncate(3.33333..) = truncate(3) = 3
示例 2:
输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = truncate(-2.33333..) = -2

提示：
被除数和除数均为 32 位有符号整数。
除数不为 0。
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231,  231 − 1]。本题中，如果除法结果溢出，则返回 231 − 1。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/divide-two-integers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

Solution

Corner Case

1.32位 int 范围 -2^31 ~ 2^31-1

将X Y 均变为 负数考虑 避免 2^31正数溢出

2.被除数 为 0 return 0

3.被除数 -2^31 除数为1 溢出 返回 2^31-1

4.除数为-2^31 被除数也为-2^31 返回 1 否则返回0

Main

快速幂（二分
X/Y=Z （X,Y均考虑负数）则有 Z*Y≥X>(Z+1)Y 成立 找到正数Z满足此公式即可
注意 本题不可使用 ‘’运算 因此用‘快速乘’ （加法实现）替代
迭代法 快速幂 对于除数 判断被除数是否大于除数 满足 继续判断 判断被除数是否大于除数的两倍

Code

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
34
35
36
37
38
39
40
41
42
43
//myCode
class Solution {
public:
    int divide(int a, int b) {
        bool flag=true;
        if((a<0&&b>0)||(a>0&&b<0)) flag=false; //判断正负
        if(a>0) a=-a; //转负数防止溢出 
        if(b>0) b=-b;

        //corner case
        if(a==0) return 0;
        if(abs(b)==pow(2,31))
        {
            if(abs(a)==pow(2,31))
                return 1;
            else return 0;
        }

        // X/Y=Z   y *2 *2 *2  -16 -2   2,-12,-4
        long z=0;
        long temp=b; //除数
        while(a<=b) //-15 -2
        {
            long cnt=1;
            while(a<temp) //-15 -8
            {
                if(temp+temp>a)
                {
                    cnt+=cnt;
                    temp+=temp;
                }
                else
                    break;
            }
            a-=temp;
            temp=b;
            z+=cnt;
        }
        if((flag==true&&z>pow(2,31)-1)||z>pow(2,31))return pow(2,31)-1;

        return flag==true?z:(-1*z);
    }
};
查看评论