首页 > 代码库 > [LeetCode]29.Divide Two Integers

[LeetCode]29.Divide Two Integers

【题目】

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

【分析】

不能用乘除和取模,就只能用加减和位运算。

最简单的方法就是不断的减去被除数。这种方法的迭代次数是结果的大小,即比如结果为n,算法复杂度是O(n)。但是这样会超时。

【代码】

/*********************************
*   日期:2015-01-24
*   作者:SJF0115
*   题目: 29.Divide Two Integers
*   网址:https://oj.leetcode.com/problems/divide-two-integers/
*   结果:AC
*   来源:Time Limit Exceeded
*   博客:
**********************************/
#include <iostream>
using namespace std;

class Solution {
public:
    int divide(int dividend, int divisor) {
        // 当dividend=INt_MAX时,-dividend会溢出,用long long
        long long a = dividend >= 0 ? dividend : -(long long)dividend;
        // divisor=INt_MAX时,-divisor,用long long
        long long b = divisor >= 0 ? divisor : -(long long)divisor;
        int count = 0;
        // 不断减
        while(a >= b){
            a -= b;
            count ++;
        }//while
        // 正负
        int isPositive = (dividend ^ divisor) >> 31;
        if(isPositive == 0){
            return count;
        }//if
        else{
            return -count;
        }//else
    }
};

int main(){
    Solution solution;
    int dividend = -2147483648;
    int divisor = -1;
    int result = solution.divide(dividend,divisor);
    // 输出
    cout<<result<<endl;
    return 0;
}


技术分享

【分析二】

通过上面超时的例子可以总结出一点东西,做一些优化。

利用位运算每次把被除数翻倍,从而加速。

【代码二】

/*********************************
*   日期:2015-01-25
*   作者:SJF0115
*   题目: 29.Divide Two Integers
*   网址:https://oj.leetcode.com/problems/divide-two-integers/
*   结果:AC
*   来源:Time Limit Exceeded
*   博客:
**********************************/
#include <iostream>
#include <climits>
using namespace std;

class Solution {
public:
    int divide(int dividend, int divisor) {
        // 当dividend=INt_MAX时,-dividend会溢出,用long long
        long long a = dividend >= 0 ? dividend : -(long long)dividend;
        // 当divisor=INt_MAX时,-divisor会溢出,用long long
        long long b = divisor >= 0 ? divisor : -(long long)divisor;
        long long result = 0;
        // 不断减
        while(a >= b){
            long long c = b;
            for(int i = 0;a >= c;++i,c <<= 1){
                a -= c;
                result += 1 << i;
            }//for
        }//while
        // 正负
        if((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0)){
            result = -result;
        }//if
        // If it is overflow, return MAX_INT.
        if (result > INT_MAX || result < INT_MIN){
            result = INT_MAX;
        }
        return static_cast<int>(result);
    }
};

int main(){
    Solution solution;
    int dividend = -2147483648;
    int divisor = -1;
    int result = solution.divide(dividend,divisor);
    // 输出
    cout<<result<<endl;
    return 0;
}


之前忽略一个细节:If it is overflow, return MAX_INT.

技术分享

2147483648 overflow 所以返回MAX_INT    2147483647



技术分享


[LeetCode]29.Divide Two Integers