两数相除

发表于
本文字数： 1.5k 阅读时长 ≈ 1 分钟

LeetCode题目，29. Divide Tow Integers

先看题目描述

slmF3D.png

大意就是给定两个数，让我们返回这两个数相除的结果，要求不能使用乘法，除法和 mod 运算，计算处理的数据范围是 32 位有符号整数，若溢出的话，则则返回该范围内的最大值

算法和思路

这题不会，看了题解才会

以 60 / 8 为例，60 / 8 = (60 - 32) / 8 + 4 = (60 - 32 - 16) / 8 + 4 + 2 = (60 - 32 - 16 - 8) / 8 + 4 + 2 + 1 = 0 + 4 + 2 + 1 = 7

我们就用代码模拟该过程即可，注意当 dividend 为 Integer.MIN_VALUE 且 divisor 为 -1 时，结果会溢出，直接返回 Integer.MAX_VALUE 即可；还有计算时我们要先将被除数和除数都转化为正数或负数来进行计算，最后为结果加上符号，为了防止将被除数和除数转化时发生溢出，我们将它们都转化为负数

具体看下面代码吧

算法源码

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
28
29
30
31
32
33
class Solution {
    public int divide(int dividend, int divisor) {
        if (divisor == 1) return dividend;
        if (divisor == -1) {
            if (dividend == Integer.MIN_VALUE) {
                return Integer.MAX_VALUE;
            } else {
                return -dividend;
            }
        }
        int sigh = 1;
        if (dividend > 0 && divisor < 0 || dividend < 0 && divisor > 0) {
            sigh = -1;
        }
        dividend = dividend < 0 ? dividend : -dividend;
        divisor = divisor < 0 ? divisor : -divisor;
        return sigh * div(dividend, divisor);
    }

    private int div(int a, int b) {
        if (a > b) {
            return 0;
        }
        int tb = b;
        int count = 1;
        // 溢出之后不再小于 0
        while ((tb + tb) >= a && (tb + tb) < 0) {
            count += count;
            tb += tb;
        }
        return count + div(a - tb, b);
    }
}

注意：在 div 函数中也要检查溢出