首页 > 代码库 > [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; }
2147483648 overflow 所以返回MAX_INT 2147483647
[LeetCode]29.Divide Two Integers
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。