当前位置:网站首页>[algorithm] sword finger offer2 golang interview question 1: integer division
[algorithm] sword finger offer2 golang interview question 1: integer division
2022-07-06 12:50:00 【Deng Jiawen jarvan】
[ Algorithm ] The finger of the sword offer2 golang Interview questions 1: Integer division
subject 1:
Given two integers a and b , Find the quotient of their division a/b , It is required that the multiplication sign... Shall not be used ‘*’、 devide ‘/’ And the remainder symbol ‘%’ .
Be careful :
The result of integer division should be truncated (truncate) Its decimal part , for example :truncate(8.345) = 8 as well as truncate(-2.7335) = -2
Suppose our environment can only store 32 Bit signed integer , The value range is [−231, 231−1]. In this question , If the division result overflows , Then return to 231 − 1
Example 1:
Input :a = 15, b = 2
Output :7
explain :15/2 = truncate(7.5) = 7
Example 2:
Input :a = 7, b = -3
Output :-2
explain :7/-3 = truncate(-2.33333..) = -2
Example 3:
Input :a = 0, b = 1
Output :0
Example 4:
Input :a = 1, b = 1
Output :1
Tips :
-231 <= a, b <= 231 - 1
b != 0
Ideas 1:
The first idea is to use speech instead of division
such as 5/2 Can keep 5-2=3> 0; res ++;
3-2=1 > 0; res++
But encountered 100000/2 It's too complicated , We try to use exponential increments , such as 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, This value gives up , res = 4, And add... To the total return value 4, resTotal += res, Union divisor =7, From the beginning, the index increases
7-2 = 5 > 2 ; res = 1
7-4 = 3 > 2 ; res = 2
7 -8 = -1 < 2; res =4, This value gives up , res = 2, And add... To the total return value 2, …
func myDividefunc(a int, b int) int {
// The return value will overflow +2^32
// Wrong input : Divisor is 0
if (a == math.MinInt32 && b == -1) || b == 0 {
return math.MaxInt32
}
// The recording time is positive
negative := 2
if a > 0 {
negative--
a = -a
}
if b > 0 {
negative--
b = -b
}
// Negative number calculation result
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 {
// Double every time
if a < (b2 + b2) {
// The result doubled each time
resAdd += resAdd
b2 += b2
} else {
break
}
}
a -= b2
res += resAdd
}
return res
}
Code
func divide(a int, b int) int {
// The return value will overflow +2^32
// Wrong input : Divisor is 0
if (a == math.MinInt32 && b == -1) || b == 0 {
return math.MaxInt32
}
// The recording time is positive
negative := 2
if a > 0 {
negative--
a = -a
}
if b > 0 {
negative--
b = -b
}
// Negative number calculation result
res := divideCore(a, b)
if negative == 1 {
res = -res
}
return res
}
//-7/-3
// Calculate in exponential increments
//-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 {
// Double every time
if a < (b2+b2) {
// The result doubled each time
resAdd += resAdd
b2 += b2
}else {
break
}
}
a -= b2
res += resAdd
}
return res
}
test
边栏推荐
- (3) Introduction to bioinformatics of R language - function, data Frame, simple DNA reading and analysis
- [Leetcode15]三数之和
- Derivation of logistic regression theory
- 第一人称视角的角色移动
- FairyGUI按钮动效的混用
- 341. Flatten nested list iterator
- [Offer29] 排序的循环链表
- [算法] 剑指offer2 golang 面试题2:二进制加法
- FairyGUI条子家族(滚动条,滑动条,进度条)
- isEmpty 和 isBlank 的用法区别
猜你喜欢
C programming exercise
Gravure sans fil Bluetooth sur micro - ordinateur à puce unique
3月15号 Go 1.18 正式版发布 了解最新特色以及使用方法
Liste des boucles de l'interface graphique de défaillance
FairyGUI簡單背包的制作
There is no red exclamation mark after SVN update
[算法] 剑指offer2 golang 面试题1:整数除法
FairyGUI增益BUFF数值改变的显示
Fairygui character status Popup
FairyGUI增益BUFF數值改變的顯示
随机推荐
【RTKLIB 2.4.3 b34 】版本更新简介一
Particle system for introduction to unity3d Foundation (attribute introduction + case production of flame particle system)
Unity3d camera, the keyboard controls the front and rear left and right up and down movement, and the mouse controls the rotation, zoom in and out
Mysql database index
[Yu Yue education] guide business reference materials of Wuxi Vocational and Technical College of Commerce
(课设第一套)1-5 317号子任务 (100 分)(Dijkstra:重边自环)
It has been solved by personal practice: MySQL row size too large (> 8126) Changing some columns to TEXT or BLOB or using ROW_ FORMAT
[leetcode15] sum of three numbers
[899] ordered queue
Minio file download problem - inputstream:closed
3月15号 Go 1.18 正式版发布 了解最新特色以及使用方法
使用rtknavi进行RT-PPP测试
【干货】提升RTK模糊度固定率的建议之周跳探测
1041 Be Unique (20 point(s))(哈希:找第一个出现一次的数)
dosbox第一次使用
Unity3D摄像机,键盘控制前后左右上下移动,鼠标控制旋转、放缩
(core focus of software engineering review) Chapter V detailed design exercises
(the first set of course design) 1-4 message passing interface (100 points) (simulation: thread)
Esp8266 connect onenet (old mqtt mode)
wsl常用命令