daily leetcode - divide-two-integers - !
题目地址
https://leetcode.com/problems/divide-two-integers/
题目描述
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.
思路
这道题让我们求两数相除,而且规定不能用乘法,除法和取余操作,那么这里可以用另一神器位操作 Bit Manipulation,思路是,如果被除数大于或等于除数,则进行如下循环,定义变量t等于除数,定义计数p,当t的两倍小于等于被除数时,进行如下循环,t扩大一倍,p扩大一倍,然后更新 res 和m。这道题的 OJ 给的一些 test case 非常的讨厌,因为输入的都是 int 型,比如被除数是 -2147483648,在 int 范围内,当除数是 -1 时,结果就超出了 int 范围,需要返回 INT_MAX,所以对于这种情况就在开始用 if 判定,将其和除数为0的情况放一起判定,返回 INT_MAX。然后还要根据被除数和除数的正负来确定返回值的正负,这里采用长整型 long 来完成所有的计算,最后返回值乘以符号即可,代码如下:
解法一:
class Solution {
public:
int divide(int dividend, int divisor) {
if (dividend == INT_MIN && divisor == -1) return INT_MAX;
long m = labs(dividend), n = labs(divisor), res = 0;
int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1;
if (n == 1) return sign == 1 ? m : -m;
while (m >= n) {
long t = n, p = 1;
while (m >= (t << 1)) {
t <<= 1;
p <<= 1;
}
res += p;
m -= t;
}
return sign == 1 ? res : -res;
}
};
我们可以通过递归的方法来解使上面的解法变得更加简洁:
解法二:
class Solution {
public:
int divide(int dividend, int divisor) {
long m = labs(dividend), n = labs(divisor), res = 0;
if (m < n) return 0;
long t = n, p = 1;
while (m > (t << 1)) {
t <<= 1;
p <<= 1;
}
res += p + divide(m - t, n);
if ((dividend < 0) ^ (divisor < 0)) res = -res;
return res > INT_MAX ? INT_MAX : res;
}
};
思路2
符合直觉的做法是,减数一次一次减去被减数,不断更新差,直到差小于0,我们减了多少次,结果就是多少。
核心代码:
let acc = divisor;
let count = 0;
while (dividend - acc >= 0) {
acc += divisor;
count++;
}
return count;
这种做法简单直观,但是性能却比较差. 下面来介绍一种性能更好的方法。
通过上面这样的分析,我们直到可以使用二分法来解决,性能有很大的提升。
关键点解析
-
二分查找
-
正负数的判断中,这样判断更简单。
const isNegative = dividend > 0 !== divisor > 0;
代码
- 语言支持:JS,Python3
/*
* @lc app=leetcode id=29 lang=javascript
*
* [29] Divide Two Integers
*/
/**
* @param {number} dividend
* @param {number} divisor
* @return {number}
*/
var divide = function(dividend, divisor) {
if (divisor === 1) return dividend;
// 这种方法很巧妙,即符号相同则为正,不同则为负
const isNegative = dividend > 0 !== divisor > 0;
const MAX_INTERGER = Math.pow(2, 31);
const res = helper(Math.abs(dividend), Math.abs(divisor));
// overflow
if (res > MAX_INTERGER - 1 || res < -1 * MAX_INTERGER) {
return MAX_INTERGER - 1;
}
return isNegative ? -1 * res : res;
};
function helper(dividend, divisor) {
// 二分法
if (dividend <= 0) return 0;
if (dividend < divisor) return 0;
if (divisor === 1) return dividend;
let acc = 2 * divisor;
let count = 1;
while (dividend - acc > 0) {
acc += acc;
count += count;
}
// 直接使用位移运算,比如acc >> 1会有问题
const last = dividend - Math.floor(acc / 2);
return count + helper(last, divisor);
}
Python3 Code:
class Solution:
def divide(self, dividend: int, divisor: int) -> int:
"""
二分法
:param int divisor
:param int dividend
:return int
"""
# 错误处理
if divisor == 0:
raise ZeroDivisionError
if abs(divisor) == 1:
result = dividend if 1 == divisor else -dividend
return min(2**31-1, max(-2**31, result))
# 确定结果的符号
sign = ((dividend >= 0) == (divisor >= 0))
result = 0
# abs也可以直接写在while条件中,不过可能会多计算几次
_divisor = abs(divisor)
_dividend = abs(dividend)
while _divisor <= _dividend:
r, _dividend = self._multi_divide(_divisor, _dividend)
result += r
result = result if sign else -result
# 注意返回值不能超过32位有符号数的表示范围
return min(2**31-1, max(-2**31, result))
def _multi_divide(self, divisor, dividend):
"""
翻倍除法,如果可以被除,则下一步除数翻倍,直至除数大于被除数,
返回商加总的结果与被除数的剩余值;
这里就不做异常处理了;
:param int divisor
:param int dividend
:return tuple result, left_dividend
"""
result = 0
times_count = 1
while divisor <= dividend:
dividend -= divisor
result += times_count
times_count += times_count
divisor += divisor
return result, dividend
本文参考自:
https://github.com/grandyang/leetcode/ &
https://github.com/azl397985856/leetcode