首页 > 代码库 > LeetCode: Divide Two Integers [028]
LeetCode: Divide Two Integers [028]
【题目】
【题意】
计算两个数的商，不能使用乘、除、取余操作
【思路】
用加法，确定多少除数相加其和恰好<=被除数为了提高算法效率，利用贪心思想，采用滚雪球式的翻倍叠加策略，使和快速逼近被除数
几种特殊情况需要注意：
1. 结果是负数
2. 除数的绝对值要比被除数的绝对值大
3. 除数是0
4. 被除是0
5. 注意除数翻倍累加时越界，超过int的上界
【代码】
class Solution {
public:
int divide(int dividend, int divisor) {
if(divisor==0 || dividend==0)return 0;
if(divisor==1)return dividend;
if(divisor==-1)return 0-dividend;
bool isNegative=false;
if((dividend<0&&divisor>0)||(dividend>0&&divisor<0))isNegative=true; //判断正负
long long dend=dividend;
long long dsor=divisor;
long long totalSum=0; //为了防止越界情况的发生，使用long long类型
long long sum=0;
int totalCount=0;
int count=0;
if(dend<0)dend=abs(dend); //取正
if(dsor<0)dsor=abs(dsor);
while(sum+dsor<=dend-totalSum){
count=1;
sum=dsor;
while(sum+sum<=dend-totalSum){
sum+=sum;
count+=count;
}
totalSum+=sum;
totalCount+=count;
sum=0;
count=0;
}
if(isNegative)return 0-totalCount;
else return totalCount;
}
};
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。