[力扣][C++]29. 两数相除

typedef long long ll;
class Solution {
public:
    int divide(int dividend, int divisor) {
        if(!dividend) return 0;
        bool sgn = dividend > 0 && divisor < 0 || dividend < 0 && divisor > 0;
        vector A;
        ll a = abs((ll)dividend);
        ll b = abs((ll)divisor);
        for(ll i = b;i <= a;i += i)
            A.push_back(i);
        ll res = 0;
        for(int i = A.size() - 1;i >= 0;i--)
            if(A[i] <= a){
                res += 1ll << i;
                a -= A[i];
            }
        if(sgn) res = -res;
        if(res > INT_MAX || res < INT_MIN) return INT_MAX;
        return res;
    }
};

typedef long long ll;
class Solution {
public:
    int divide(int dividend, int divisor) {
        if(dividend == 0) return 0;
        bool sgn = (dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0);
        ll a = abs((ll)dividend);
        ll b = abs((ll)divisor);
        ll res = 0;
        for(ll t = a;t >= b;t -= b){
            res ++;
        }
        if(res > INT_MAX || res < INT_MIN) return INT_MAX;
        return sgn ? (int)-res:(int)res;
    }
};

本题要求不用乘除和取模运算完成整数除法，我们可以使用加减法进行计算，如朴素代码所示。
然而这样的时间复杂度为 O ( n ) O(n) O(n)，相对于整型的数据范围来说，复杂度过高。

因此我们应该寻找 O ( l o g 2 n ) O(log_2n) O(log2​n)级别的算法。
这里可以使用类似于多重背包问题优化的思路——即“打包”的思想进行优化。

d i v i d e n d = d i v i s o r ∗ k + r ( r < d i v i s o r ) dividend = divisor * k + r(r < divisor) dividend=divisor∗k+r(r 令 k = k 1 + k 2 + k 3 + . . . + k n （ 0 = < k i < = k , k i < k i + 1 ） 令k = k_1 + k_2 + k_3+...+k_n（0= 则 d i v i d e n d = d i v i s o r ∗ k 1 + d i v i s o r ∗ k 2 + d i v i s o r ∗ k 3 + . . . + d i v i s o r ∗ k n + r 则dividend = divisor * k_1 + divisor*k_2 + divisor*k_3+...+divisor*k_n + r 则dividend=divisor∗k1​+divisor∗k2​+divisor∗k3​+...+divisor∗kn​+r
而这里对于k的拆分方法，我们同样可以参考多重背包问题的方法，即使用位运算。
代码如AC代码所示。

题目链接
原创不易，感谢支持！