Leetcode题解（二）
中等难度leetcode算法刷题记录
29. Divide Two Integers
Companies
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, which means losing its fractional part. For example, truncate(8.345) = 8 and truncate(-2.7335) = -2.
Note: Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For this problem, assume that your function returns 231 − 1 when the division result overflows.
Example 1
Input: dividend = 10, divisor = 3
Output: 3
Explanation: 10/3 = truncate(3.33333..) = 3.
Example 2:
Input: dividend = 7, divisor = -3
Output: -2
Explanation: 7/-3 = truncate(-2.33333..) = -2.
Example 3:
Input: dividend = 0, divisor = 1
Output: 0
Example 4:
Input: dividend = 1, divisor = 1
Output: 1
Constraints
-231 <= dividend, divisor <= 231 - 1
divisor != 0
Solution1
主要思路为不断减去除数，直到被除数无法再减
func divide(dividend int, divisor int) int {
result := 0
sign := true
if dividend >= 0 {
if divisor < 0 {
divisor = -divisor
} else {
sign = false
}
} else {
dividend = -dividend
if divisor < 0 {
divisor = -divisor
sign = false
}
}
for dividend >= divisor {
dividend = dividend - divisor
result++
}
if sign {
result = -result
} else {
result = result
}
if result < -int(math.Pow(2, 31)) {
return -int(math.Pow(2, 31))
}
if result > int(math.Pow(2, 31)-1) {
return int(math.Pow(2, 31) - 1)
}
return result
}
Solution2
使用二分法，依次判断是否能减去1xdivisor，2xdivisor，4xdivisor……
func divide(dividend int, divisor int) int {
if divisor == 0 {
return 0
}
result := 0
sign1 := dividend > 0
sign2 := divisor > 0
sign := !(sign1 != sign2)
if !sign1 {
dividend = -dividend
}
if !sign2 {
divisor = -divisor
}
for dividend >= divisor {
num := 1
d:=divisor
for d<<1 <= dividend {
d <<= 1
num <<= 1
}
dividend -= d
result += num
}
if !sign {
result=-result
if result<math.MinInt32{
return math.MinInt32
}
}else{
if result>math.MaxInt32 {
return math.MaxInt32
}
}
return result
}
