每周一道算法题(二十四)

本周的题目难度级别'Medium'

题目:本周的题目又是一道造轮子的题，就是不用‘*’和‘/’来实现除法。

思路：a/b = c,c可以写成二进制，即2⁰⁺²1+...+2^n，根据这个公式，来实现此题，下面看看代码：

int divide(int dividend, int divisor) {
    if (dividend == 0) return 0;
    //i和j是用来实现循环的，flag是判断正负符号
    int i=0,j,flag=0;
    //result是商，a,b是新的除数和被除数，map和times作为2进制存储的容器，容器33是因为int类型总长度是2^32,0〜32是33个数
    long long result=0,a,b,map[33],times[33];
    //判断正负
    if((dividend>0 && divisor>0) || (dividend<0 && divisor<0))flag=1;
    //转为正整数
    a=(long long)dividend > 0?(long long)dividend:-(long long)dividend;
    //转为正整数
    b=(long long)divisor>0 ?(long long)divisor:-(long long)divisor;
    //map从b开始，times从2^0开始
    map[0]=b;times[0]=1;
    //先展开
    while(map[i] <= a && i<33){
        i++;
        map[i]=map[i-1]+map[i-1];
        times[i]=times[i-1]+times[i-1];
    }
    //统计结果
    for(j=i-1;j>=0;j--){
        while(a >= map[j]){
            a-=map[j];
            result+=times[j];
        }
    }
    //加上符号
    result=flag?result:-result;
    //判断是否越界
    if(result<INT_MIN || result > INT_MAX)return INT_MAX;
    return (int)result;
}

以上代码效率一般，也有别的思路，比如位操作、迭代等方法效率更好，有兴趣的小伙伴可以自己学习，另外，我们也能看出实现除法也并不是很容易(毕竟难度级别Medium)，我记得上学的时候老师也说过能写乘法就别也除法，我也在我的代码中能口算的除法直接写成乘法了，比如除以2就写成乘以0.5。。。Y(^_^)Y（用Markdown打表情还需要技巧）

版权声明：本文为 Crazy Steven 原创出品，欢迎转载，转载时请注明出处!