【LeetCode-29】两数相除
2021/8/15 6:38:25
本文主要是介绍【LeetCode-29】两数相除,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
问题
给定两个整数,被除数 dividend 和除数 divisor。将两数相除,要求不使用乘法、除法和 mod 运算符。
返回被除数 dividend 除以除数 divisor 得到的商。
整数除法的结果应当截去(truncate)其小数部分,例如:truncate(8.345) = 8 以及 truncate(-2.7335) = -2
示例
输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = truncate(3.33333..) = truncate(3) = 3
解答1:二分答案+倍增乘法
class Solution { public: int divide(int dividend, int divisor) { long a = dividend, b = divisor; bool neg = (a ^ b) < 0; // 两个数异或,结果小于0则异号 if (a < 0) a = -a; if (b < 0) b = -b; long left = 0, right = a; while (left < right) { long mid = (left + right + 1) >> 1; if (mul(mid, b) > a) right = mid - 1; else left = mid; } long res = neg ? -left : left; if (res > INT_MAX || res < INT_MIN) return INT_MAX; return res; } private: long mul(long a, long b) { long res = 0; while (b > 0) { if (b & 1) res += a; a += a; b >>= 1; } return res; } };
重点思路
中间变量有使用long
,这样逻辑会清楚很多。首先统计是否异号,然后将两个数均置为正数。使用二分答案的方法缩小解的范围,二分中的check
函数使用倍增乘法的模版(类似快速幂),时间复杂度为\(O(log(a)) * O(log(b))\)。
解答2
class Solution { public: int divide(int dividend, int divisor) { if (dividend == INT_MIN && divisor == -1) return INT_MAX; // 唯一可能导致res溢出的输入 if (divisor == 1) return dividend; // 防止INT_MIN / 1时,div中的res溢出 bool neg = (dividend ^ divisor) < 0; if (divisor > 0) divisor = -divisor; // 全部置为负数,保证处理INT_MIN相关计算时不会溢出 if (dividend > 0) dividend = -dividend; int res = div(dividend, divisor); return neg ? -res : res; } private: int div(int a, int b) { if (a > b) return 0; int res = 1, step = b; while (a - step <= step) { step += step; res += res; } return res + div(a - step, b); } };
重点思路
- 两种特殊情况直接输出;
- 全部置为负数,保证处理
INT_MIN
相关计算时不会溢出; - 在
div
函数中,需要注意a
和b
都是小于等于0的。
这篇关于【LeetCode-29】两数相除的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 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专业技术文章分享