j
jaryue
V1
2023/03/22阅读:21主题:默认主题
整数除法
剑指offer01整数除法
题目描述
除法,不能使用/*,考虑符号.
解题思路
方法1 暴力循环 不断地减,(符号不同就加),直到换号前,返回循环次数
if a >= 0 && b > 0 {//ab大于0时
for ; a-b >= 0; i++ {//记录循环次数
a = a - b
}
} else if a > 0 && b < 0 {//a>0 , b<0
for ; a+b >= 0; i-- {
a = a + b
}
} else if a < 0 && b > 0 {//a>0 , b<0
for ; a+b <= 0; i-- {
a = a + b
}
} else {//ab小于0时
for ; a-b <= 0; i++ {
a = a - b
}
}
if i > 2147483647 {//题目对数字极限的要求-2^31 <= a, b <= 2^31 - 1
return 2147483647
}
return i
代码示例
func divide1(a int, b int) int {
if b == 1 {//当b=1或-1时为了降低循环次数,可以直接返回
return a
} else if b == -1 {
if -a > 2147483647 {
return 2147483647
} else {
return -a
}
}
i := 0
if a >= 0 && b > 0 {//ab大于0时
for ; a-b >= 0; i++ {//记录循环次数
a = a - b
}
} else if a > 0 && b < 0 {
for ; a+b >= 0; i-- {
a = a + b
}
} else if a < 0 && b > 0 {
for ; a+b <= 0; i-- {
a = a + b
}
} else {
for ; a-b <= 0; i++ {
a = a - b
}
}
if i > 2147483647 {
return 2147483647
}
return i
}
但是这个提交不了,不建议使用.....原因是太过于暴力
方法2
位运算,二分查找法
二分查找可以说是最好的查找方法了
-
首先我们考虑到a很大b很小的时候需要循环太多次,为了避免这种情况我们需要一次减b的多倍,就是运用位运算,b<<n左移n位数字扩大2^n倍也就是一次减了2^n次b,同时用一个数来记录减的次数,1<<n记录,一位一位的移动就实现了二分查找了,循环条件设置为a-b >= 0就是当a不能减b是时停止
核心算法
// 大于0时的除法
func zsc(a, b int) int {
t := 0 //记录循环次数
bt := b
for i := 1; a-b >= 0; { //都大于0的情况
if a-(bt<<1) > 0 {//如果能够继续减去左移就继续左移
bt <<= 1
i <<= 1
} else {//如果不能继续减去左移就记录次数,i(临时)重新计数t(总次数)次数叠加
a = a - bt
t = t + i
i = 1
bt = b
}
}
return t
}
执行结果
// 大于0时的除法
func zsc(a, b int) int {
t := 0 //记录循环次数
bt := b
for i := 1; a-b >= 0; { //都大于0的情况
if a-(bt<<1) > 0 {//如果能够继续减去左移就继续左移
bt <<= 1
i <<= 1
} else {//如果不能继续减去左移就记录次数,i(临时)重新计数t(总次数)次数叠加
a = a - bt
t = t + i
i = 1
bt = b
}
}
return t
}
// 返回正数
func abs(a int) int {
if a < 0 {
return -a
}
return a
}
// 位运算
func divide(a int, b int) int {
if abs(a) < abs(b) {//比较绝对值大小,|a|<|b|返回0
return 0
}
if b == 1 {//不用循环的情况
return a
} else if b == -1 {
if -a > 2147483647 {
return 2147483647
} else {
return -a
}
}
if a >= 0 && b > 0 {//ab的各种情况全部转换正数传入计算,根据需求输出
return zsc(a, b)//都大于0
} else if a > 0 && b < 0 {
return -zsc(a, -b)//a>0,b<0
} else if a < 0 && b > 0 {
return -zsc(-a, b)//a<0,,b>0
} else {
return zsc(-a, -b)//a<0..b<0
}
}
执行用时: 4 ms , 在所有 Go 提交中击败了 47.55% 的用户 内存消耗: 2.2 MB , 在所有 Go 提交中击败了 95.10% 的用户 通过测试用例: 992 / 992
作者介绍
j
jaryue
V1