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

淡淡的烟草味﹌ 2022-03-06 03:16 148阅读 0赞

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

![clipboard.png][]

## 题目大意 ##

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

备注：  
1.除数和被除数都是32位有符号整数  
2.除数不为0  
3.假设我们正在处理一个只能在32位有符号整数范围内存储整数的环境\[−231,  231 − 1\],对于这个问题如果结果溢出了，则可以返回231 − 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));
        }
    
    }

## 时间和空间复杂度 ##

![clipboard.png][clipboard.png 1]

![clipboard.png][clipboard.png 2]

看到上面的运行时间心里凉了大半啊！，看来还有更好的方法，有时间的话写一下最优解的思路  
,此处立下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的情况是取值为−231）  
    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导致溢出
 *  修改方式  
    直接将这个用例视为特殊情况处理之，直接返回整值最大

--------------------

[clipboard.png]: /images/20220306/1432cd5984514a8dac684c39aff6d1f6.png
[clipboard.png 1]: /images/20220306/86b24197d9304df899c132d2e8478616.png
[clipboard.png 2]: /images/20220306/9d4f3c4f6c8c4dab8935471a7ee6e697.png