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;
}
}; |
