题目链接
英文链接:https://leetcode.com/problems/divide-two-integers/
中文链接:https://leetcode-cn.com/problems/divide-two-integers/
题目详述
给定两个整数,被除数 dividend 和除数 divisor。将两数相除,要求不使用乘法、除法和 mod 运算符。
返回被除数 dividend 除以除数 divisor 得到的商。
示例 1:
1 | 输入: dividend = 10, divisor = 3 |
示例 2:
1 | 输入: dividend = 7, divisor = -3 |
说明:
- 被除数和除数均为 32 位有符号整数。
- 除数不为 0。
- 假设我们的环境只能存储 32 位有符号整数,其数值范围是 [−2^31, 2^31 − 1]。本题中,如果除法结果溢出,则返回 2^31 − 1。
题目详解
- 本题看起来简单,实际上写起来很容易出错。
- 由于不允许使用乘法、除法和取模运算,那么只能采用加减法运算和位运算。
- 首先可以想到把两个数变为正数,然后通过减法来得到结果,最后判别一下符号。并且我们可以找到最大的减数然后逐步递减将时间复杂度从
O(n)
降为O(logn)
。但题目限制了环境只能存储 32 位有符号整数,其数值范围是 [−2^31, 2^31 − 1],当被减数为 −2^31时,在这个环境下不能转换为对应的正数(如果没有这个条件可以使用 64 位的 long),所以这种方法行不通。 - 换一种思路,既然存在负数不能转换为正数,那么能否把正数转换为负数转换位负数?显然可行,32 位有符号环境下,正数能得到对应的负数。接下来的思路同上,依旧是做减法,直至被减数小于减数。同样可以把时间复杂度从
O(n)
降为O(logn)
。 - 特别要注意一些边界条件的判断。
- 时间复杂度为
O(logn)
,n
为被除数的绝对值,不超过 32。
1 | public class LeetCode_00029 { |