快速幂

由x/y = k ,我们不难想到除法的本质：x -y - y - y - y .....= 余数，其中减了k次y，如果极端的情况x为int的最大值，y为1，则会减$10^9$次，超时。

而我们利用快速幂的思想

$ x/y = k $ ，将k看成二进制表示，并且将y移到右边，则有

$ x = y * k $

$ x = y * (2^1 + 2^3 + … + 2 ^i)$

$ x = y * 2^1 + y * 2^3 + … + 2^i $

1.确定最终符号

2.先预处理出来$ 2^i*y$ .

3.从后往前遍历预处理的数组，如果$ x >= 2^i * y$ 则说明x的i位是1,x减$ 去2^i * y$ ,答案加上2的i次方。

• 否则$ x < 2^i * y$ 则说明x的i位是0，不做任何事。

$ 时间复杂度O(logN) , 空间复杂度O(logN)$

参考文献

lc究极班

AC代码

class Solution {
public:
    int divide(int _x, int _y) {
        typedef long long LL;
        //记录答案的符号
        bool is_minus = false;
        if (_x < 0 && _y > 0 || _x > 0 && _y < 0) is_minus = true;
        LL x = abs(LL(_x)) , y = abs(LL(_y));
        //预处理y*(2的i次方)
        vector<LL> q;
        for (LL i = y ; i <= x ; i = i + i){
            q.push_back(i);
        }
        //计算答案
        LL res = 0;
        for (int i = q.size() - 1; i >= 0 ; i --){
            if (x >= q[i]) {
                x -= q[i];
                res += 1ll << i;
            }
        }
        if (is_minus) res = -res;

        if (res < INT_MIN || res > INT_MAX) return INT_MAX;
        return res;
    }
};