Skip to content
Fetching contributors…
Cannot retrieve contributors at this time
173 lines (128 sloc) 4.24 KB

## 题目地址

https://leetcode.com/problems/divide-two-integers/description/

## 题目描述

``````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.

``````

## 思路

```  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```

## 相关题目

You can’t perform that action at this time.