LeetCode: 29. Divide Two Integers

引言

题目链接:https://leetcode.com/problems/divide-two-integers/

题目大意

给定一个除数和被除数,要求不使用除法、乘法以及取模操作计算。返回两个数做除法的商(结果取整数,就相当于两个int做计算)

Hint

------------------
1. 被除数和除数都是32位整数(int32)
2. 除数永远不可能为0
3. 本题运行环境只能存储int32类型,如果计算结果溢出,返回2^31 − 1

  • Example

题解

题目规定了无法使用乘除法取模运算,因此就只有考虑加减法和位运算了。

假设商为s,余数为r,则有$dividend=divisor*s+r$

一个比较朴素的想法就是一直用被除数($dividend$)减去除数($divisor$),直到某一次结果小于除数的时候,总共操作的减法次数就是商s的值。但是这样当被除数很大,除数很小的时候,进行减法操作次数会很多,运算就会超时。

可行的方法就是减少做减法的次数,有如下操作过程

$s=2^0+2^1+...2^k$

$dividend=divisor∗(2^0+2^1+...+2^k)+r$

每一次确定当前等式的$2^k$,$dividend$减去$dicisor*2^k$,$2^k$等于减去这个数等效的做减法次数,至于求解$2^k$,一个高效的方法可以通过位移运算实现,即原等式与如下等式等价

$dividend=divisor<<0+divisor<<1+...+divisor<<k+r$

复杂度

时间复杂度 O((logn)^2), n等于被除数的位数

空间复杂度 O(1)

AC代码

c++版本

go版本

繁夜

发表评论


:[微笑]::[撇嘴]::[色]::[发呆]::[得意]::[流泪]::[害羞]::[闭嘴]::[睡]::[大哭]::[尴尬]::[发怒]::[调皮]::[呲牙]::[惊讶]::[难过]::[酷]::[冷汗]::[抓狂]::[吐]::[偷笑]::[可爱]::[白眼]::[傲慢]::[饥饿]::[困]::[惊恐]::[流汗]::[憨笑]::[大兵]::[奋斗]::[咒骂]::[疑问]::[嘘...]::[晕]::[折磨]::[衰]::[骷髅]::[敲打]::[再见]::[擦汗]::[抠鼻]::[鼓掌]::[糗大了]::[坏笑]::[左哼哼]::[右哼哼]::[哈欠]::[鄙视]::[委屈]::[快哭了]::[阴险]::[亲亲]::[吓]::[可怜]::[笑哭]::[doge]::[泪奔]::[无奈]::[托腮]::[斜眼笑]::[喷血]::[惊喜]::[骚扰]::[小纠结]::[我最美]::[羊驼]::[幽灵]::[吃]::[OK]::[爱你]::[抱拳]::[勾引]::[强]::[弱]::[拳头]::[爱心]::[喝彩]::[西瓜]::[啤酒]::[玫瑰]::[凋谢]::[礼物]::[拥抱]::[月亮]::[菊花]::[棒棒糖]::[蛋]::[刀]::[菜刀]::[炸弹]::[手枪]:

刷新评论