两数相除

发布: 分类: 评论次数： 阅读次数： 本文字数： 1k

从今天开始学习一下其他大佬，，在自己的小破站上记录一下自己在leetcode上遇到的坑和一些超级大佬的思想。

今天由于是第一次记录刷题的经验（原本我这个小破站是主打各种番剧的，尤其是那种，你懂的(>^ω^<)），可能会有些不足，还望海涵。。。。。

题目介绍

给定两个整数，dividend与divisor，两数相除，不能使用乘法，触法，mod运算，返回商，小数部分向零截断，当除法结果溢出，返回Integer.MAX_VALUE.

我的解法

一开始我自然是按照最基本的方法去做，既然乘法与除法等都不让用，那我加法总可以吧，所以一开始我的做法是这样的：

1
2
3
4
5
6
7
int ans = 0;
int k = 0;
while(ans <= dividend){
	ans += divisor;
	k++;
}
return tag * (k-1);

结果嘛，显而易见的只过了两个测试用例，，到了第三个用例，就直接报了超出时间限制的错（很明显）

接下来，既然超出时间限制，那就加快累加：

1
2
3
4
5
6
int ans = divisor;
int k = 1;
while(ans+ans<=dividend){
	ans += ans;
	k += k;
}

这里我没有完整写出，举个例子：31/3

3+3=6 k=2

6+6=12 k=4

12+12=24 k=8

24+24=48>31

说明最后的结果一定大于等于8，但是大多少，，我当时并没有想出方法，后面看了大神的方法才知道，先暂时不说

最后，我的想法就是递归，，可以我写了好久都没递归出来（对于递归我实在没什么法子，，脑袋太笨）

本题解答思路

  • 最常见的位操作（左移乘2）

    思路上就是将除数不断移位，使其逼近被除数，举个例子：31/3

    3<<1 = 6

    3<<2 = 12

    3<<3 = 24

    3<<4 = 48 > 31

    被除数=被除数-24 = 7

    3<<1 = 6

    3<<2 = 12 > 7

    被除数=被除数-6 = 1

    1<3

    退出

    代码如下：

    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
    public int divide(int dividend, int divisor){
        //判断符号
        int tag = 0;   // -1表示负，1表示正
        if((dividend>0 && divisor<0) || (dividend<0 && divisor>0)){
            tag = -1;
        }else if(dividend==0){
            return 0;
        }else{
            tag = 1;
        }
      
        //溢出处理
        if(dividend==Integer.MIN_VALUE && divisor==-1){
            return Integer.MAX_VALUE;
        }
      
        long d1 = Math.abs((long) dividend);
        long d2 = Math.abs((long) divisor);
      
        int k = 0;
        int ans = 31;
        //计算结果值
        while (ans>=0){
            if(d1 < d2<<ans){
                ans--;
                continue;
            }
            k += (1<<ans);
            d1 -= d2<<ans;
        }
        return tag * k;
    }

    (注意，上述代码里的左移位数是直接从31开始往下减，这样可以对较大的数逼近的更快)

    不知道细心的同学有没有发现啥，没错，移位的思想和我之前的第二种想法很像，只是我是加，它是移位

  • 累加+递归

    累加的想法就是我那个，至于递归，看看代码就懂了

    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
     public int divide(int dividend, int divisor){
        if(dividend==Integer.MIN_VALUE && divisor==-1){
            return Integer.MAX_VALUE;
        }
        int tag = 1;
        if((dividend<0 && divisor>0) || (dividend>0 && divisor<0)){
            tag = -1;
        }
        //将被除数与除数全部转为负数（负数的范围比正数大）
        int a = dividend>0?-dividend:dividend;
        int b = divisor>0?-divisor:divisor;
      
        int ans = div(a,b);
        if(tag==1){
            return ans;
        }else{
            return -ans;
        }
      
    }
    private int div(int a,int b){
        if(a>b){
            return 0;   //负数
        }
        int b1 = b;
        int ans = 1;
        while(b1 + b1 >= a && b1 + b1 <0){
            b1 += b1;
            ans += ans;
        }
        return ans + div(a - b1,b);
    }

    这个代码里最精彩的地方不是递归，不是累加，而是对溢出的处理：

    首先，现将被除数与除数全部转化为负数，（原因是在32位有符号整数中，负数的范围比正数大）；其次，通过判断b1+b1的符号来判断累加中是否溢出，因为两个负数累加后溢出一定是正数

结束

以上就是我在这道题里学到的东西—对溢出的特殊判断，以及我思路上的断线是在哪断的这个问题