LeetCode第29题 – 两数相除

319 views

题目

给定两个整数,被除数 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。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/divide-two-integers
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解答

class Solution {
    public int divide(int dividend, int divisor) {
        if (dividend == 0) {
            return 0;
        }
        
        
        boolean adjust = true;
        if (dividend == divisor) {
            return 1;
        }
        
        if ((dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0)) {
            adjust = false;
        }
        
        if (dividend == Integer.MIN_VALUE) {
            if (divisor == -1) {
                return Integer.MAX_VALUE;
            }
            else if (divisor == 1) {
                return Integer.MIN_VALUE;
            }
        }
        
        if (dividend == Integer.MAX_VALUE) {
            if (divisor == -1) {
                return 0 - Integer.MAX_VALUE;
            }
            else if (divisor == 1) {
                return Integer.MAX_VALUE;
            }
        } 
        
        long dividend1 = java.lang.Math.abs(Long.valueOf(String.valueOf(dividend)));
        long divisor1 = java.lang.Math.abs(Long.valueOf(String.valueOf(divisor)));
        
        long result = 0;
        while (dividend1 >= divisor1) {
            dividend1 -= divisor1;
            ++result;
        }
        
        if (result > Integer.MAX_VALUE || result < Integer.MIN_VALUE) {
            return Integer.MAX_VALUE;
        }
        
        if (adjust) {
            return 0 - (int)result;
        }
        
        return (int)result;
    }
}

要点
当前给出的实现仅能满足功能,无法满足题目对性能的要求。但受限于当前的工作状态,没有太多时间投入,因此暂时先做到这个程度。

准备的用例,如下

    @Test
    public void test01() {
        
        assertEquals(0, new L29().divide(0, 3));
        assertEquals(0, new L29().divide(0, -3));
        
        assertEquals(3, new L29().divide(10, 3));
        assertEquals(-2, new L29().divide(7, -3));
        assertEquals(-2, new L29().divide(-7, 3));
        
        assertEquals(Integer.MAX_VALUE, new L29().divide(Integer.MIN_VALUE, -1));
        assertEquals(Integer.MIN_VALUE, new L29().divide(Integer.MIN_VALUE, 1));
        
        assertEquals(Integer.MIN_VALUE + 1, new L29().divide(Integer.MAX_VALUE, -1));
        assertEquals(Integer.MAX_VALUE, new L29().divide(Integer.MAX_VALUE, 1));
        
        assertEquals(1, new L29().divide(Integer.MAX_VALUE, Integer.MAX_VALUE));
        assertEquals(1, new L29().divide(Integer.MIN_VALUE, Integer.MIN_VALUE));
        
        assertEquals(-1073741824, new L29().divide(-2147483648, 2));
        assertEquals(1073741824, new L29().divide(-2147483648, -2));
        
        assertEquals(715827882, new L29().divide(-2147483648, -3));
    }


若非注明,均为原创,欢迎转载,转载请注明来源:LeetCode第29题 – 两数相除

关于 JackieAtHome

基层程序员,八年之后重新启航

此条目发表在 Java, LeetCode 分类目录。将固定链接加入收藏夹。