h****e
发帖数: 928 | 1 LeetCode上的据说是Facebook的面试题：
Divide two integers without using multiplication, division and mod operator.
这要考虑正负数，还要考虑溢出的情况。看了解答还是觉得头大。 |
w****x
发帖数: 2483 | 2
operator.
恩, 除了这题还有一道电面题是字符串乘法, 15分钟
谁能在15分钟内写完那题我立马从图书馆8楼跳下去
【在 h****e 的大作中提到】
: LeetCode上的据说是Facebook的面试题：
: Divide two integers without using multiplication, division and mod operator.
: 这要考虑正负数，还要考虑溢出的情况。看了解答还是觉得头大。
|
l*********8
发帖数: 4642 | 3 整数除法为什么会有溢出？
operator.
【在 h****e 的大作中提到】
: LeetCode上的据说是Facebook的面试题：
: Divide two integers without using multiplication, division and mod operator.
: 这要考虑正负数，还要考虑溢出的情况。看了解答还是觉得头大。
|
g**********y
发帖数: 14569 | 4 你买降落伞吧。
在topcoder那儿做比赛的人，我可以肯定地说，至少1000人能在15分钟内写出无错可运
行代码。万一有一个逛到这个版。。。
【在 w****x 的大作中提到】
:
: operator.
: 恩, 除了这题还有一道电面题是字符串乘法, 15分钟
: 谁能在15分钟内写完那题我立马从图书馆8楼跳下去
|
a***g
发帖数: 234 | 5 似乎对runtime还有要求
我写过一个，judge large超时了。。。
球大牛完美版code
operator.
【在 h****e 的大作中提到】
: LeetCode上的据说是Facebook的面试题：
: Divide two integers without using multiplication, division and mod operator.
: 这要考虑正负数，还要考虑溢出的情况。看了解答还是觉得头大。
|
p*****2
发帖数: 21240 | 6 public int divide(int dividend, int divisor) // return c=a/b;
{
long a = dividend;
long b = divisor;
if (b == 0)
throw new ArithmeticException();
boolean neg = false;
if (a < 0)
neg = !neg;
if (b < 0)
neg = !neg;
a = Math.abs(a);
b = Math.abs(b);
int d = 0;
while (b << d <= a)
{
d++;
}
int c = 0;
for (int i = d; i >= 0; i--)
{
if (b << i <= a)
{
c |= 1 << i;
a -= b << i;
}
}
if (neg)
c = -c;
return c;
} |
p*****2
发帖数: 21240 | 7
对鸡牛来说就是3分钟的事情呀。
【在 g**********y 的大作中提到】
: 你买降落伞吧。
: 在topcoder那儿做比赛的人，我可以肯定地说，至少1000人能在15分钟内写出无错可运
: 行代码。万一有一个逛到这个版。。。
|
L***Q
发帖数: 508 | 8 二爷也是大牛……
【在 p*****2 的大作中提到】
:
: 对鸡牛来说就是3分钟的事情呀。
|
g*****e
发帖数: 64 | 9 问一个无关的，leetcode上现在还能看出来是哪个公司的题吗？好像从某一时间开始，
公司的tag的删了。 |
L***Q
发帖数: 508 | 10 除了leetcode，这儿还有一个我觉得挺有帮助的网站，也是有详细解答和code
http://www.geeksforgeeks.org/
【在 g*****e 的大作中提到】
: 问一个无关的，leetcode上现在还能看出来是哪个公司的题吗？好像从某一时间开始，
: 公司的tag的删了。
|
|
|
y**********u
发帖数: 6366 | 11 一般来说不会溢出把。。。
operator.
【在 h****e 的大作中提到】
: LeetCode上的据说是Facebook的面试题：
: Divide two integers without using multiplication, division and mod operator.
: 这要考虑正负数，还要考虑溢出的情况。看了解答还是觉得头大。
|
L***Q
发帖数: 508 | 12 这种情况会溢出：
a / b
a = INT_MIN
b = -1
得到的结果是INT_MAX + 1
【在 y**********u 的大作中提到】
: 一般来说不会溢出把。。。
:
: operator.
|
y**********u
发帖数: 6366 | 13 嗯，对的。。。
要考虑到这种情况，很不容易啊。。。
【在 L***Q 的大作中提到】
: 这种情况会溢出：
: a / b
: a = INT_MIN
: b = -1
: 得到的结果是INT_MAX + 1
|
L***Q
发帖数: 508 | 14 受leetcode大牛的启发，function内部结果用long long保存，方便判断溢出，返回时
候转换成int
【在 y**********u 的大作中提到】
: 嗯，对的。。。
: 要考虑到这种情况，很不容易啊。。。
|
y**********u
发帖数: 6366 | 15 但是long long也会溢出啊
哦，你的意思是用大的变量类型来保存
【在 L***Q 的大作中提到】
: 受leetcode大牛的启发，function内部结果用long long保存，方便判断溢出，返回时
: 候转换成int
|
L***Q
发帖数: 508 | 16 你如果是计算两个整数除法，function的参数是int，返回值也是int，内部就用一个更
大，能确保不溢出的变量。leetcode上面atoi的题就是如此，返回值是int，那么就用
long long来计算，返回前判断long long的值是不是已经超过int的范围。
【在 y**********u 的大作中提到】
: 但是long long也会溢出啊
: 哦，你的意思是用大的变量类型来保存
|
l****o
发帖数: 315 | |
l*********b
发帖数: 1541 | 18
同意。 至少还得搞几个垫子。 不需要编译运行的话我甚至觉得有人15秒能写出来。看
看那些最好纪录，简直太恐怖。
【在 g**********y 的大作中提到】
: 你买降落伞吧。
: 在topcoder那儿做比赛的人，我可以肯定地说，至少1000人能在15分钟内写出无错可运
: 行代码。万一有一个逛到这个版。。。
|
N**N
发帖数: 1713 | 19 15秒，光敲键盘的速度都没那么快把。。。。
【在 l*********b 的大作中提到】
:
: 同意。 至少还得搞几个垫子。 不需要编译运行的话我甚至觉得有人15秒能写出来。看
: 看那些最好纪录，简直太恐怖。
|
y*******g
发帖数: 6599 | 20 那些都是有template的
【在 l*********b 的大作中提到】
:
: 同意。 至少还得搞几个垫子。 不需要编译运行的话我甚至觉得有人15秒能写出来。看
: 看那些最好纪录，简直太恐怖。
|
|
|
i*********7
发帖数: 348 | 21 int divide(int a, int b)
{
bool flag = false;
if(((1 << 31) & a) != 0){
flag = !flag;
a = ~a + 1;
}
if(((1 << 31) & b) != 0){
flag = !flag;
b = ~b + 1;
}
int digitA = log2(a);
int digitB = log2(b);
cout<
int q = 0;
int msb = (digitA - digitB + 1);
for(int i = msb; i >= 0; i--)
{
if((b << i) > a)
{
continue;
}
q |= (1 << i);
a -= (b << i);
}
if(flag){
q = ~q + 1;
}
return q;
}
我原本做的用Bit operation来做的除法，刚才改了一下能跑正负数了。
至于考虑溢出。。不知道是不是要考虑long long int的情况？不然我还能改改？ |
h****e
发帖数: 928 | 22 LeetCode上的据说是Facebook的面试题：
Divide two integers without using multiplication, division and mod operator.
这要考虑正负数，还要考虑溢出的情况。看了解答还是觉得头大。 |
w****x
发帖数: 2483 | 23
operator.
恩, 除了这题还有一道电面题是字符串乘法, 15分钟
谁能在15分钟内写完那题我立马从图书馆8楼跳下去
【在 h****e 的大作中提到】
: LeetCode上的据说是Facebook的面试题：
: Divide two integers without using multiplication, division and mod operator.
: 这要考虑正负数，还要考虑溢出的情况。看了解答还是觉得头大。
|
l*********8
发帖数: 4642 | 24 整数除法为什么会有溢出？
operator.
【在 h****e 的大作中提到】
: LeetCode上的据说是Facebook的面试题：
: Divide two integers without using multiplication, division and mod operator.
: 这要考虑正负数，还要考虑溢出的情况。看了解答还是觉得头大。
|
g**********y
发帖数: 14569 | 25 你买降落伞吧。
在topcoder那儿做比赛的人，我可以肯定地说，至少1000人能在15分钟内写出无错可运
行代码。万一有一个逛到这个版。。。
【在 w****x 的大作中提到】
:
: operator.
: 恩, 除了这题还有一道电面题是字符串乘法, 15分钟
: 谁能在15分钟内写完那题我立马从图书馆8楼跳下去
|
a***g
发帖数: 234 | 26 似乎对runtime还有要求
我写过一个，judge large超时了。。。
球大牛完美版code
operator.
【在 h****e 的大作中提到】
: LeetCode上的据说是Facebook的面试题：
: Divide two integers without using multiplication, division and mod operator.
: 这要考虑正负数，还要考虑溢出的情况。看了解答还是觉得头大。
|
p*****2
发帖数: 21240 | 27 public int divide(int dividend, int divisor) // return c=a/b;
{
long a = dividend;
long b = divisor;
if (b == 0)
throw new ArithmeticException();
boolean neg = false;
if (a < 0)
neg = !neg;
if (b < 0)
neg = !neg;
a = Math.abs(a);
b = Math.abs(b);
int d = 0;
while (b << d <= a)
{
d++;
}
int c = 0;
for (int i = d; i >= 0; i--)
{
if (b << i <= a)
{
c |= 1 << i;
a -= b << i;
}
}
if (neg)
c = -c;
return c;
} |
p*****2
发帖数: 21240 | 28
对鸡牛来说就是3分钟的事情呀。
【在 g**********y 的大作中提到】
: 你买降落伞吧。
: 在topcoder那儿做比赛的人，我可以肯定地说，至少1000人能在15分钟内写出无错可运
: 行代码。万一有一个逛到这个版。。。
|
L***Q
发帖数: 508 | 29 二爷也是大牛……
【在 p*****2 的大作中提到】
:
: 对鸡牛来说就是3分钟的事情呀。
|
g*****e
发帖数: 64 | 30 问一个无关的，leetcode上现在还能看出来是哪个公司的题吗？好像从某一时间开始，
公司的tag的删了。 |
|
|
L***Q
发帖数: 508 | 31 除了leetcode，这儿还有一个我觉得挺有帮助的网站，也是有详细解答和code
http://www.geeksforgeeks.org/
【在 g*****e 的大作中提到】
: 问一个无关的，leetcode上现在还能看出来是哪个公司的题吗？好像从某一时间开始，
: 公司的tag的删了。
|
y**********u
发帖数: 6366 | 32 一般来说不会溢出把。。。
operator.
【在 h****e 的大作中提到】
: LeetCode上的据说是Facebook的面试题：
: Divide two integers without using multiplication, division and mod operator.
: 这要考虑正负数，还要考虑溢出的情况。看了解答还是觉得头大。
|
L***Q
发帖数: 508 | 33 这种情况会溢出：
a / b
a = INT_MIN
b = -1
得到的结果是INT_MAX + 1
【在 y**********u 的大作中提到】
: 一般来说不会溢出把。。。
:
: operator.
|
y**********u
发帖数: 6366 | 34 嗯，对的。。。
要考虑到这种情况，很不容易啊。。。
【在 L***Q 的大作中提到】
: 这种情况会溢出：
: a / b
: a = INT_MIN
: b = -1
: 得到的结果是INT_MAX + 1
|
L***Q
发帖数: 508 | 35 受leetcode大牛的启发，function内部结果用long long保存，方便判断溢出，返回时
候转换成int
【在 y**********u 的大作中提到】
: 嗯，对的。。。
: 要考虑到这种情况，很不容易啊。。。
|
y**********u
发帖数: 6366 | 36 但是long long也会溢出啊
哦，你的意思是用大的变量类型来保存
【在 L***Q 的大作中提到】
: 受leetcode大牛的启发，function内部结果用long long保存，方便判断溢出，返回时
: 候转换成int
|
L***Q
发帖数: 508 | 37 你如果是计算两个整数除法，function的参数是int，返回值也是int，内部就用一个更
大，能确保不溢出的变量。leetcode上面atoi的题就是如此，返回值是int，那么就用
long long来计算，返回前判断long long的值是不是已经超过int的范围。
【在 y**********u 的大作中提到】
: 但是long long也会溢出啊
: 哦，你的意思是用大的变量类型来保存
|
l****o
发帖数: 315 | |
l*********b
发帖数: 1541 | 39
同意。 至少还得搞几个垫子。 不需要编译运行的话我甚至觉得有人15秒能写出来。看
看那些最好纪录，简直太恐怖。
【在 g**********y 的大作中提到】
: 你买降落伞吧。
: 在topcoder那儿做比赛的人，我可以肯定地说，至少1000人能在15分钟内写出无错可运
: 行代码。万一有一个逛到这个版。。。
|
N**N
发帖数: 1713 | 40 15秒，光敲键盘的速度都没那么快把。。。。
【在 l*********b 的大作中提到】
:
: 同意。 至少还得搞几个垫子。 不需要编译运行的话我甚至觉得有人15秒能写出来。看
: 看那些最好纪录，简直太恐怖。
|
|
|
y*******g
发帖数: 6599 | 41 那些都是有template的
【在 l*********b 的大作中提到】
:
: 同意。 至少还得搞几个垫子。 不需要编译运行的话我甚至觉得有人15秒能写出来。看
: 看那些最好纪录，简直太恐怖。
|
i*********7
发帖数: 348 | 42 int divide(int a, int b)
{
bool flag = false;
if(((1 << 31) & a) != 0){
flag = !flag;
a = ~a + 1;
}
if(((1 << 31) & b) != 0){
flag = !flag;
b = ~b + 1;
}
int digitA = log2(a);
int digitB = log2(b);
cout<
int q = 0;
int msb = (digitA - digitB + 1);
for(int i = msb; i >= 0; i--)
{
if((b << i) > a)
{
continue;
}
q |= (1 << i);
a -= (b << i);
}
if(flag){
q = ~q + 1;
}
return q;
}
我原本做的用Bit operation来做的除法，刚才改了一下能跑正负数了。
至于考虑溢出。。不知道是不是要考虑long long int的情况？不然我还能改改？ |
n****r
发帖数: 471 | 43 用c++实现的，在leetcode上一跑就超时。
卡在
dividend = 2147483647
divisor = 1
Code 是：
int divide(int dividend, int divisor){
long a = dividend;
long b = divisor;
bool neg = false;
if(a < 0)
neg = !neg;
if(b < 0)
neg = !neg;
a = abs(a);
b = abs(b);
int d = 0;
while(b<
d++;
int c = 0;
for(int i = d; i >=0; i--){
if(b<
c |= 1 << i;
a -= b <
}
}
if(neg)
c = -c;
return c;
}
【在 p*****2 的大作中提到】
:
: 对鸡牛来说就是3分钟的事情呀。
|
H****s
发帖数: 247 | 44 divisor 是 1 你就单独判断吧，我还没想到更好的解法。
【在 n****r 的大作中提到】
: 用c++实现的，在leetcode上一跑就超时。
: 卡在
: dividend = 2147483647
: divisor = 1
: Code 是：
: int divide(int dividend, int divisor){
: long a = dividend;
: long b = divisor;
: bool neg = false;
: if(a < 0)
|
e***s
发帖数: 799 | 45 这种情况怎么搞呢，如果返回值是int
【在 L***Q 的大作中提到】
: 这种情况会溢出：
: a / b
: a = INT_MIN
: b = -1
: 得到的结果是INT_MAX + 1
|
H****s
发帖数: 247 | 46 内部用long long 处理，返回时再转换为int
【在 e***s 的大作中提到】
: 这种情况怎么搞呢，如果返回值是int
|
n***e
发帖数: 723 | 47 但是longlong强制转换int的话不就成0了么？
edit:不好意思，强制转换后，是minint吧
【在 H****s 的大作中提到】
: 内部用long long 处理，返回时再转换为int
|
H****s
发帖数: 247 | 48 要自己加判断， 大于INT_MAX则返回INT_MAX
【在 n***e 的大作中提到】
: 但是longlong强制转换int的话不就成0了么？
: edit:不好意思，强制转换后，是minint吧
|
s***y
发帖数: 203 | |
y****n
发帖数: 743 | 50 如果不考虑正负和溢出，一行代码的事。
public static int Div(Int64 a, Int64 b, ref Int64 m)
{
return a >= b << 1 ? (Div(a, b << 1, ref m) << 1) + Div(m, b, ref m) : a
>= b ? (m = a - b) > 0 ? 1 : 1 : (m = a) > 0 ? 0 : 0;
}
public static Int64 Div(Int64 a, Int64 b)
{
if (b == 0)
throw new Exception("Div By 0");
else if ((a == Int64.MinValue) && (b == -1))
throw new Exception("Overflow");
bool neg = (Math.Sign(a) != Math.Sign(b));
Int64 mod = 0;
Int64 result = Div(a, b, ref mod);
return neg ? -result : result;
} |
|
|
w****a
发帖数: 710 | 51 我想知道这题这么写，面试会算你过么？？
我发誓我没用用"运算符"
int divide(int dividend, int divisor)
{
int result = 0;
__asm
{
mov eax,dividend
cdq
idiv divisor
mov result,eax
}
return result;
} |
w********p
发帖数: 948 | 52 如果是电面老老实实的写减法，没有overflow的担心，然后再告诉他可以用bit运算提
高应该也是可以过的吧。如果是bug free 的code |
j*****y
发帖数: 1071 | 53 bit ?
a / b 的 的除法可以做到 log(b / a) 的复杂度吧
【在 w********p 的大作中提到】
: 如果是电面老老实实的写减法，没有overflow的担心，然后再告诉他可以用bit运算提
: 高应该也是可以过的吧。如果是bug free 的code
|
w********p
发帖数: 948 | 54 public static int Div(Int64 a, Int64 b, ref Int64 m)
这个方程的实现很有可能被认为coding style 不好，看起来，改起来都麻烦。不如多
写几行的好。
我认识的人中确实有题都做出来，但是因为coding style被dream company拒掉的。
code 要简洁加上易懂，易维护。
a
【在 y****n 的大作中提到】
: 如果不考虑正负和溢出，一行代码的事。
: public static int Div(Int64 a, Int64 b, ref Int64 m)
: {
: return a >= b << 1 ? (Div(a, b << 1, ref m) << 1) + Div(m, b, ref m) : a
: >= b ? (m = a - b) > 0 ? 1 : 1 : (m = a) > 0 ? 0 : 0;
: }
: public static Int64 Div(Int64 a, Int64 b)
: {
: if (b == 0)
: throw new Exception("Div By 0");
|
w********p
发帖数: 948 | 55 我只是认同一个很牛朋友的看法。无bug的解决问题，比有bug的最好算法，更容易pass
interview.
用减法做，速度不是最快的，但是没有overflow的担心。10 分钟写出无bug的code是可
行的。
用bit operation做，更快些，但是对于多数人来说，很难做到10－15分钟内写出无bug
的code.
版上也有人说过面试的时候不要先功最好的算法，而是给出安全的code，再提高。
当然超牛，15秒落地的人随便咋写啦。
【在 j*****y 的大作中提到】
: bit ?
: a / b 的 的除法可以做到 log(b / a) 的复杂度吧
|
y****n
发帖数: 743 | 56 完全同意你的观点，这个是自己写着玩儿，面试时当然不能这样写。
改良了一下style：
递归O(log(a/b))，没有位运算，忽略负数和除零和溢出情况。
public static int Div(UInt64 a, UInt64 b, ref UInt64 mod)
{
UInt64 b2 = b + b;
if (a >= b2)
{
int r1 = Div(a, b2, ref mod);
int r2 = Div(mod, b, ref mod);
return r1 + r1 + r2;
}
else if (a >= b)
{
mod = a - b;
return 1;
}
else
{
mod = a;
return 0;
}
}
【在 w********p 的大作中提到】
: public static int Div(Int64 a, Int64 b, ref Int64 m)
: 这个方程的实现很有可能被认为coding style 不好，看起来，改起来都麻烦。不如多
: 写几行的好。
: 我认识的人中确实有题都做出来，但是因为coding style被dream company拒掉的。
: code 要简洁加上易懂，易维护。
:
: a
|
w********p
发帖数: 948 | 57 赞。学习。。。
【在 y****n 的大作中提到】
: 完全同意你的观点，这个是自己写着玩儿，面试时当然不能这样写。
: 改良了一下style：
: 递归O(log(a/b))，没有位运算，忽略负数和除零和溢出情况。
: public static int Div(UInt64 a, UInt64 b, ref UInt64 mod)
: {
: UInt64 b2 = b + b;
: if (a >= b2)
: {
: int r1 = Div(a, b2, ref mod);
: int r2 = Div(mod, b, ref mod);
|
y****n
发帖数: 743 | 58 这个观点我不太同意。
至少这道题如果用纯减法做，几乎没有通过的可能。
首先，该overflow时自然会overflow，减法也会overflow。
其次，面试中我们必须要考虑算法的实用价值。
比如有人算(2^64)/1，纯减法会算上百年。
当然，我们也并不需要在15分钟之内找到神乎其技的超级算法。
至少应该展示“我在努力优化”。
pass
bug
【在 w********p 的大作中提到】
: 我只是认同一个很牛朋友的看法。无bug的解决问题，比有bug的最好算法，更容易pass
: interview.
: 用减法做，速度不是最快的，但是没有overflow的担心。10 分钟写出无bug的code是可
: 行的。
: 用bit operation做，更快些，但是对于多数人来说，很难做到10－15分钟内写出无bug
: 的code.
: 版上也有人说过面试的时候不要先功最好的算法，而是给出安全的code，再提高。
: 当然超牛，15秒落地的人随便咋写啦。
|
b***i
发帖数: 3043 | 59 减法难道不是一边移位一边减?
【在 y****n 的大作中提到】
: 这个观点我不太同意。
: 至少这道题如果用纯减法做，几乎没有通过的可能。
: 首先，该overflow时自然会overflow，减法也会overflow。
: 其次，面试中我们必须要考虑算法的实用价值。
: 比如有人算(2^64)/1，纯减法会算上百年。
: 当然，我们也并不需要在15分钟之内找到神乎其技的超级算法。
: 至少应该展示“我在努力优化”。
:
: pass
: bug
|
w****a
发帖数: 710 | |
|
|
b***i
发帖数: 3043 | 61 32位整数的除法当然最多减32次就行了，也就是移位32次。或者说自加32次，比较32次。
其实就是a/b是几位2进制，就最多移几次。
【在 w****a 的大作中提到】
: 减法不需要移位吧
|
b***i
发帖数: 3043 | 62 不用long 也行。直接用负数做，哪怕是正数也变负数。
【在 L***Q 的大作中提到】
: 受leetcode大牛的启发，function内部结果用long long保存，方便判断溢出，返回时
: 候转换成int
|
j*****y
发帖数: 1071 | 63 nice.
【在 y****n 的大作中提到】
: 完全同意你的观点，这个是自己写着玩儿，面试时当然不能这样写。
: 改良了一下style：
: 递归O(log(a/b))，没有位运算，忽略负数和除零和溢出情况。
: public static int Div(UInt64 a, UInt64 b, ref UInt64 mod)
: {
: UInt64 b2 = b + b;
: if (a >= b2)
: {
: int r1 = Div(a, b2, ref mod);
: int r2 = Div(mod, b, ref mod);
|
j*****y
发帖数: 1071 | 64 感觉这个复杂度是 (log(a/b))^2 阿？
【在 y****n 的大作中提到】
: 完全同意你的观点，这个是自己写着玩儿，面试时当然不能这样写。
: 改良了一下style：
: 递归O(log(a/b))，没有位运算，忽略负数和除零和溢出情况。
: public static int Div(UInt64 a, UInt64 b, ref UInt64 mod)
: {
: UInt64 b2 = b + b;
: if (a >= b2)
: {
: int r1 = Div(a, b2, ref mod);
: int r2 = Div(mod, b, ref mod);
|
y****n
发帖数: 743 | 65 复杂度是O(log(a/b))。
你可以用Div((UInt64)1 << n, 1, mod)试验一下, n in [0..63]。
递归最深层次为n，递归次数为2n。
我前面贴的代码包含一个bug，当b >= 2^63时会溢出，导致堆栈溢出。
这是修复版。（bug free不容易呀）
public static UInt64 Div(UInt64 a, UInt64 b, ref UInt64 mod)
{
UInt64 b2 = b + b;
if ((b2 > b) && (a >= b2))
{
UInt64 r1 = Div(a, b2, ref mod);
UInt64 r2 = Div(mod, b, ref mod);
return r1 + r1 + r2;
}
else if (a >= b)
{
mod = a - b;
return 1;
}
else
{
mod = a;
return 0;
}
}
【在 j*****y 的大作中提到】
: 感觉这个复杂度是 (log(a/b))^2 阿？
|
j*****y
发帖数: 1071 | 66 b 是 int 类型，不会出现 b >= 2^63的情况吧
你的那个递归里面call 了两个 子递归, 感觉说复杂度只是 O(log(a/b))有点不太像
【在 y****n 的大作中提到】
: 复杂度是O(log(a/b))。
: 你可以用Div((UInt64)1 << n, 1, mod)试验一下, n in [0..63]。
: 递归最深层次为n，递归次数为2n。
: 我前面贴的代码包含一个bug，当b >= 2^63时会溢出，导致堆栈溢出。
: 这是修复版。（bug free不容易呀）
: public static UInt64 Div(UInt64 a, UInt64 b, ref UInt64 mod)
: {
: UInt64 b2 = b + b;
: if ((b2 > b) && (a >= b2))
: {
|
y****n
发帖数: 743 | 67 在我新贴的代码中，纠正了所有的整数类型为 UInt64。
你可以在代码中加个计数器，数一下就知道了。
【在 j*****y 的大作中提到】
: b 是 int 类型，不会出现 b >= 2^63的情况吧
: 你的那个递归里面call 了两个 子递归, 感觉说复杂度只是 O(log(a/b))有点不太像
|
n****r
发帖数: 471 | 68 用c++实现的，在leetcode上一跑就超时。
卡在
dividend = 2147483647
divisor = 1
Code 是：
int divide(int dividend, int divisor){
long a = dividend;
long b = divisor;
bool neg = false;
if(a < 0)
neg = !neg;
if(b < 0)
neg = !neg;
a = abs(a);
b = abs(b);
int d = 0;
while(b<
d++;
int c = 0;
for(int i = d; i >=0; i--){
if(b<
c |= 1 << i;
a -= b <
}
}
if(neg)
c = -c;
return c;
}
【在 p*****2 的大作中提到】
:
: 对鸡牛来说就是3分钟的事情呀。
|
H****s
发帖数: 247 | 69 divisor 是 1 你就单独判断吧，我还没想到更好的解法。
【在 n****r 的大作中提到】
: 用c++实现的，在leetcode上一跑就超时。
: 卡在
: dividend = 2147483647
: divisor = 1
: Code 是：
: int divide(int dividend, int divisor){
: long a = dividend;
: long b = divisor;
: bool neg = false;
: if(a < 0)
|
e***s
发帖数: 799 | 70 这种情况怎么搞呢，如果返回值是int
【在 L***Q 的大作中提到】
: 这种情况会溢出：
: a / b
: a = INT_MIN
: b = -1
: 得到的结果是INT_MAX + 1
|
|
|
H****s
发帖数: 247 | 71 内部用long long 处理，返回时再转换为int
【在 e***s 的大作中提到】
: 这种情况怎么搞呢，如果返回值是int
|
n***e
发帖数: 723 | 72 但是longlong强制转换int的话不就成0了么？
edit:不好意思，强制转换后，是minint吧
【在 H****s 的大作中提到】
: 内部用long long 处理，返回时再转换为int
|
H****s
发帖数: 247 | 73 要自己加判断， 大于INT_MAX则返回INT_MAX
【在 n***e 的大作中提到】
: 但是longlong强制转换int的话不就成0了么？
: edit:不好意思，强制转换后，是minint吧
|
s***y
发帖数: 203 | |
y****n
发帖数: 743 | 75 如果不考虑正负和溢出，一行代码的事。
public static int Div(Int64 a, Int64 b, ref Int64 m)
{
return a >= b << 1 ? (Div(a, b << 1, ref m) << 1) + Div(m, b, ref m) : a
>= b ? (m = a - b) > 0 ? 1 : 1 : (m = a) > 0 ? 0 : 0;
}
public static Int64 Div(Int64 a, Int64 b)
{
if (b == 0)
throw new Exception("Div By 0");
else if ((a == Int64.MinValue) && (b == -1))
throw new Exception("Overflow");
bool neg = (Math.Sign(a) != Math.Sign(b));
Int64 mod = 0;
Int64 result = Div(a, b, ref mod);
return neg ? -result : result;
} |
w****a
发帖数: 710 | 76 我想知道这题这么写，面试会算你过么？？
我发誓我没用用"运算符"
int divide(int dividend, int divisor)
{
int result = 0;
__asm
{
mov eax,dividend
cdq
idiv divisor
mov result,eax
}
return result;
} |
w********p
发帖数: 948 | 77 如果是电面老老实实的写减法，没有overflow的担心，然后再告诉他可以用bit运算提
高应该也是可以过的吧。如果是bug free 的code |
j*****y
发帖数: 1071 | 78 bit ?
a / b 的 的除法可以做到 log(b / a) 的复杂度吧
【在 w********p 的大作中提到】
: 如果是电面老老实实的写减法，没有overflow的担心，然后再告诉他可以用bit运算提
: 高应该也是可以过的吧。如果是bug free 的code
|
w********p
发帖数: 948 | 79 public static int Div(Int64 a, Int64 b, ref Int64 m)
这个方程的实现很有可能被认为coding style 不好，看起来，改起来都麻烦。不如多
写几行的好。
我认识的人中确实有题都做出来，但是因为coding style被dream company拒掉的。
code 要简洁加上易懂，易维护。
a
【在 y****n 的大作中提到】
: 如果不考虑正负和溢出，一行代码的事。
: public static int Div(Int64 a, Int64 b, ref Int64 m)
: {
: return a >= b << 1 ? (Div(a, b << 1, ref m) << 1) + Div(m, b, ref m) : a
: >= b ? (m = a - b) > 0 ? 1 : 1 : (m = a) > 0 ? 0 : 0;
: }
: public static Int64 Div(Int64 a, Int64 b)
: {
: if (b == 0)
: throw new Exception("Div By 0");
|
w********p
发帖数: 948 | 80 我只是认同一个很牛朋友的看法。无bug的解决问题，比有bug的最好算法，更容易pass
interview.
用减法做，速度不是最快的，但是没有overflow的担心。10 分钟写出无bug的code是可
行的。
用bit operation做，更快些，但是对于多数人来说，很难做到10－15分钟内写出无bug
的code.
版上也有人说过面试的时候不要先功最好的算法，而是给出安全的code，再提高。
当然超牛，15秒落地的人随便咋写啦。
【在 j*****y 的大作中提到】
: bit ?
: a / b 的 的除法可以做到 log(b / a) 的复杂度吧
|
|
|
y****n
发帖数: 743 | 81 完全同意你的观点，这个是自己写着玩儿，面试时当然不能这样写。
改良了一下style：
递归O(log(a/b))，没有位运算，忽略负数和除零和溢出情况。
public static int Div(UInt64 a, UInt64 b, ref UInt64 mod)
{
UInt64 b2 = b + b;
if (a >= b2)
{
int r1 = Div(a, b2, ref mod);
int r2 = Div(mod, b, ref mod);
return r1 + r1 + r2;
}
else if (a >= b)
{
mod = a - b;
return 1;
}
else
{
mod = a;
return 0;
}
}
【在 w********p 的大作中提到】
: public static int Div(Int64 a, Int64 b, ref Int64 m)
: 这个方程的实现很有可能被认为coding style 不好，看起来，改起来都麻烦。不如多
: 写几行的好。
: 我认识的人中确实有题都做出来，但是因为coding style被dream company拒掉的。
: code 要简洁加上易懂，易维护。
:
: a
|
w********p
发帖数: 948 | 82 赞。学习。。。
【在 y****n 的大作中提到】
: 完全同意你的观点，这个是自己写着玩儿，面试时当然不能这样写。
: 改良了一下style：
: 递归O(log(a/b))，没有位运算，忽略负数和除零和溢出情况。
: public static int Div(UInt64 a, UInt64 b, ref UInt64 mod)
: {
: UInt64 b2 = b + b;
: if (a >= b2)
: {
: int r1 = Div(a, b2, ref mod);
: int r2 = Div(mod, b, ref mod);
|
y****n
发帖数: 743 | 83 这个观点我不太同意。
至少这道题如果用纯减法做，几乎没有通过的可能。
首先，该overflow时自然会overflow，减法也会overflow。
其次，面试中我们必须要考虑算法的实用价值。
比如有人算(2^64)/1，纯减法会算上百年。
当然，我们也并不需要在15分钟之内找到神乎其技的超级算法。
至少应该展示“我在努力优化”。
pass
bug
【在 w********p 的大作中提到】
: 我只是认同一个很牛朋友的看法。无bug的解决问题，比有bug的最好算法，更容易pass
: interview.
: 用减法做，速度不是最快的，但是没有overflow的担心。10 分钟写出无bug的code是可
: 行的。
: 用bit operation做，更快些，但是对于多数人来说，很难做到10－15分钟内写出无bug
: 的code.
: 版上也有人说过面试的时候不要先功最好的算法，而是给出安全的code，再提高。
: 当然超牛，15秒落地的人随便咋写啦。
|
b***i
发帖数: 3043 | 84 减法难道不是一边移位一边减?
【在 y****n 的大作中提到】
: 这个观点我不太同意。
: 至少这道题如果用纯减法做，几乎没有通过的可能。
: 首先，该overflow时自然会overflow，减法也会overflow。
: 其次，面试中我们必须要考虑算法的实用价值。
: 比如有人算(2^64)/1，纯减法会算上百年。
: 当然，我们也并不需要在15分钟之内找到神乎其技的超级算法。
: 至少应该展示“我在努力优化”。
:
: pass
: bug
|
w****a
发帖数: 710 | |
b***i
发帖数: 3043 | 86 32位整数的除法当然最多减32次就行了，也就是移位32次。或者说自加32次，比较32次。
其实就是a/b是几位2进制，就最多移几次。
【在 w****a 的大作中提到】
: 减法不需要移位吧
|
b***i
发帖数: 3043 | 87 不用long 也行。直接用负数做，哪怕是正数也变负数。
【在 L***Q 的大作中提到】
: 受leetcode大牛的启发，function内部结果用long long保存，方便判断溢出，返回时
: 候转换成int
|
j*****y
发帖数: 1071 | 88 nice.
【在 y****n 的大作中提到】
: 完全同意你的观点，这个是自己写着玩儿，面试时当然不能这样写。
: 改良了一下style：
: 递归O(log(a/b))，没有位运算，忽略负数和除零和溢出情况。
: public static int Div(UInt64 a, UInt64 b, ref UInt64 mod)
: {
: UInt64 b2 = b + b;
: if (a >= b2)
: {
: int r1 = Div(a, b2, ref mod);
: int r2 = Div(mod, b, ref mod);
|
j*****y
发帖数: 1071 | 89 感觉这个复杂度是 (log(a/b))^2 阿？
【在 y****n 的大作中提到】
: 完全同意你的观点，这个是自己写着玩儿，面试时当然不能这样写。
: 改良了一下style：
: 递归O(log(a/b))，没有位运算，忽略负数和除零和溢出情况。
: public static int Div(UInt64 a, UInt64 b, ref UInt64 mod)
: {
: UInt64 b2 = b + b;
: if (a >= b2)
: {
: int r1 = Div(a, b2, ref mod);
: int r2 = Div(mod, b, ref mod);
|
y****n
发帖数: 743 | 90 复杂度是O(log(a/b))。
你可以用Div((UInt64)1 << n, 1, mod)试验一下, n in [0..63]。
递归最深层次为n，递归次数为2n。
我前面贴的代码包含一个bug，当b >= 2^63时会溢出，导致堆栈溢出。
这是修复版。（bug free不容易呀）
public static UInt64 Div(UInt64 a, UInt64 b, ref UInt64 mod)
{
UInt64 b2 = b + b;
if ((b2 > b) && (a >= b2))
{
UInt64 r1 = Div(a, b2, ref mod);
UInt64 r2 = Div(mod, b, ref mod);
return r1 + r1 + r2;
}
else if (a >= b)
{
mod = a - b;
return 1;
}
else
{
mod = a;
return 0;
}
}
【在 j*****y 的大作中提到】
: 感觉这个复杂度是 (log(a/b))^2 阿？
|
|
|
j*****y
发帖数: 1071 | 91 b 是 int 类型，不会出现 b >= 2^63的情况吧
你的那个递归里面call 了两个 子递归, 感觉说复杂度只是 O(log(a/b))有点不太像
【在 y****n 的大作中提到】
: 复杂度是O(log(a/b))。
: 你可以用Div((UInt64)1 << n, 1, mod)试验一下, n in [0..63]。
: 递归最深层次为n，递归次数为2n。
: 我前面贴的代码包含一个bug，当b >= 2^63时会溢出，导致堆栈溢出。
: 这是修复版。（bug free不容易呀）
: public static UInt64 Div(UInt64 a, UInt64 b, ref UInt64 mod)
: {
: UInt64 b2 = b + b;
: if ((b2 > b) && (a >= b2))
: {
|
y****n
发帖数: 743 | 92 在我新贴的代码中，纠正了所有的整数类型为 UInt64。
你可以在代码中加个计数器，数一下就知道了。
【在 j*****y 的大作中提到】
: b 是 int 类型，不会出现 b >= 2^63的情况吧
: 你的那个递归里面call 了两个 子递归, 感觉说复杂度只是 O(log(a/b))有点不太像
|
b****g
发帖数: 192 | 93 复杂度确实是O(log(a/b))吧，虽然递归了，但是递归之前的和之后的是分开的又合并
了，所以还是lg那么多
【在 j*****y 的大作中提到】
: b 是 int 类型，不会出现 b >= 2^63的情况吧
: 你的那个递归里面call 了两个 子递归, 感觉说复杂度只是 O(log(a/b))有点不太像
|
h********e
发帖数: 1972 | 94 高精度乘除法。。15-20分钟肯定写得完。。除法就写个减法模块就行了。乘法也就是
个加法模块。。
fb没考算法题已经很优待了 |
