首页 > 其他 > 详细

LeetCode-29-Divide Two Integers

时间:2019-01-28 20:52:21      阅读:143      评论:0      收藏:0      [点我收藏+]

算法描述:

Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.

Return the quotient after dividing dividend by divisor.

The integer division should truncate toward zero.

Example 1:

Input: dividend = 10, divisor = 3
Output: 3

Example 2:

Input: dividend = 7, divisor = -3
Output: -2

Note:

  • Both dividend and divisor will be 32-bit signed integers.
  • The divisor will never be 0.
  • Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [?231,  231 ? 1]. For the purpose of this problem, assume that your function returns 231 ? 1 when the division result overflows.

解题思路:用加法或者向左移动实现乘法或者除法。这道题需要考虑的细节比较多。1 为避免溢出,采用长整型。2 长整型的绝对值函数为labs(long long a, long long b),3 考虑特殊溢出情况。

    int divide(int dividend, int divisor) {
        if(!divisor || (divisor==-1 && dividend == INT_MIN)) return INT_MAX;
        long long ldd = labs(dividend);
        long long ldv = labs(divisor);
        int res = 0;
        res = divideLong(ldd, ldv);
        if((dividend < 0 && divisor > 0 ) || (dividend > 0 && divisor < 0)) return -(int)res;
        else return (int)res;
    }
    
    long long divideLong(long long ldd, long long ldv){
        if(ldd < ldv) return 0; 
        long long sum = ldv;
        long long res = 1;
        while((sum + sum) <= ldd){
            sum += sum;
            res += res;
        }
        return res + divideLong(ldd-sum, ldv);
    }

 

LeetCode-29-Divide Two Integers

原文:https://www.cnblogs.com/nobodywang/p/10331640.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!