leetcode29.两数相除（中等）

本文主要是介绍leetcode29.两数相除（中等），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

思路：二分
乘法：用快速乘来替代。
除法：除以2用>>1来替代
mod：用不到
注意：（dividend / intdivisor）
1：如果除法结果溢出，那么需要返回 2^31-1作为答案。因此在编码之前，我们可以首先对于溢出或者容易出错的边界情况进行讨论：
dividend讨论：
（1）INT_MIN : 1 （ans越界：return INT_MIN） -1(最终结果越界：return INT_MAX)
（2）0 : return 0
2:对于一般的情况，根据除数和被除数的符号，需要考虑 4种不同的可能性。因此，为了方便编码，我们可以将被除数或者除数取相反数，使得它们符号相同。如果我们将被除数和除数都变为正数，那么可能会导致溢出。例如当被除数为 -2^31,它的相反数产生了溢出。因此可以考虑将被除数和除数都变为负数，这样就不会有溢出的问题，在编码时只需要考虑1种情况了。
3：二分来源（x y为负数 ，z为正数，z的取值范围为：1到INT_MAX）
x/y==z 转化为：yz>=x>(z+1)y， 问题转化为找最大的z，满足yz大于等于x！！！因此可以用二分。
4：我自己二分的写法习惯用（）两个开区间来写，所以，看一下边界，发现INT_MAX得单独考虑下
dividend为INT_MAX : 1（return INT_MAX） -1（return -INT_MAX）
这样二分时右边界初始化可以初始为INT_MAX。

class Solution {
public:
	//m*n大于等于a的话return true 否则false，n是正数
    bool fast_cheng(int m, int n, int a) { 
        int ans = 0;
        while (n) {
            if (n & 1) {
                if (ans < a - m) return false; //ans+m<a转换下，因为m为负数，ans+m可能会越界！！！
                //上面，因为m是负数，所以ans若已经小于a，则直接返回false！！！
                ans += m; //上面先判断再+=，怕ans+m越界！！！
            }
            if(n != 1) {
                if (m < a - m) return false; //若更新后的m已经小于a，说明m*n肯定小于a，返回false！！！
                m += m; //-2147483648 + -2147483648会越界,m+m应该大于a，小于直接return false!!!
            }
            n >>= 1;
        }
        return true; 
    }
    int divide(int dividend, int divisor) {
       
        if (dividend == INT_MIN) {
            if (divisor == 1) return INT_MIN;
            if (divisor == -1) return INT_MAX;
        }
        if (dividend == INT_MAX) {
            if (divisor == 1) return INT_MAX;
            if (divisor == -1) return -INT_MAX;
        }
        if (dividend == 0) return 0;
        bool flag = true;
        if (dividend > 0) { 
            dividend = -dividend;
            flag = !flag;
        }
        if (divisor > 0) {
            divisor = -divisor;
            flag = !flag;
        }
        int l = 0, r = INT_MAX;
        while (l + 1 < r) {
            int mid = l + ((r - l) >> 1); //
            if (fast_cheng(divisor, mid, dividend)) l = mid; //乘法->快速乘
            else r = mid;
        }
        return (flag) ? l : -l;
    }
};

易错点：
1：由于判断mid * divisor >= dividend，使用快速乘时要对mid进行移位，因为mid是正数，不能搞错了。
2：使用二分求mid时，/2可以用>>1来写。
3：易错点已经在上面的代码中注释。

这篇关于leetcode29.两数相除（中等）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！