LeetCode刷题——29. Divide Two Integers（Part 1靠自己）

当我第一次看到这个题目时候我我心想不就是两数相除嘛，这么简单的题目为什么要放到 Medium 中，事实证明我当时的想法Too young,Too simple,Too naive 以至于被打脸n次，可以直接查看最后答案，中间我的思路自白可以忽略。

题目大意

给两个数字，除数和被除数，在不使用乘、除、取模的方法做除法，返回两数之商

备注：

1.除数和被除数都是32位有符号整数

2.除数不为0

3.假设我们正在处理一个只能在32位有符号整数范围内存储整数的环境[−2 ³¹ ,  2 ³¹ − 1],对于这个问题如果结果溢出了，则可以返回2 ³¹ − 1

解题代码

public class Solution {
    /**整体思路是用减法**/
    public int divide(int dividend, int divisor) {
        // 符号相同用减法
        if(dividend==Integer.MIN_VALUE&&divisor==-1) {
            return Integer.MAX_VALUE;
        }
        
        if ((dividend ^ divisor) >= 0) {
            return getQuotientUsesSubtraction(dividend, divisor);
        } else {
            int absDividend = Math.abs(dividend);
            int absDivisor = Math.abs(divisor);
            if (absDividend < 0) {
                absDivisor = -absDivisor;
            } else if (absDivisor < 0) {
                absDividend = -absDividend;
            }
            return 0 - getQuotientUsesSubtraction(absDividend, absDivisor);
        }
    }

    /**
     * 使用减法获取两个数的商 除数dividend，被除数divisor
     * 条件：dividend*divisor >0 且divisor>0
     */
    private int getQuotientUsesSubtraction(int dividend, int divisor) {
        int quotient = 0;
        if (dividend >= 0)
            while (dividend >= divisor) {
                quotient++;
                dividend = dividend - divisor;
            }
        else {
            while (dividend <= divisor) {
                quotient++;
                dividend = dividend - divisor;
            }
        }
        return quotient;

    }
}

测试用例

用的是 junit5，如果是4或者3的胖友自己修改下

import org.junit.Assert;
import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.api.Test;

@DisplayName("不用乘除取模运算计算除数")
public class TestSolution {
    @Test
    @DisplayName("MIN_VALUE情况和1")
    void e1() {
        int out = Integer.MIN_VALUE;
        Solution s = new Solution();
        Assert.assertEquals(out, s.divide(Integer.MIN_VALUE, 1));
    }
    @Test
    @DisplayName("MIN_VALUE情况和-1")
    void e9() {
        int out = Integer.MAX_VALUE;
        Solution s = new Solution();
        Assert.assertEquals(out, s.divide(Integer.MIN_VALUE, -1));
    }

    @Test
    @DisplayName("除数是0情况")
    void e2() {
        int out = 0;
        Solution s = new Solution();
        Assert.assertEquals(out, s.divide(0, 1));
    }

    @Test
    @DisplayName("符号相反")
    void e3() {
        int out = -1;
        Solution s = new Solution();
        Assert.assertEquals(out, s.divide(1, -1));
    }

    @Test
    @DisplayName("符号相同")
    void e4() {
        int out = 1;
        Solution s = new Solution();
        Assert.assertEquals(out, s.divide(-1, -1));
    }

    @Test
    @DisplayName("除数MIN_VALUE和被除数MAX_VALUE")
    void e5() {
        int out = -1;
        Solution s = new Solution();
        Assert.assertEquals(out, s.divide(Integer.MIN_VALUE, Integer.MAX_VALUE));
    }

    @Test
    @DisplayName("除数MAX_VALUE和被除数MIN_VALUE")
    void e6() {
        int out = 0;
        Solution s = new Solution();
        Assert.assertEquals(out, s.divide(Integer.MAX_VALUE, Integer.MIN_VALUE));
    }

    @Test
    @DisplayName("冒烟测试10,3")
    void e7() {
        int out = 3;
        Solution s = new Solution();
        Assert.assertEquals(out, s.divide(10, 3));
    }

    @Test
    @DisplayName("冒烟测试7,-3")
    void e8() {
        int out = -2;
        Solution s = new Solution();
        Assert.assertEquals(out, s.divide(7, -3));
    }

}

时间和空间复杂度

看到上面的运行时间心里凉了大半啊！，看来还有更好的方法，有时间的话写一下最优解的思路

,此处立下flag，我要写 Part 2靠大家

初级解题思路（ ‍♀️此处开始为我折腾过程不重要，可以忽略）

既然乘、除、取模都用不了就用减法吧。两数取商用减法的角度思考 就是，被除数可以减几个除数。因为题目取值范围是包含负值的所以要区分符号，相同符号则返回正数，符号相反则返回负值

第一次尝试（失败 ）

• 思路：

1. 取两个数的绝对值
2. 当被除数大于除数时，计算相减次数，小于时则直接返回0
3. 当两数相同符号则返回相减次数，符号相反则返回相减次数负值

• 代码：

  class Solution {
      public int divide(int dividend, int divisor) {
          int absDividend= Math.abs(dividend);
          int absDivisor= Math.abs(divisor);
          int quotient =0;
          while(absDividend>absDivisor){
              quotient++;
              absDividend=absDividend-absDivisor;
          }
          if((dividend^divisor)>= 0){
              return quotient;
          }else{
              return 0-quotient;
          }
      }
  }

• 结果
  自测的两个冒烟测试用例通过，但是用例[1,1]没用通过

第二次尝试（失败:fearful:）

• 分析失败原因
  循环的时候没有考虑相等的情况
• 修改方式
  while(absDividend>absDivisor) 改为 while(absDividend>=absDivisor)
• 修改后[1,1]用例通过，但是未通过用例[-2147483648,-1]

第三次尝试（失败:cold_sweat:）

• 分析失败原因
  没有考虑负数的最大值的绝对值溢出了
• 修改方式
  修改思路
  1.符号相同的时候直接获取相减次数
  2.符号不同的时候，取两数的绝对值
  3.判断两数的绝对值是否大于0，（小于0的情况是取值为−2 ³¹ ）
  4.大于0时，返回相减次数的绝对值
  5.小于0时，将大于0的数取反数再计算相减次数，返回相减次数的反数

• 代码

  class Solution {
      public int divide(int dividend, int divisor) {
          // 符号相同用减法
          if ((dividend ^ divisor) >= 0) {
              return getQuotientUsesSubtraction(dividend, divisor);
          } else {
              int absDividend = Math.abs(dividend);
              int absDivisor = Math.abs(divisor);
              if (absDividend < 0) {
                  absDivisor = -absDivisor;
              } else if (absDivisor < 0) {
                  absDividend = -absDividend;
              }
              return 0 - getQuotientUsesSubtraction(absDividend, absDivisor);
          }
      }
     
      private int getQuotientUsesSubtraction(int dividend, int divisor) {
          int quotient = 0;
          if (dividend >= 0)
              while (dividend >= divisor) {
                  quotient++;
                  dividend = dividend - divisor;
              }
          else {
              while (dividend <= divisor) {
                  quotient++;
                  dividend = dividend - divisor;
              }
          }
          return quotient;
  
      }
  }

• 结果
  未通过用例[-2147483648,-1]，但是可以处理除数或被除数为-2147483648的其他用例可以处理

第四次尝试（成功:v:）

• 分析失败原因
  没有考虑负数最大值除以-1导致溢出
• 修改方式
  直接将这个用例视为特殊情况处理之，直接返回整值最大