LeetCode 29 Divide Two Integers

Tag: LeetCode 二分搜索  Posted on 2020-06-07 11:44:34 Edited on 2020-06-07 11:46:56

分析

题目要求不能使用乘法,除法以及取模,而且限制了整型的范围:[-2^31, 2^31-1]。

考虑到除数和被除数的符号可能不一致,为了方便后续处理,我们先统一符号,并使用一个布尔值记录结果的正负形。

一般我们都会考虑将其都转化为正数,但在这里,变成正数会有溢出的问题,原因就在于在题目要求的整型范围内正数的数量比负数的数量少一。

之后,如何在只使用加减法的情况下求出商呢? 我们可以考虑每次对被除数减去一定数量的除数,循环进行,直到不能再减去, 然后把我们减去的除数的总的数量加起来即结果(当然还要考虑我们之前确定的正负问题)。

暴力方法是每次减去一个,易于理解实现但是会超时。

我们可以考虑每次减去 i 个,如果可以减去的话下次减去 2*i 个,如果不行的话,我们就把被除数减去当前已减去的部分作为新的被除数,递归下去。

基础情况显然是被除数小于除数,此时返回 0 即可。

代码

class Solution {
public:
    int divide(int dividend, int divisor) {
        bool negative = (dividend > 0) ^ (divisor > 0); // ^ 在 C++ 中为异或运算
        if(dividend == INT_MIN && divisor == -1) return INT_MAX; // The only case the result will overfolw
        if(dividend > 0) dividend = -dividend; // Turn it into negative beacuse negative part is larger
        if(divisor > 0) divisor = -divisor; // Same as above
        int mul = divideHelper(dividend, divisor);
        return negative ? mul : -mul;
    }

private:
    int divideHelper(int dividend, int divisor) {
        if(dividend > divisor) return 0; // why '>' ? Because they are negative.
        int mul = -1;
        int sum = divisor;
        while(sum >= dividend - sum) { // 就是 2*sum >= dividend,考虑到 2*sum 会溢出,因此就把其转换一下
            mul += mul;
            sum += sum;
            if(sum > 0) break; // Consider the overflow, sum is smaller than dividend if it turns positive
        }
        return mul + divideHelper(dividend-sum, divisor);
    }
};