[力扣_29] 两数相除

题目入口:点击进入

前言:29和30题实不相瞒我想了一周,但是还是草草结尾,这道题尤为困难,因为位运算一直是自己的弱项,所以才琢磨良久,这题还是采用评论区大佬的思路,自己只能想到一点点门路。

相关算法:

  • 位运算——时间复杂度O(logn),空间复杂度——O(1)
  • 减法递增——时间复杂度O(logn),空间复杂度——O(1)

思路与算法:

题目表明了以下几个点:

  • 不能使用取模,除法,乘法
  • 只能存储32位整数的环境下进行

那么除了题目规定不能使用的运算,剩下的就只有:加减,左移,右移了,所以我们可以从这儿入手来解决,我们看个例子:10/3,在小时候是怎么做的呢?

3+3+3=9<10,这个时候还剩下一,显然加不上去了,那么就只能加3次,这是一个思路,就是让被除数每次减去除数,直到比除数小为止,但是,会超时,比如:

被除数为2^31,除数为2,那么我们将需要循环(2^31)/2,显然会超时的。

位运算

从上述思路我们可以得知,若使用位运算,则有<<和>>可以使用,我们来复习下这两个运算符:

  • <<

    • 左移一位,低位补0,也就是说,比如一个数8,二进制位1000,我们将其左移一位则变成了10000,那么增长为16
  • >>

    • 右移一位,高位补0,例如一个数8,二进制1000,我们将其右移一位变成0100,则为4

从上我们是不是可以得知,左移就等于乘了2,而右移是不是就等于除了2呢?我们再来模拟一下。拿10/3作例子,3的二进制为11,则将其不断左移:

  • 3<<1=110=6

    • 此时依旧小于10,我们将计数变量也左移一位,计数变量从1开始,原因是,3*1=3嘛,左移一位则变成10,也就是2
  • 6<<1=1100=12

    • 此时要大于10了,则肯定结果是不对的,但是我们可以发现,答案就在2与4之间

      • 4是由结果继续右移得到的,但是此时不能右移。
  • 这个时候怎么办?我们用10-6=4得到新的被除数,将除数恢复成3
  • 继续去判断,4>3,但是3<<1=6,还是大于4了,所以我们只能返回一个1,也就是3本身,它比4要小,但是它的两倍比4要大
  • 我们通过第一次的结果2加上第二次的结果1得到3
  • 验证一下,10/3不考虑余数的情况下也等于3,则能证明我们上述的思路是正确的

归纳一下:

  • 初始结果为1

    • 因为若被除数比除数小,则直接就能在边界情况时返回0
  • 判断除数<<是否大于被除数,若不大于,则将其右移动,直到它<<后的数大于被除数

    • 结果也跟着<<
  • 被除数减去此时最大的除数,恢复除数,重复1,2
  • 返回结果

千言不胜一张图,我们看下图来了解,也就是我们小时候最常用的竖立乘法:

img

注意:我愚笨,这种解法只能解决不用规定的运算符,放出来也是为了更为了解运算在计算机里是如何实现的,这题因为int和边界的限制,在INT_MAX/2的样例中会报错,所以只能用long来实现。

代码如下所示:

long dive(long a,long b)//精髓所在,采用递归的思想
{
    if(a<b) return 0;
    long count=1;//若被除数比除数大,则初始化为结果为1
    long c=b;
    while(a>=(c<<1))
    {
        c=c<<1;
        count=count<<1;
    }
    return count+dive((a-c),b);//结果累加
}
int divide(int dividend, int divisor){
  //特判
  if(dividend==divisor) return 1;//相等返回1,剪枝
  if(divisor==1) return dividend;//若除数等于1则返回其本身
  if(divisor==-1)//若除数等于-1.则对最小值要个判断,因为最小值若转换为最大值会越界
    if(dividend <= INT_MIN) return INT_MAX;
    else return -dividend;

  int flag=0;
  if(dividend>0&&divisor<0||dividend<0&&divisor>0) flag=1;
  
  long divdtemp=dividend;
  long divitemp=divisor;

  if(dividend<0) divdtemp=-divdtemp;
  if(divisor<0) divitemp=-divitemp;

  long res=dive(divdtemp,divitemp);
  
  if(flag) return 0-res;
  return res;
}

减法模拟

位运算可以对原码进行,但是不能对补码进行!

img

位运算解法虽然可以解决问题,但是达*不到全部要求*,我们来看边界条件:

img

为了方便记忆,我啰嗦一下,放上int的最大和最小值

-2147483648至+2147483647

这儿我们不提起复杂的计组知识,我们只需要知道:

若除数为-2147483648,我们使用位运算,必须将两数转换为正数来进行,但是若将这个数转换为正数,则越界了,所以在上种解法种,只能用long来存储。

竟然正数用不了,我们可否用负数来代替?但是负数又不能实现位运算,我们如何实现呢?想一下,左移是乘2,而不断加自己本身是否也是乘2呢?

  • 3<<1=6
  • 3+3=6
  • 6<<1=12
  • 6+6=12

诶,我们可以用自身相加来解决位移问题,那么我们来看如何解决边界问题。

我们从题意可知,其被除数和除数不会超过int的范围,那么我们可否将边界设为0

什么意思,我们可以拿INT_MIN=-2147483648减去每次的除数,来判断是否越界,若越界,则减去后肯定大于0,也就是说,只有除数每次倍增要大于或等于2147483648的时候,就达到了边界,则不继续了。

我们拿

img这个例子来看

在第一次循环,其每次的被除数和结果倍增如下所示:

img可以看到,我所框选的为此时的除数

它若再备增,则肯定超过了-2^31

我们若用-2^31去减去它,得到的数也就是超出的那一部分,但是是个正数,没有越界,可以用它来判断是否继续倍增

归纳一下:

  • 用自身相加实现倍增,等同于乘2和左移
  • 将被除数和除数转换为负数解决边界问题
  • 每次判断其倍增的数与INT_MIN的差是否大于0

    • 若不大于,则继续判断是否大于被除数(若大于,则未达到被除数,可以继续,若小于,则其不能继续)
    • 上述两条件是与。
  • 除数倍增,结果倍增
  • 将被除数为被除数减去除数(负数相减即为相加,将除数恢复)

代码如下所示:

int dive(int a,int b)
{
    if(b<a) return 0;//边界,因为是负数,则除数不能大于被除数
    int count=1;//若不达到边界,则初始化为1
    int c=b;
    while(INT_MIN-(c+c)<0&&a<=(c+c))//精髓所在
    {
        c+=c;
        count+=count;
    }
    return count+dive((a-c),b);
}
int divide(int dividend, int divisor){
  //边界处理
  if(dividend==divisor) return 1;
  if(divisor==1) return dividend;
  if(divisor==-1)
    if(dividend <= INT_MIN) return INT_MAX;
    else return -dividend;
  
  int flag=0;//符号标记
  if(dividend>0&&divisor<0||dividend<0&&divisor>0) flag=1;
  
  int divdtemp=0;
  int divitemp=0;
  //全部转换为负数
  if(dividend>0)
     divdtemp=-dividend;
  else
     divdtemp=dividend;
  if(divisor>0)
     divitemp=-divisor;
  else
     divitemp=divisor;

  //将负数递归
  int res=dive(divdtemp,divitemp);
  
  if(flag) return 0-res;
  return res;
}

本文链接:

https://nullcode.fun/76.html
1 + 2 =
快来做第一个评论的人吧~