大家好,欢迎来到IT知识分享网。
Given two integers dividend
and divisor
, divide two integers without using multiplication, division and mod operator.
Return the quotient after dividing dividend
by divisor
.
The integer division should truncate toward zero.
Example 1:
Input: dividend = 10, divisor = 3 Output: 3
Example 2:
Input: dividend = 7, divisor = -3 Output: -2
Note:
- Both dividend and divisor will be 32-bit signed integers.
- The divisor will never be 0.
- Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 231 − 1 when the division result overflows.
这道题让我们求两数相除,而且规定不能用乘法,除法和取余操作,那么这里可以用另一神器位操作 Bit Manipulation,思路是,如果被除数大于或等于除数,则进行如下循环,定义变量t等于除数,定义计数p,当t的两倍小于等于被除数时,进行如下循环,t扩大一倍,p扩大一倍,然后更新 res 和m。这道题的 OJ 给的一些 test case 非常的讨厌,因为输入的都是 int 型,比如被除数是 -2147483648,在 int 范围内,当除数是 -1 时,结果就超出了 int 范围,需要返回 INT_MAX,所以对于这种情况就在开始用 if 判定,将其和除数为0的情况放一起判定,返回 INT_MAX。然后还要根据被除数和除数的正负来确定返回值的正负,这里采用长整型 long 来完成所有的计算,最后返回值乘以符号即可,代码如下:
解法一:
class Solution { public: int divide(int dividend, int divisor) { if (dividend == INT_MIN && divisor == -1) return INT_MAX; long m = labs(dividend), n = labs(divisor), res = 0; int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1; if (n == 1) return sign == 1 ? m : -m; while (m >= n) { long t = n, p = 1; while (m >= (t << 1)) { t <<= 1; p <<= 1; } res += p; m -= t; } return sign == 1 ? res : -res; } };
我们可以通过递归的方法来解使上面的解法变得更加简洁:
解法二:
class Solution { public: int divide(int dividend, int divisor) { long m = labs(dividend), n = labs(divisor), res = 0; if (m < n) return 0; long t = n, p = 1; while (m > (t << 1)) { t <<= 1; p <<= 1; } res += p + divide(m - t, n); if ((dividend < 0) ^ (divisor < 0)) res = -res; return res > INT_MAX ? INT_MAX : res; } };
Github 同步地址:
https://github.com/grandyang/leetcode/issues/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 题目讲解汇总(持续更新中…)
免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/29079.html