[数据结构与算法]Leetcode--Java--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
 

提示：

被除数和除数均为 32 位有符号整数。
除数不为 0。
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [?231,  231 ? 1]。本题中，如果除法结果溢出，则返回 231 ? 1。

思路

1. 快速幂（倍乘）思想
   
   先预处理，
   
   判断，是否大于等于
   
2. 如果是大于等于，就每次减去2的k次方，然后商的部分加上这个数。
3. 负数的情况，直接取绝对值，最后改成相反数即可
   
4. 注意去绝对值，移位都要强转为long，结果res也要先用long，都是为了放置溢出

代码

class Solution {
    public int divide(int dividend, int divisor) {
       List<Long> powers = new ArrayList<>();
       boolean isMinus = false;
       if (dividend > 0 && divisor < 0 || dividend < 0 && divisor > 0)
       isMinus = true;
       //先转为long  防止取绝对值时溢出
       long a = Math.abs((long)dividend), b = Math.abs((long)divisor);
       //预处理  先计算2^0一直到2^31 
       for (long i = b; i <= a; i = i + i) {
           powers.add(i);
       }
       long res = 0;  //防溢出 先用long
       //相除
       for (int i = powers.size() - 1; i >= 0; i -- ) {
           if (a >= powers.get(i)) {
               a -= powers.get(i);
               //1左移  要先强转为long 避免溢出
               res += (long)1 << i;
           }
       }
       if (isMinus) res = -res;
       //溢出的话
       if (res > Integer.MAX_VALUE || res < Integer.MIN_VALUE) 
       res = Integer.MAX_VALUE;
       return (int)res;
    }
}