当前位置：首页 > news >正文

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

news 来源：原创 2024/4/25 12:36:06

当我第一次看到这个题目时候我我心想不就是两数相除嘛，这么简单的题目为什么要放到 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靠大家

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

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

第一次尝试（失败?）

思路：

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

代码：

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;

    }
}