LeetCode No29. 两数相除
2022/4/27 23:15:12
本文主要是介绍LeetCode No29. 两数相除,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目
给定两个整数,被除数 dividend 和除数 divisor。将两数相除,要求不使用乘法、除法和 mod 运算符。
返回被除数 dividend 除以除数 divisor 得到的商。
整数除法的结果应当截去(truncate)其小数部分,例如:truncate(8.345) = 8 以及 truncate(-2.7335) = -2
示例 1:
输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = truncate(3.33333..) = truncate(3) = 3
示例 2:
输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = truncate(-2.33333..) = -2
提示:
被除数和除数均为 32 位有符号整数。
除数不为 0。
假设我们的环境只能存储 32 位有符号整数,其数值范围是 [−2^31, 2^31 − 1]。本题中,如果除法结果溢出,则返回 2^31 − 1。
思路
这种模拟计算底层运算的算法应该来说是比较难的,求两数相除的数,也就是 a/b, 既然是取整的,我们就可以看成求一个最大的数c,使得 c*b<=a,而这种在固定顺序中找某个数的方法当仁不让的要用二分了。而想到这一步之后,其实还有一个难点,就是题目要求不使用乘法、除法和 mod 运算符,那也就是说需要用加法去模拟乘法了,但是用不同的方法很容易就超时,于是就想到了快速乘算法。
AC代码
点击查看代码
class Solution { public int divide(int dividend, int divisor) { // 考虑被除数为最小值的情况 if (dividend == Integer.MIN_VALUE) { if (divisor == 1) { return Integer.MIN_VALUE; } if (divisor == -1) { return Integer.MAX_VALUE; } } // 考虑除数为最小值的情况 if (divisor == Integer.MIN_VALUE) { return dividend == Integer.MIN_VALUE ? 1 : 0; } // 考虑被除数为 0 的情况 if (dividend == 0) { return 0; } // 一般情况,使用二分查找 // 将所有的正数取相反数,这样就只需要考虑一种情况 boolean rev = false; if (dividend > 0) { dividend = -dividend; rev = !rev; } if (divisor > 0) { divisor = -divisor; rev = !rev; } int left = 1, right = Integer.MAX_VALUE, ans = 0; while (left <= right) { // 注意溢出,并且不能使用除法 int mid = left + ((right - left) >> 1); boolean check = quickAdd(divisor, mid, dividend); if (check) { ans = mid; // 注意溢出 if (mid == Integer.MAX_VALUE) { break; } left = mid + 1; } else { right = mid - 1; } } return rev ? -ans : ans; } // 快速乘 public boolean quickAdd(int y, int z, int x) { // x 和 y 是负数,z 是正数 // 需要判断 z * y >= x 是否成立 int result = 0, add = y; while (z != 0) { if ((z & 1) != 0) { // 需要保证 result + add >= x if (result < x - add) { return false; } result += add; } if (z != 1) { // 需要保证 add + add >= x if (add < x - add) { return false; } add += add; } // 不能使用除法 z >>= 1; } return true; } }
这篇关于LeetCode No29. 两数相除的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-03微信支付提示下单账户与支付账户不一致-icode9专业技术文章分享
- 2024-07-03微信支付提示订单号重复-icode9专业技术文章分享
- 2024-07-02微服务启动nacos注册上去了,但是一直没有收到请求-icode9专业技术文章分享
- 2024-07-02如何检查文件的编码格式-icode9专业技术文章分享
- 2024-07-02sublime 更改编码格式-icode9专业技术文章分享
- 2024-06-30uniAPP 实现全屏左右滚动滚动的效果-icode9专业技术文章分享
- 2024-06-30如何在本地使用授权或插件-icode9专业技术文章分享
- 2024-06-30伪静态规则配置方法汇总-icode9专业技术文章分享
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享