除法转换为减法]leetcode29:两数相除(medium)"/>
[除法转换为减法]leetcode29:两数相除(medium)
题目:
题解:
- 题解1:作弊法,排除溢出情况后,直接返回两数相除的结果
- 题解2:减法,计算被除数能减去除数的个数
- 比如
[15,3]
,若被除数15
每次减除数3
,需要减5次。那么请思考如何简化呢?- 答案:将除数每次都翻倍,直到除数大于被除数时,将除数还原为初始值。
- 比如第一次
[15,3]
(这里减了一个除数,result+=1),第二次就变为[12,6]
(这里减了两个除数,result+=2),第三次为[6,12]
(除数大于被除数需要将除数还原变为[6,3]),第4次[6,3]
(这里减了一个除数,result+=1),第5次[3,3]
(这里减了一个除数,result+=1)
代码如下:
class Solution {
public://题解1:作弊法int divide_1(int dividend, int divisor) {if (dividend==-2147483648&&divisor==-1)return INT_MAX;return dividend/divisor;}//题解2:减法,计算被除数能减去除数的个数int divide(int dividend, int divisor){int sign=1;//表示符号位的,正数为0,负数为1if ((dividend>0&&divisor>0)||(dividend<0&&divisor < 0)){//正数sign=0;}//注意这里的数都要转为long long,不然lc就报错了long long dd=abs((long long)dividend),ds=abs((long long)divisor),result=0;while(dd>=ds){long long temp=ds,i=1;//temp表示翻倍的除数,i表示除数的个数while(dd>=temp){dd-=temp;//被除数减去除数result+=i;//加上减去除数的个数temp<<=1;//除数翻倍i<<=1;//除数个数也翻倍}}result=sign==0?result:-result;if(result<INT_MIN)return INT_MIN;if(result>INT_MAX)return INT_MAX;return result;}
};
更多推荐
[除法转换为减法]leetcode29:两数相除(medium)
发布评论