剑指offer57（剑指OfferII001.整数除法）
剑指offer57（剑指OfferII001.整数除法）示例 4：输入：a = 1 b = 1 输出：1示例 3：输入：a = 0 b = 1 输出：0解释：15/2 = truncate(7.5) = 7示例 2：输入：a = 7 b = -3 输出：-2解释：7/-3 = truncate(-2.33333..) = -2
题目给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%' 。
注意：整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231 231−1]。本题中，如果除法结果溢出，则返回 231 − 1
示例 1：输入：a = 15 b = 2 输出：7
解释：15/2 = truncate(7.5) = 7
示例 2：输入：a = 7 b = -3 输出：-2
解释：7/-3 = truncate(-2.33333..) = -2
示例 3：输入：a = 0 b = 1 输出：0
示例 4：输入：a = 1 b = 1 输出：1
提示:-231 <= a b <= 231 - 1
b != 0
注意：本题与主站 29 题相同
解题思路分析1、遍历；时间复杂度O(log(n))，空间复杂度O(1)
func divide(a int b int) int {
if b == 0 || a == 0 {
return 0
}
if b == 1 {
return a
}
flag count := 1 1
if a < 0 {
flag = -flag
a = -a
}
if b < 0 {
flag = -flag
b = -b
}
x y z := a b 0
temp := y
for x-y >= 0 {
for x-y >= 0 {
x = x - y
z = z count
y = y y
count = count count
}
y = temp
count = 1
}
if z > math.MaxInt32 {
return math.MaxInt32
}
if flag < 0 {
return -z
}
return z
}
2、计算；时间复杂度O(1)，空间复杂度O(1)
func divide(a int b int) int {
res := a / b
if res > math.MaxInt32 {
return math.MaxInt32
}
return res
}总结
Easy题目，题目同leetcode 29.两数相除
