[leetcode javascript解题]Divide Two Integers

柔光的暖阳◎ 2022-07-13 03:48 111阅读 0赞

leetcode第29题，“Divide Two Integers” 的描述如下：

> Divide two integers without using multiplication, division and mod operator.  
> If it is overflow, return MAX\_INT.

题目就是要大家不使用乘除法和模运算来实现除法。同时要考虑边界条件。  
这道题在leetcode上的ac率非常低，其实总的来说，出思路并不是特别的难，难就难在思路的整合以及边界条件的处理。  
首先为了方便运算，当然是将传入的数值使用绝对值转换为了正整数，接着先判断为0的特殊条件，然后使用一个变量flag来正负值(其实)。我的处理方式代码里面可以看到，有很多人可能想着哪需要这么麻烦，直接两数相乘看符号就行了，可是。。拜托，人家明明说了不允许使用乘法。  
到算法核心部分，当被除数还比除数大，就继续执行内层循环，使用一个临时变量来储存除数，使用左移运算来减少运算次数，需要注意的是内层循环的判断条件应该是，被除数是否大于当前这个临时除数的两倍，因为每次进入循环是除数是需要再乘2的。  
如果给的数太大，左移会出现超出位数，符号位变化，变为负值（1073741824<<1=-2147483648），所以添加判断条件，直接跳出当前循环。同样，当内层计数变量i超出边界也就意味着结果肯定超出数边界了，直接返回。之所以不在得到结果后再处理，是为了避免循环次数过多，TIME LIMIT EXCEEDED。

/** * @param {number} dividend * @param {number} divisor * @return {number} */
    var divide = function(dividend, divisor) {
        var MAX_INT = Math.pow(2, 31) - 1,
            MIN_INT = -Math.pow(2, 31),
            result = 0,
            newDividend = Math.abs(dividend),
            newDivisor = Math.abs(divisor),
            flag;
        if (newDividend < newDivisor) {
            return 0;
        }
        if (dividend >= 0 && divisor > 0 || dividend <= 0 && divisor < 0) {
            flag = 1;
        } else {
            flag = -1;
        }
        while (newDividend >= newDivisor) {
            var temp = newDivisor,
                i = 0;
            while (newDividend >= temp << 1) {
                if ((temp << 1) <= 0) {
                    break;
                }
                temp = temp << 1;
                i++;
                if (flag > 0 && i > 29) {
                    return MAX_INT;
                }
                if (flag < 0 && i > 30) {
                    return MIN_INT;
                }
            }
            newDividend -= temp;
            result += Math.pow(2, i);
        }
        if (flag > 0) {
            return result;
        } else {
            return -result;
        }
    };