新博文地址:[leetcode]Divide Two Integers
Divide Two Integers
Divide two integers without using multiplication, division and mod operator.
不使用 乘法、除法、取余来计算除法,这道题在很多书中都有提及,比如面试金典中就有一道题要求只用加法来计算:减法、乘法、除法。其中它对除法的算法思想是,用迭代一个一个加被除数,直到》dividend,但是这无疑是个坑,比如当divideng = Integer.MAX_VALUE;divisor =1;必定会超时。
这道题的题干就给人隐约一种位运算的感觉,事实也的确如此
第一次我尝试用2分法,每一次将divisor * 2,迟早newDivisor * 2会大于dividend,
那么dividend就在[newDivisor ,2 * newDivisor]之间,然后继续从newDivisor开始逐个+ divisor,直到dividend,但是还是超时了.....
今早上突然想到这种2分法可以持续下去的。
接下来用2进制,简单讲一下:
比如dividend 用2进制的表示是1010100,divisor是11,我们一直将divisor * 2,当divisor达到1100000时,超过了dividend,再将其/2,即110000,记录叠加次数。
然后得到二者之差——100100,继续迭代刚才的做法,得到divisor为11000,得到差1100,。
继续刚才的迭代,得到divisor为1100,差为0(差<divisor)则结束。
public int divide(int dividend, int divisor) { long absDividend = Math.abs((long) dividend); long absDivisor = Math.abs((long) divisor); long count = 0, c = 1; while (absDividend >= absDivisor) { absDivisor <<= 1; c <<= 1; if (absDivisor >= absDividend) { if (absDivisor > absDividend) { absDivisor >>= 1; c >>= 1; absDividend -= absDivisor; } count += c; c = 1; if(absDividend == absDivisor){ break; } absDivisor = Math.abs((long) divisor); } } return (int) ((dividend < 0 ^ divisor < 0) ? -count : count); }
要注意溢出情况的考虑,因此将int类型都向上转型为long
相关推荐
c c语言_leetcode 0029_divide_two_integers.zip
js js_leetcode题解之29-divide-two-integers.js
先来看LeetCode-29上的Divide Two Integers题目要求: Divide two integers without using multiplication, division and mod operator. If it is overflow, return MAX_INT. 1 2 3 就是说不用乘法,除法,求模运算...
371 | [Sum of Two Integers](https://leetcode.com/problems/sum-of-two-integers/) | [C++](./C++/sum-of-two-integers.cpp) [Python](./Python/sum-of-two-integers.py) | _O(1)_ | _O(1)_ | Easy | LintCode | ...
8. leetcode-29-Divide-Two-Integers.md:第29题,两数相除,涉及到整数除法和位运算。 9. leetcode-218-The-Skyline-Problem.md:第218题,天际线问题,可能涉及到二维数组处理和线段树或平衡二叉搜索树的数据结构...
- Divide Two Integers: 实现整数除法,不能使用乘法、除法和模运算符。 - Search in Rotated Sorted Array: 在旋转过的排序数组中进行二分查找。 - Search for a Range: 给定一个按照升序排列的数组,和一个目标值...
029_divide_two_integers*.py # 实现整除 050_pow.py # 实现乘幂 066_plus_one.py # 数列末尾值+1 069_sqrt.py # 实现开根号 136_single_number.py # 位操作:异或(xor)操作 x ^ 0 = x; x ^ x = 0 sum 001_two_sum....
Divide Two Integers 两个整数相除,要求不能使用 *,/,以及mod操作符,返回除数,若除数有小数点,只返回整数部分,如2.789,只应返回2,此题为leetcode上的题目 Random Numbers 用计算机生成了N个1到1000之间的...
Practice-Leetcode 这是一个Chinese School Girl:China:用来练习leetcode的文档....29.Divide Two Integers 二进制累加代替除法,防止溢出 36.Valid Sudoku set去重复 2018/04/19: 038.Count and Say 递归 040.C
问题 完全的 017_Letter_Combinations_of_a_Phone_Number 018_4总和 019_Remove_Nth_Node_From_End_of_List 020_Valid_Parentheses ... 029_Divide_Two_Integers 030_Substring_with_Concatenation_of
5. **除以两个整数(Divide Two Integers)** 任务是实现一个函数,模拟整数除法,返回商(不考虑浮点数部分)。这个题目需要考虑整数溢出问题,可以使用位运算和减法进行求解。例如,将除数和被除数都乘以一个足够大...