Leetcode No.29 两数相除
一、题目描述
给定两个整数，被除数 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 位有符号整数，其数值范围是 [−231, 231 − 1]。本题中，如果除法结果溢出，则返回 231 − 1。
二、解题思路
除法的本质是减法，比如8/2=4 也就是8-2-2-2-2=0 关于如何提高效率快速逼近结果 举个例子：11 除以 3 。 首先11比3大，结果至少是1， 然后我让3翻倍，就是6，发现11比6还要大，那么结果就至少是2了，那我让这个6再翻倍，得12，11小于12。最终结果肯定在2和4之间。
也就是说2再加上某个数，这个数是多少呢？我让11减去刚才最后一次的结果6，剩下5，我们计算5是3的几倍，也就是除法，看，递归出现了。
一些细节的处理：将除数和被除数都转化为负数，可防止整数越界，如果转化为正数，当处理INT最小值时，会出现整数越界。
三、代码
class Solution {
public:
int divide(int dividend, int divisor) {
if(divisor==-1){
if(dividend<=INT_MIN){
return INT_MAX;
}else{
return -dividend;
}
}
if(divisor==1){
return dividend;
}
int sign=1;
if((dividend>0&&divisor<0)||(dividend<0&&divisor>0)){
sign=-1;
}
dividend=-abs(dividend);//转化为负数,如果使用正数，-2147483648取绝对值会越界
divisor=-abs(divisor);//转化为负数
int rs = div(dividend,divisor);
cout<<rs<<endl;
if(sign>0){
return rs;
}
return -rs;
}
int div(int a,int b){
if(a>b){
return 0;
}
int cnt=1;
int tb=b;
while(tb - a + tb >= 0){
cnt=cnt+cnt;// 解翻倍
tb=tb+tb;// 除数翻倍
}
return cnt+div(a-tb,b);
}
};四、复杂度分析
时间复杂度：O(logn）
空间复杂度：O(1)
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020/12/20 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
