[力扣_29] 两数相除

444
[ LeetCode ] [ 算法基础 ]

题目入口：点击进入

前言：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 + 3 =
快来做第一个评论的人吧~