[数据结构与算法]LeetCode--29.两数相除

题目

题解

1、采用直接想减的方式进行处理

//直接相减,在leetCde中无法提交，提示超时
    public static int divide(int dividend, int divisor){
        int quotient = 0;
        boolean postiveNumber = true;
        if((dividend>0 && divisor<0) ||  (dividend<0 && divisor>0)){
            postiveNumber = false;
        }
        long absDividend = Math.abs((long)dividend);
        long absDivisor = Math.abs((long)divisor);
        while(absDividend >= absDivisor){
            absDividend -= absDivisor;
            quotient++;
            if(quotient >= Integer.MAX_VALUE){
                return Integer.MAX_VALUE;
            }
        }
        if(!postiveNumber){
            return -quotient;
        }
        return  quotient;
    }

2、使用移位运算实现计算

public static int divide1(int dividend, int divisor){
        //存放商数
        long quotient = 0;
        //返回结果值
        int result = 0;
        //判断返回结果是+/-
        boolean postiveNumber = true;
        //两种情况返回结果为-
        if((dividend>0 && divisor<0) ||  (dividend<0 && divisor>0)){
            postiveNumber = false;
        }
        //将除数和被除数进行取绝对值，转为long型防止-2^31绝对值后变为0.
        long absDividend = Math.abs((long)dividend);
        long absDivisor = Math.abs((long)divisor);
        //如果被除数小于除数，返回结果为0.
        if(absDividend<absDivisor) return 0;
        /**
         *该方法类似递归，当被除数大于等于除数时，将一直调用移位算法进行计算。
         * 当移位算法满足条件后，用被除数-移位算法的除数最大值，下一次调用移位算法时，使用差值作为被除数，并且每次的移位值进行累加。
         * 当最后一次被除数和除数相等时，商数最后加1，得到商值。
         */
        while (absDividend >= absDivisor) {
            long tmp = absDivisor,tempQuotient=1 ;
            /**
             * 当被除数大于等于临时除数移位后的值时，对临时除数和临时商数进行移位。
             */
            while(absDividend >= tmp<<1){
                tmp<<=1;
                tempQuotient<<=1;
            }
            absDividend -= tmp;
            quotient += tempQuotient;

        }
        /**
         * 商值使用long存储，当商值>int类型的最大值，返回商值最大值。
         * 由于int类型的除法出现最大值的情况有以下两种：
         * 1、-2147483648 / 1 = -2147483648 不需要取最大值，最后的计算结果正确。
         * 2、-2147483648 / -1 = 2147483648 需要取int类型的最大值。
         */
        return result = postiveNumber? quotient>Integer.MAX_VALUE ? Integer.MAX_VALUE : (int)quotient : (int)-quotient;
    }