乐趣区

关于java:leetcode-29-两数相除中等

题目形容

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

返回被除数 dividend 除以除数 divisor 失去的商。

整数除法的后果该当截去(truncate)其小数局部,例如:truncate(8.345) = 8 以及 truncate(-2.7335) = -2

示例 1:
输出: dividend = 10, divisor = 3
输入: 3
解释: 10/3 = truncate(3.33333..) = truncate(3) = 3

示例 2:
输出: dividend = 7, divisor = -3
输入: -2
解释: 7/-3 = truncate(-2.33333..) = -2

解题思路

首先要思考到数字的正负问题,如果 除数 被除数 都为负数或者都为正数,后果也是负数,否则为正数。应用 sign 标记正负,而后将 除数 被除数 都转成负数:

int sign = 1;
if ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0)) {sign = -1;}
int dividends = Math.abs(dividend);
int divisors = Math.abs(divisor);

要求不能应用乘法、除法和取余运算,算出两数相除的值,后果值取整。波及到运算,那就得应用到别的运算符,比方加法。比方 10/3 转成 10 始终减 3, 直到被减的数小于被除数。

10 - 3 = 7 
7 -3 = 4 
4 - 3 = 1 < 3 

下面一共减了三次,所以 10/3 = 3,依据思路写出上面代码:

public int divide(int dividend, int divisor) {
        int sign = 1;
        if ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0)) {sign = -1;}
        int dividends = Math.abs(dividend);
        int divisors = Math.abs(divisor);
        int index = 0;
        while (dividends >= divisors) {
            dividends = dividends - divisors;
            index++;
        }

        return index * sign;
    }

后果:

这里波及到数字范畴的问题,咱们发现 -2147483648,取相反数还是 -2147483648,这是因为编码 int 占四个字节,一个字节八个位。

所以须要应用转成 long 类型,防止数据越界问题:

 int sign = 1;
        if ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0)) {sign = -1;}
        long dividends = Math.abs((long) dividend);
        long divisors = Math.abs((long) divisor);
        long index = 0;
        while (dividends >= divisors) {
            dividends = dividends - divisors;
            index++;
        }
        if (index > Integer.MAX_VALUE && sign == 1) {return Integer.MAX_VALUE * sign;}
        return (int) index * sign;

后果:

后果超时,是因为一个个减,是须要反复次数,工夫复杂度是 O(n)。

这里须要应用 递进式 的减法,比方

10/1 = 10
10 - 1 = 9   index = 1
9 - 1 = 8   index = 2
8 - 1 = 7   index = 3
7 - 1 = 6   index = 4
6 - 1 = 5   index = 5
....
1 - 1 = 0   index = 10

这下面是要进行十步操作,须要做的一个递进的操作,被除数做加倍,比方下面能够转成:

10 - 1= 9          index = 1 = 1
9 - 1*2 = 7        index = 1 + 1*2 = 3
7 - 1*2*2 =  3    index = 1 + 1*2 + 1 *2*2 = 7

再匹配 3 - 1*2*2*2 < 0, 还须要再进行下面的减操作
3 - 1 = 2          index = 7 + 1 = 8
2 - 1*2 = 0       index = 7 + 1 + 1* 2 = 10

具体流程:

依据以上思路可得如下代码:

int sign = 1;
        if ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0)) {sign = -1;}
        long dividends = Math.abs((long) dividend);
        long divisors = Math.abs((long) divisor);
        long index = 0;
        while (dividends >= divisors) {
            long temp = divisors;
            long i = 1;
            while (dividends >= temp) {
                dividends = dividends - temp;
                index = index + i;
                temp = temp << 1;
                i = i << 1;
            }
        }
        if (index > Integer.MAX_VALUE && sign == 1) {return Integer.MAX_VALUE * sign;}
        return (int) index * sign;

总结

  • 此题解法开始想到将除法转成减法,一个一个累计减
  • 须要思考 int 范畴溢出问题,这里对立换成 long 类型
  • 累减须要的工夫负复杂度是 O(n), 容易超时,这里须要转成递进减法,即每次都对被减数 加倍

如果感觉文章对你有帮忙的话,请点个赞吧!

退出移动版