【leetcode】001整数相除

第一个版本代码：

• 考虑到：减法代替乘法
• 考虑到：减法代替乘法时需要转成同号，并且针对a b异号时将结果变为负的。
• 未考虑到：整数的范围：-2^31- 2^31 ，所以在转成同号时候，使用Math.abs(-2^31)结果还是 -2^31 ，所以比如：-2^31/1= -2147483648
  但是使用该算法在while(a>=b)判断时，-2^31并不大于1所以结果是0，计算错误。所以我们都转成负数就不会越界了。
• 未考虑到：另一个越界问题：我们知道整数的范围：-2^31- 2^31 ，所以我们在计算-2^31/-1= 2147483648，此时已经超过int类型的整数最大值了，所以针对这种情况我们应该再单独做约束。

class Solution {
    public int divide(int a, int b) {
        if(a==0) return 0;
        //首先，我们可以使用减法来代替乘法：
        //20-3=17 17-3=14 14-3=11 ...通过计算减法的次数就能算出商
        //其次，我们要考虑使用减法代替除法时，a与b的符号问题
        //a b同号则没问题，如果a，b异号则算法出错：a-b会越来越大或者越来越小
        //所以应该将a b转成同号，同时如果a b异号则结果肯定时负的，这个我们也应该记录
        int sign= 1;
        if((a>0&&b<0)||(a<0&&b>0)){
            sign=-1;
        }
        a=Math.abs(a);
        b=Math.abs(b);
        int res=0;
        while(a>=b){
            a=a-b;
            res++;
        }
        return sign*res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

第二个版本代码

• 考虑到：减法代替乘法。
• 考虑到：异号需要转成同号的情况。
• 考虑到：整数范围的情况：负数转成正数会越界。
• 考虑到：边界值的情况：分别对a和b等于 -2^31 、2^32、 1 、-1 、0等5种情况进行分析，找到 -2^31/-1 这种情况会越界，所以单独做处理。
• 未考虑到：时间限制的问题

class Solution {
    public int divide(int a, int b) {
        if(a==0) return 0;
        if(a==-2147483648&&b==-1) return 2147483647;
        //首先，我们可以使用减法来代替乘法：
        //20-3=17 17-3=14 14-3=11 ...通过计算减法的次数就能算出商
        //其次，我们要考虑使用减法代替除法时，a与b的符号问题
        //a b同号则没问题，如果a，b异号则算法出错：a-b会越来越大或者越来越小
        //所以应该将a b转成同号，同时如果a b异号则结果肯定时负的，这个我们也应该记录
        int sign= 1;
        if((a>0&&b<0)||(a<0&&b>0)){
            sign=-1;
        }
        //都转成相反数
        if(a>0) a=-a;
        if(b>0) b=-b;
        int res=0;
        while(a<=b){
            a=a-b;
            res++;
        }
        return sign*res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

时间复杂度的分析： O(n)级别时间复杂度，主要来源于while循环的复杂度，其中n最大应该为2147483647，对标 2147483647/1，显然n已经超过10^10（一般0(N)级别的，N不超过10的8次方）,这显然会超出时间限制，尤其是计算2147483647/1、2147483647/3，每次都会进行大量计算。必须对时间进行优化。

第三个版本代码

class Solution {
    public int divide(int a, int b) {
        if(a==0) return 0;
        if(a==-2147483648&&b==-1) return 2147483647;
        if(a==Integer.MIN_VALUE&&b==1) return Integer.MIN_VALUE;
        //首先，我们可以使用减法来代替乘法：
        //20-3=17 17-3=14 14-3=11 ...通过计算减法的次数就能算出商
        //其次，我们要考虑使用减法代替除法时，a与b的符号问题
        //a b同号则没问题，如果a，b异号则算法出错：a-b会越来越大或者越来越小
        //所以应该将a b转成同号，同时如果a b异号则结果肯定时负的，这个我们也应该记录
        int sign= 1;
        if((a>0&&b<0)||(a<0&&b>0)){
            sign=-1;
        }
        //都转成相反数
        if(a>0) a=-a;
        if(b>0) b=-b;
        int res=0;
        while(a<=b){
            int value=b;
            int k=1;
         while(value>=(0xc0000000) && a<=value+value){
            value=value+value;
            if(k>=Integer.MAX_VALUE / 2) return Integer.MIN_VALUE;
            k=k+k;
        }
            a=a-value;
            res=res+k;
        }
        return sign*res;
    }
}

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

规范题解：

// 时间复杂度：O(logn * logn)，n 是最大值 2147483647 --> 10^10
public int divide(int a, int b) {
    if (a == Integer.MIN_VALUE && b == -1)
        return Integer.MAX_VALUE;
    int sign = (a > 0) ^ (b > 0) ? -1 : 1;
    if (a > 0) a = -a;
    if (b > 0) b = -b;
    int res = 0;
    while (a <= b) {
        int value = b;
        int k = 1;
        // 0xc0000000 是十进制 -2^30 的十六进制的表示
        // 判断 value >= 0xc0000000 的原因：保证 value + value 不会溢出
        // 可以这样判断的原因是：0xc0000000 是最小值 -2^31 的一半，
        // 而 a 的值不可能比 -2^31 还要小，所以 value 不可能比 0xc0000000 小
        // -2^31 / 2 = -2^30
        while (value >= 0xc0000000 && a <= value + value) {
            value += value;
            // 代码优化：如果 k 已经大于最大值的一半的话，那么直接返回最小值
            // 因为这个时候 k += k 的话肯定会大于等于 2147483648 ，这个超过了题目给的范围
            if (k > Integer.MAX_VALUE / 2) {
                return Integer.MIN_VALUE;
            }
            k += k;
        }
        a -= value;
        res += k;
    }
    // bug 修复：因为不能使用乘号，所以将乘号换成三目运算符
    return sign == 1 ? res : -res;
}

作者：tangweiqun
链接：https://leetcode.cn/problems/xoh6Oh/solution/jian-dan-yi-dong-javac-pythonjs-zheng-sh-e8r6/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
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