当前位置:网站首页>[算法] 剑指offer2 golang 面试题1:整数除法
[算法] 剑指offer2 golang 面试题1:整数除法
2022-07-06 09:18:00 【邓嘉文Jarvan】
[算法] 剑指offer2 golang 面试题1:整数除法
题目1:
给定两个整数 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
思路1:
首先的思路是使用讲话代替除法
比如 5/2 可以不断 5-2=3> 0; res ++;
3-2=1 > 0; res++
但是遇到 100000/2 复杂度太高了,我们尝试使用指数级递增, 比如 5/2
15 - 2 = 13> 2; res = 1
15- 4 = 11> 2 ; res = 2
15- 8 > 7 >2; res = 4
15 - 16 = -1 < 2; res = 8, 这个值放弃, res = 4,并在总返回值上加 4, resTotal += res, 并令除数=7, 从头开始指数递增
7-2 = 5 > 2 ; res = 1
7-4 = 3 > 2 ; res = 2
7 -8 = -1 < 2; res =4, 这个值放弃, res = 2,并在总返回值上加 2, …
func myDividefunc(a int, b int) int {
//返回值会溢出 +2^32
//错误输入: 除数为0
if (a == math.MinInt32 && b == -1) || b == 0 {
return math.MaxInt32
}
//记录时候是正数
negative := 2
if a > 0 {
negative--
a = -a
}
if b > 0 {
negative--
b = -b
}
// 负数计算结果
res := divideCore(a, b)
if negative == 1 {
res = -res
}
return res
}
func divideCore(a int, b int) int {
res := 0
// -7 <= -3
for a <= b {
resAdd := 1
b2 := b
for {
//每次翻倍
if a < (b2 + b2) {
//结果每次翻倍
resAdd += resAdd
b2 += b2
} else {
break
}
}
a -= b2
res += resAdd
}
return res
}
代码
func divide(a int, b int) int {
//返回值会溢出 +2^32
//错误输入: 除数为0
if (a == math.MinInt32 && b == -1) || b == 0 {
return math.MaxInt32
}
//记录时候是正数
negative := 2
if a > 0 {
negative--
a = -a
}
if b > 0 {
negative--
b = -b
}
// 负数计算结果
res := divideCore(a, b)
if negative == 1 {
res = -res
}
return res
}
//-7/-3
//使用指数级递增的方式计算
//-7 < -3, 1
//-7 < -6 2
// -7 > -12 3
//-13/3
func divideCore(a int, b int) int {
res := 0
// -7 <= -3
for a <= b {
resAdd := 1
b2 := b
for {
//每次翻倍
if a < (b2+b2) {
//结果每次翻倍
resAdd += resAdd
b2 += b2
}else {
break
}
}
a -= b2
res += resAdd
}
return res
}
测试
边栏推荐
- [offer78]合并多个有序链表
- [Yu Yue education] guide business reference materials of Wuxi Vocational and Technical College of Commerce
- 编译原理:源程序的预处理及词法分析程序的设计与实现(含代码)
- FairyGUI循环列表
- 平衡二叉树详解 通俗易懂
- Get the position of the nth occurrence of the string
- In 2020, the average salary of IT industry exceeded 170000, ranking first
- Teach you to release a DeNO module hand in hand
- 使用rtknavi进行RT-PPP测试
- (1) Introduction Guide to R language - the first step of data analysis
猜你喜欢
idea中好用的快捷键
程序设计大作业:教务管理系统(C语言)
(3) Introduction to bioinformatics of R language - function, data Frame, simple DNA reading and analysis
服务未正常关闭导致端口被占用
RTKLIB: demo5 b34f.1 vs b33
Mysql database reports an error: row size too large (> 8126) Changing some columns to TEXT or BLOB or using ROW_ FORMAT=DY
Single chip Bluetooth wireless burning
NRF24L01故障排查
单片机蓝牙无线烧录
Unity3d makes the registration login interface and realizes the scene jump
随机推荐
How to add music playback function to Arduino project
Unity3D摄像机,键盘控制前后左右上下移动,鼠标控制旋转、放缩
2021.11.10 compilation examination
平衡二叉树详解 通俗易懂
数据库课程设计:高校教务管理系统(含代码)
Matlab读取GNSS 观测值o文件代码示例
What is the maximum length of MySQL varchar field
What are the advantages of using SQL in Excel VBA
idea中导包方法
Fabrication of fairygui simple Backpack
音乐播放(Toggle && PlayerPrefs)
Detailed explanation of truncate usage
1041 Be Unique (20 point(s))(哈希:找第一个出现一次的数)
Talking about the startup of Oracle Database
微信小程序开发心得
(1) Introduction Guide to R language - the first step of data analysis
First use of dosbox
Lock wait timeout exceeded try restarting transaction
Excel导入,导出功能实现
(3) Introduction to bioinformatics of R language - function, data Frame, simple DNA reading and analysis