LeetCode第29题两数相除

继续打卡算法题，今天学习的是LeetCode的第29题两数相除，这道题目是道中等题。算法题的一些解题思路和技巧真的非常巧妙，每天看一看算法题和解题思路，我相信对我们的编码思维和编码能力有一些提升。

分析一波题目

这道题其实挺有意思的，两数相除不适用除法，乘法，取余。

那么我们只能使用加法，减法，二进制位移法了。

如果使用位移法，我们可以将除数不断的左位移，进行双倍扩容增长，同时记录扩容次数，如果扩容后的值大于被除数，说明到达了除数接近的值，这样不是每次增加除数。

同时本题需要考虑整数越界的情况。我们可以将被除数和除数统一转换成long类型防止溢出。

编码解决

class Solution {
   
   
    public int divide(int dividend, int divisor) {
   
   

        // 当除数为1，直接返回被除数
        if (divisor == 1) {
   
   
            return dividend;
        }
        // 当除数为-1且被除数为Integer.MIN_VALUE时，将会溢出，返回Integer.MAX_VALUE
        if (divisor == -1 && dividend == Integer.MIN_VALUE) {
   
   
            return Integer.MAX_VALUE;
        }

        // 把被除数与除数调整为正数,为防止被除数Integer.MIN_VALUE转换为正数会溢出，使用long类型保存参数
        if (dividend < 0 && divisor < 0) {
   
   
            return divide(-(long) dividend, -(long) divisor);
        } else if (dividend < 0 || divisor < 0) {
   
   
        //虽然有负数，统一转换成正数
            return -divide(Math.abs((long) dividend), Math.abs((long) divisor));
        } else {
   
   
            return divide((long) dividend, (long) divisor);
        }
    }

    public int divide(long dividend, long divisor) {
   
   
        // 如果被除数小于除数，结果明显为0
        if (dividend < divisor) {
   
   
            return 0;
        }
        long sum = divisor; // 记录用了count个divisor的和
        int count = 1; // 使用了多少个divisor
        while (dividend >= sum) {
   
   
            // 每次翻倍 左移就是相乘
            sum <<= 1;
            //计数也翻倍
            count <<= 1;
        }

        // 此时dividend < sum
        sum >>>= 1; //扩容的除数，需要回退1位
        count >>>= 1; //计数也需要回退1位
        // 此时dividend >= sum
        // 将count个divisor从dividend消耗掉，剩下的还需要多少个divisor交由递归函数处理
        return count + divide(dividend - sum, divisor);
    }
}

总结

这个题目有两个技巧可以运用到其他问题上：

• 防止整数溢出，将数转换成long类型
• 在某些场景下，如果不能使用乘除运算的时候，我们可以想到使用二进制形式位移运算

一个数左移1位就是乘以2，左移n位就是乘以2的n次方，左移运算效率比乘法效率高

一个数右移1位就是除以2，右移n位就是除以2的n次方，当得到的商不是整数时会往小取整