LeetCode29-两数相除

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/divide-two-integers/

中文链接：https://leetcode-cn.com/problems/divide-two-integers/

题目详述

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

示例 1:

1
2
输入: dividend = 10, divisor = 3
输出: 3

示例 2:

1
2
输入: dividend = 7, divisor = -3
输出: -2

说明:

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

题目详解

  • 本题看起来简单，实际上写起来很容易出错。
  • 由于不允许使用乘法、除法和取模运算，那么只能采用加减法运算和位运算。
  • 首先可以想到把两个数变为正数，然后通过减法来得到结果，最后判别一下符号。并且我们可以找到最大的减数然后逐步递减将时间复杂度从 O(n) 降为 O(logn)。但题目限制了环境只能存储 32 位有符号整数，其数值范围是 [−2^31, 2^31 − 1]，当被减数为 −2^31时，在这个环境下不能转换为对应的正数（如果没有这个条件可以使用 64 位的 long），所以这种方法行不通。
  • 换一种思路，既然存在负数不能转换为正数，那么能否把正数转换为负数转换位负数？显然可行，32 位有符号环境下，正数能得到对应的负数。接下来的思路同上，依旧是做减法，直至被减数小于减数。同样可以把时间复杂度从 O(n) 降为 O(logn)。
  • 特别要注意一些边界条件的判断。
  • 时间复杂度为 O(logn)，n 为被除数的绝对值，不超过 32。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class LeetCode_00029 {

    public int divide(int dividend, int divisor) {
        if (dividend == 0 || divisor == 1) {
            return dividend;
        }
        if (divisor == -1) {
            return dividend == Integer.MIN_VALUE ? Integer.MAX_VALUE : -dividend;
        }
        int x = -Math.abs(dividend), y = -Math.abs(divisor);
        int p = 1;
        while (y << 1 < 0 && y << 1 >= x) {
            y <<= 1;
            p <<= 1;
        }
        int res = 0;
        while (p >= 1) {
            if (x <= y) {
                x -= y;
                res += p;
            }
            y >>= 1;
            p >>= 1;
        }
        return dividend > 0 ^ divisor > 0 ? -res : res;
    }
}