-
-
Notifications
You must be signed in to change notification settings - Fork 737
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
[LeetCode] 29. Divide Two Integers #29
Comments
应该是不能用long定义变量的 |
Really hate this Problem. SO many overflow inputs... After hours of commits, finally fixed the overflow inputs...
|
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
请点击下方图片观看讲解视频
Click below image to watch YouTube Video
Given two integers
dividend
anddivisor
, divide two integers without using multiplication, division, and mod operator.The integer division should truncate toward zero, which means losing its fractional part. For example,
8.345
would be truncated to8
, and-2.7335
would be truncated to-2
.Return _the quotient after dividing _
dividend
bydivisor
.Note: Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range:
[−2^31, 2^31 − 1]
. For this problem, if the quotient is strictly greater than2^31 - 1
, then return2^31 - 1
, and if the quotient is strictly less than-2^31
, then return-2^31
.Example 1:
Example 2:
Constraints:
-2^31 <= dividend, divisor <= 2^31 - 1
divisor != 0
这道题让我们求两数相除,而且规定不能用乘法,除法和取余操作,那么这里可以用另一神器位操作 Bit Manipulation,思路是,如果被除数大于或等于除数,则进行如下循环,定义变量t等于除数,定义计数p,当t的两倍小于等于被除数时,进行如下循环,t扩大一倍,p扩大一倍,然后更新 res 和m。这道题的 OJ 给的一些 test case 非常的讨厌,因为输入的都是 int 型,比如被除数是 -2147483648,在 int 范围内,当除数是 -1 时,结果就超出了 int 范围,需要返回 INT_MAX,所以对于这种情况就在开始用 if 判定,返回 INT_MAX。然后还要根据被除数和除数的正负来确定返回值的正负,这里采用长整型 long 来完成所有的计算,最后返回值乘以符号即可。其实这道题的本质还是不停的成倍数扩大除数,虽然题目说了不能用乘法,但是这里用了位操作的左移来巧妙地规避了这一点,因为左移一位就相当于乘以2。
这里的外层 while 循环是判断被除数大于等于除数,然后里面定义了个临时变量t,初始化为除数n,还有表示临时商的p,初始化为1。内层的 while 循环就是通过不停扩大除数,来找到临时商的最大值,比如若被除数 m=56,除数 n=5 的话,此时经过内层 while 循环后,t=40,p=8,此时t再翻倍的话,就会超过被除数了,所以就到这里,然后更新结果 res 和被除数m的值。下一轮循环时被除数 m=16,除数 n=5,此时经过内层 while 循环后,t=10,p=2,此时t再翻倍的话,就会超过被除数了,所以就到这里,然后更新结果 res 和被除数m的值。下一轮循环时被除数 m=6,除数 n=5,此时经过内层 while 循环后,t=5,p=1,此时t再翻倍的话,就会超过被除数了,所以就到这里,然后更新结果 res 和被除数m的值。这时候被除数 m=1,除数 n=5,被除数小于除数了,跳出外层 while 循环,返回结果 res=11 即可,参见代码如下:
解法一:
我们可以通过递归的方法来解使上面的解法变得更加简洁:
解法二:
Github 同步地址:
#29
参考资料:
https://leetcode.com/problems/divide-two-integers/
https://leetcode.com/problems/divide-two-integers/discuss/13524/summary-of-3-c-solutions
https://leetcode.com/problems/divide-two-integers/discuss/13407/C%2B%2B-bit-manipulations
https://leetcode.com/problems/divide-two-integers/discuss/142849/C%2B%2BJavaPython-Should-Not-Use-%22long%22-Int
LeetCode All in One 题目讲解汇总(持续更新中...)
(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,快快加入吧~)
微信打赏
Venmo 打赏
---|---
The text was updated successfully, but these errors were encountered: