0%

leetcode 29 Divide Two Integers

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT. 题目地址:leetcode Divide Two Integers

题目大意: 给两个数,要求实现除法运算,但是不能用乘法、除法和模运算。

思路

用除数每次*2(向左移动一位)去逼近被除数,被除数减去新的除数如此循环。

详见代码。

需要注意的是溢出需要返回int_max ,还有防止移位运算溢出需要用long long

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
long long bit_divide(long long &dividend, long long divisor) {
long long res = 1;
for (; (divisor << 1) <= dividend; res <<= 1, divisor <<= 1) ;
dividend -= divisor;
return res;
}

public:
int divide(int dividend, int divisor) {
long long dividend_l = labs(dividend), divisor_l = labs(divisor);
int flag = (dividend < 0) ^ (divisor < 0);
long long ans = 0;
while (divisor_l <= dividend_l) {
ans += bit_divide(dividend_l, divisor_l);
if (ans >= INT_MAX) {
if (flag && -ans == INT_MIN) return INT_MIN;
return INT_MAX;
}
}
return flag? -ans : ans;
}
};

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
def divide(self, dividend, divisor):
"""
:type dividend: int
:type divisor: int
:rtype: int
"""
flag = (dividend < 0) ^ (divisor < 0)
dividend, divisor = abs(dividend), abs(divisor)
ans = 0
while divisor <= dividend:
temp = 1
div = divisor
while (div << 1) <= dividend:
div <<= 1
temp <<= 1
dividend -= div
ans += temp
if ans >= 0x7fffffff:
if flag and ans == 0x80000000:
return -0x80000000
return 0x7fffffff
return ans if not flag else -ans

 

更多题解可以查看: https://www.hrwhisper.me/leetcode-algorithm-solution/

请我喝杯咖啡吧~