【刷题记录】29. 两数相除

一、题目描述

来源：力扣（LeetCode）

给定两个整数，被除数 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 位有符号整数，其数值范围是 [
  网络异常，图片无法展示

  |
  ,  
  网络异常，图片无法展示

  |
  ]。本题中，如果除法结果溢出，则返回  
  网络异常，图片无法展示

  |
  。

二丶思路分析

倍增 + 二分查找

题目要求 不使用乘法、除法和 mod 运算符

• 如果被除数为X，除数为 Y ,结果为Z，那么肯定满足：

• 不能使用乘法运算符，我们需要使用快速乘算法得到
  网络异常，图片无法展示

  |
  的值
• 为了避免，计算过程中 被除数 和除数 符号不一致，我们处理时候，当两数统一转化为正数或者负数
• 注意边界和溢出问题

三、代码实现

class Solution {
    public static int divide(int dividend, int divisor) {
        long result =0;
        long x = dividend;
        long y = divisor;
        // 考虑被除数为最小值的情况
if (dividend == Integer.MIN_VALUE) {
if (divisor ==1) {
                return Integer.MIN_VALUE;
            }
if (divisor ==-1) {
                return Integer.MAX_VALUE;
            }
        }
        // 考虑除数为最小值的情况
if (divisor == Integer.MIN_VALUE) {
            return dividend == Integer.MIN_VALUE ? 1 : 0;
        }
        // 考虑被除数为 0 的情况
if (dividend ==0) {
            return 0;
        }
        boolean flag = (x < 0 && y > 0) || (x > 0 && y < 0);
        //将所有的负数变成正数，考虑一种情况
if (x < 0) {
            x =-x;
        }
if (y < 0) {
            y =-y;
        }
        // 一半情况 二分
        long left =0;
        long right = x;
while (left < right) {
            long mid = left + right +1 >> 1;
            long  quicknum = quickAdd(mid, y);
if (quicknum <= x) {
                // 相乘结果不大于x，左指针右移
                left = mid;
            } else {
                right = mid -1;
            }
        }
        result = flag ? -left : left;
        // 判断是否溢出
if (result < Integer.MIN_VALUE || result > Integer.MAX_VALUE) {
            return Integer.MAX_VALUE;
        }
        return (int)result;
    }
    public static long quickAdd(long a, long b) {
        long result =0;
while (b > 0) {
if ((b & 1) ==1) {
                // 当前最低位为1，结果里加上a
                result += a;
            }
            // 被乘数右移1位，相当于除以2
            b >>=1;
            // 乘数倍增，相当于乘以2
            a += a;
        }
        return result;
    }
}

复杂度分析

• 时间复杂度：
  网络异常，图片无法展示

  |
• 空间复杂度：
  网络异常，图片无法展示

  |

运行结果

总结

这个题目主要在于

1. 将问题转化为对结果的二分查找过程。

1. 在不能使用 乘法、除法和 mod的时候 通过倍增的思想来实现一个快速乘法。
   多学习和熟悉一些模板函数的书写和使用，如使用到的 二分，快速乘法等等。这些常用的模板函数，可以帮助我们更快更好的去解决问题。

继续加油~~