a***e 发帖数: 413 | 1 Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.
这个Ccp150上那种做法(也就是我一开始做的直接减的方法会TLE)
是不是说明现在面试要求比以前高很多?
还在试图在原来的code上面改变以加快
class Solution {
public:
int divide(int dividend, int divisor) {
if (divisor==0) return INT_MAX;
int r=0;
if (dividend==0) return r;
int flag=sign(dividend)*sign(divisor);
dividend=abs(dividend);
divisor=abs(divisor);
dividend=dividend-divisor;
while(dividend>=0)
{
r++;
dividend=dividend-divisor;
}
return flag>0?r:-r;
}
int sign(int num)
{
if (num>0)
return 1;
else if (num<0)
return -1;
else
return 0;
}
}; |
a***e 发帖数: 413 | 2 看到soulmachine的答案说
‘最简单的方法,是不断减去被除数。在这个基础上,可以做一点优化,每次把被除数
翻倍,从
而加速。’
不太懂为啥可以用这个翻倍除数来加速。看那个code也是有点晕。
int divide(int dividend, int divisor) {
// 当dividend = INT_MIN 时,-dividend 会溢出,所以用long long
long long a = dividend >= 0 ? dividend : -(long long)dividend;
long long b = divisor >= 0 ? divisor : -(long long)divisor;
// 当dividend = INT_MIN 时,divisor = -1 时,结果会溢出,所以用long long
long long result = 0;
while (a >= b) {
long long c = b;
for (int i = 0; a >= c; ++i, c <<= 1) {
a -= c;
result += 1 << i;
}
}
return ((dividend^divisor) >> 31) ? (-result) : (result);
} |
s*******g 发帖数: 170 | 3 只有这样才能实现O(logN)的速度。
【在 a***e 的大作中提到】 : 看到soulmachine的答案说 : ‘最简单的方法,是不断减去被除数。在这个基础上,可以做一点优化,每次把被除数 : 翻倍,从 : 而加速。’ : 不太懂为啥可以用这个翻倍除数来加速。看那个code也是有点晕。 : int divide(int dividend, int divisor) { : // 当dividend = INT_MIN 时,-dividend 会溢出,所以用long long : long long a = dividend >= 0 ? dividend : -(long long)dividend; : long long b = divisor >= 0 ? divisor : -(long long)divisor; : // 当dividend = INT_MIN 时,divisor = -1 时,结果会溢出,所以用long long
|
i******t 发帖数: 22541 | 4 每次dividend ×2 , 直到 大于等于 divisor
这题我想主要是
1 边际处理
2 overflow
话说 overflow 怎么处理? |
r******t 发帖数: 250 | 5 soulmachine...这人也够无良的 在 leetcode 旧 discuss 上找了一些还可以的题解编
成自己的书
也不注明出处 还顺便把别人的题解加个 creative commons 的版权声明
【在 a***e 的大作中提到】 : 看到soulmachine的答案说 : ‘最简单的方法,是不断减去被除数。在这个基础上,可以做一点优化,每次把被除数 : 翻倍,从 : 而加速。’ : 不太懂为啥可以用这个翻倍除数来加速。看那个code也是有点晕。 : int divide(int dividend, int divisor) { : // 当dividend = INT_MIN 时,-dividend 会溢出,所以用long long : long long a = dividend >= 0 ? dividend : -(long long)dividend; : long long b = divisor >= 0 ? divisor : -(long long)divisor; : // 当dividend = INT_MIN 时,divisor = -1 时,结果会溢出,所以用long long
|
a***e 发帖数: 413 | 6 通过的code,但不清楚怎么能证明这个是对的,有人知道怎么证明吗?
长除法也可以写,但没这么简洁。
class Solution {
public:
int divide(int dividend, int divisor) {
if (divisor==0) return INT_MAX;
long long r=0;
if (dividend==0) return r;
if (-1==divisor) return (-(long long int)dividend>INT_MAX? INT_MAX :
-(long long int)dividend);
long long a = dividend>=0?dividend:-(long long)dividend;
long long b = divisor>=0?divisor:-(long long)divisor;
while(a>=b)
{
long long c=b;
for (int i=0; a>=c; i++,c=c<<1)
{
a-=c;
r+=1<
}
}
return (dividend<0^divisor<0)?-r:r;
}
}; |