Leetcode算法Java全解答--29. 两数相除

浅浅的花香味﹌ 2022-04-14 03:39 181阅读 0赞

# Leetcode算法Java全解答–29. 两数相除 #

### 文章目录 ###

*  Leetcode算法Java全解答--29. 两数相除
 *   *  题目
     *  想法
     *  结果
     *  总结
     *  代码
     *   *  我的答案
         *  大佬们的答案
         *  测试用例
     *  其他

## 题目 ##

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。
    
     示例 1:
    
     输入: dividend = 10, divisor = 3
     输出: 3
     示例 2:
    
     输入: dividend = 7, divisor = -3
     输出: -2
     说明:
    
     被除数和除数均为 32 位有符号整数。
     除数不为 0。
     假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231,  231 − 1]。本题中，如果除法结果溢出，则返回 231 − 1。

示例：

输入: dividend = 10, divisor = 3
         输出: 3
         示例 2:
    
         输入: dividend = 7, divisor = -3
         输出: -2

## 想法 ##

1.  累加被除数，知道大于除数
2.  （网上资源）

任何一个整数可以表示成以2的幂为底的一组基的线性组合，

即num=a\_020+a\_121+a\_222+…+a\_n2n。

基于以上这个公式以及左移一位相当于乘以2，

我们先让除数左移直到大于被除数之前得到一个最大的基。

然后接下来我们每次尝试减去这个基，如果可以则结果增加加2^k,然后基继续右移迭代，直到基为0为止。

因为这个方法的迭代次数是按2的幂知道超过结果，所以时间复杂度为O(log(n))。

## 结果 ##

超过99%的测试案例

时间复杂度/空间复杂度： log n/ 1

## 总结 ##

## 代码 ##

### 我的答案 ###

/**************************************
         * 题目
         给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
    
         返回被除数 dividend 除以除数 divisor 得到的商。
    
         示例 1:
    
         输入: dividend = 10, divisor = 3
         输出: 3
         示例 2:
    
         输入: dividend = 7, divisor = -3
         输出: -2
         说明:
    
         被除数和除数均为 32 位有符号整数。
         除数不为 0。
         假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231,  231 − 1]。本题中，如果除法结果溢出，则返回 231 − 1。
         **************************************/
    
        /**************************************
         *
         * 想法：
         *      1. 累加被除数，知道大于除数
         *
         *　　  2.（网上资源）  任何一个整数可以表示成以2的幂为底的一组基的线性组合，
         *      即num=a_0*2^0+a_1*2^1+a_2*2^2+…+a_n*2^n。
         *      基于以上这个公式以及左移一位相当于乘以2，
         *      我们先让除数左移直到大于被除数之前得到一个最大的基。
         *      然后接下来我们每次尝试减去这个基，如果可以则结果增加加2^k,然后基继续右移迭代，直到基为0为止。
         *      因为这个方法的迭代次数是按2的幂知道超过结果，所以时间复杂度为O(log(n))。
         *
         * 我的做法
         *      超过99%的测试案例
         *      时间复杂度/空间复杂度：  log n/ 1
         * 代码执行过程：
         *
         * 总结：
         *
         * ***********************************/
        public int divide(int dividend, int divisor) {
            // 相除时溢出处理
            if (divisor == 0 || dividend == Integer.MIN_VALUE && divisor == -1) {
                return Integer.MAX_VALUE;
            }
    
            // 求符号位
            int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1;
    
            // 求绝对值，为防止溢出使用long
            long dvd = Math.abs((long) dividend);
            long dvs = Math.abs((long) divisor);
    
            // 记录结果
            int result = 0;
    
            // 被除数大于除数
            while (dvd >= dvs) {
                // 记录除数
                long tmp = dvs;
                // 记录商的大小
                long mul = 1;
    
                while (dvd >= (tmp << 1)) {
                    tmp <<= 1;
                    mul <<= 1;
                }
    
                // 减去最接近dvd的dvs的指数倍的值（值为tmp）
                dvd -= tmp;
    
                // 修正结果
                result += mul;
            }
    
            return result * sign;
        }

### 大佬们的答案 ###

public int better(int dividend, int divisor) {
            if (dividend == 0 || divisor == 0) {
                return 0;
            }
            long d1 = dividend, d2 = divisor;
            long result = divideLong(Math.abs(d1), Math.abs(d2));
            result = d1 * d2 < 0 ? -result : result;
            if (result > Integer.MAX_VALUE || result < Integer.MIN_VALUE) {
                return Integer.MAX_VALUE;
            }
            return (int) result;
        }
        public long divideLong(long d1,long d2){
            if(d1<d2) {
                return 0;
            }
            long sum=d2,num=1;
            while(sum+sum<=d1){
                sum+=sum;
                num+=num;
            }
            return num+divideLong(d1-sum,d2);
        }

### 测试用例 ###

@Test
        public void test029() {
            // 创建测试案例
            int dividend1 = 10;
            int divisor1 = 3;
            int dividend2 = 7;
            int divisor2 = -3;
    
            int expResult1 = 3;
            int expResult2 = -2;
    
            Solution029 solution029 = new Solution029();
    
            int result1 = solution029.divide(dividend1, divisor1);
            int result2 = solution029.divide(dividend2, divisor2);
    
            Assert.assertEquals(expResult1, result1);
            Assert.assertEquals(expResult2, result2);
        }

## 其他 ##

代码托管码云地址：[https://gitee.com/lizhaoandroid/LeetCodeAll.git][https_gitee.com_lizhaoandroid_LeetCodeAll.git]

查看其他内容可以点击专栏或者我的博客哈：[https://blog.csdn.net/cmqwan][https_blog.csdn.net_cmqwan]

“大佬们的答案” 标签来自leetcode，侵权请联系我进行删改

如有疑问请联系，联系方式：QQ3060507060

[https_gitee.com_lizhaoandroid_LeetCodeAll.git]: https://gitee.com/lizhaoandroid/LeetCodeAll.git
[https_blog.csdn.net_cmqwan]: https://blog.csdn.net/cmqwan