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

题目大意

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

备注：

1.除数和被除数都是32位有符号整数2.除数不为03.假设我们正在处理一个只能在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]没用通过

第二次尝试（失败?）

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

第三次尝试（失败?）

• 分析失败原因
  没有考虑负数的最大值的绝对值溢出了
• 修改方式
  修改思路
  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的其他用例可以处理

第四次尝试（成功✌️）

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

---