由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - leetcode: Divide Two Integers 怎么做?
相关主题
leecode上的divide two integers问题问一个facebook的电面题
Divide Two Integers OJ和CCP150的做法Divide Two Integers
M 家电面G等消息中 求bless
leetcode上的2个整数相除最近onsite的时候刚拿到一道面试题?
divide two integersDivide Two Integers Answer 超时
Help, Algorithms questions问一道 ama的除法题
关于Divide a integer关于除法的问题
讨论一道面试题两整数相除问题
相关话题的讨论汇总
话题: long话题: divisor话题: dividend话题: ret话题: int
进入JobHunting版参与讨论
1 (共1页)
h**o
发帖数: 548
1
题目: Divide two integers without using multiplication, division and mod
operator.
应该是怎么做哪?leetcode 有个人气解答如下,但是我看不懂, 有谁给解释一下你怎
么做的?
int divide(int dividend, int divisor) {
long long a = abs((double)dividend);;
long long b = abs((double)divisor);
long long ret = 0;
while (a >= b) {
long long c = b;
for (int i = 0; a >= c; ++i, c <<= 1) {
a -= c;
ret += 1 << i;
}
}
return ((dividend^divisor)>>31) ? (-ret) : (ret);
}
o**f
发帖数: 76
2
Line 2/3 ignore sign of dividend/divisor.
Line 5 to 12 try to remove divisor (or multiple of
divisors) from dividend, until a becomes < b.
Note that line 8 c<<=1 is bit operation and so does
line 10 ret += 1 < Line 14 check signs of dividend/divisor, if they are
same, return ret. Otherwise, return -1 * ret.
1 int divide(int dividend, int divisor) {
2 long long a = abs((double)dividend);;
3 long long b = abs((double)divisor);
4
5 long long ret = 0;
6 while (a >= b) {
7 long long c = b;
8 for (int i = 0; a >= c; ++i, c <<= 1) {
9 a -= c;
10 ret += 1 << i;
11 }
12 }
13
14 return ((dividend^divisor)>>31) ? (-ret) : (ret);
15 }
z****e
发帖数: 54598
3
public class Solution {
public int divide(int dividend, int divisor) {
// Start typing your Java solution below
// DO NOT write main() function
if(dividend == 0) return 0;
long a = Math.abs((long)dividend);
long b = Math.abs((long)divisor);
long[] result = div(a,b);
long r = ((dividend>0&&divisor<0)||(dividend<0&&divisor>0))?-result[
0]:result[0];
return (int)r;
}
private long[] div(long a, long b){
long[] r = new long[2];
if(a r[0] = 0;
r[1] = a;
}else if(a==b){
r[0] = 1;
r[1] = 0;
}else{
long[] result = div(a>>1,b);
r[0] = result[0]<<1;
r[1] = result[1]<<1;
if((a&1)==1) r[1]+=1;
if(r[1]>=b){
r[0]+=1;
r[1]-=b;
}
}
return r;
}
}
h****g
发帖数: 105
4
最主要的思想就是如果你一个一个的去计算被除数里包含多少哥除数的话,在极端例子
下比如INT_MAX/1, 时间复杂度会很高。那么怎么做才能更快呢?就是让除数指数级的
自增(c<<1),直到下一次double比被除数大为止。假设此时被除数b自增到c, 那么商
可以分为两部分,一部分是c里包含有多少个b,另一个是a-c里包含有多少个b。前者我
们已经用ret记录好了,后者可以重复第一步的步骤
h**o
发帖数: 548
5
明白了。 谢谢大牛们。
请问我贴的方法 time complexity 是 [(log(dividend/divisor)]^2 吧。

【在 h****g 的大作中提到】
: 最主要的思想就是如果你一个一个的去计算被除数里包含多少哥除数的话,在极端例子
: 下比如INT_MAX/1, 时间复杂度会很高。那么怎么做才能更快呢?就是让除数指数级的
: 自增(c<<1),直到下一次double比被除数大为止。假设此时被除数b自增到c, 那么商
: 可以分为两部分,一部分是c里包含有多少个b,另一个是a-c里包含有多少个b。前者我
: 们已经用ret记录好了,后者可以重复第一步的步骤

h**o
发帖数: 548
6
明白了。 谢谢大牛们。
请问我贴的方法 time complexity 是 [(log(dividend/divisor)]^2 吧。

【在 h****g 的大作中提到】
: 最主要的思想就是如果你一个一个的去计算被除数里包含多少哥除数的话,在极端例子
: 下比如INT_MAX/1, 时间复杂度会很高。那么怎么做才能更快呢?就是让除数指数级的
: 自增(c<<1),直到下一次double比被除数大为止。假设此时被除数b自增到c, 那么商
: 可以分为两部分,一部分是c里包含有多少个b,另一个是a-c里包含有多少个b。前者我
: 们已经用ret记录好了,后者可以重复第一步的步骤

c********p
发帖数: 1969
7
你邮箱满了?

result[

【在 z****e 的大作中提到】
: public class Solution {
: public int divide(int dividend, int divisor) {
: // Start typing your Java solution below
: // DO NOT write main() function
: if(dividend == 0) return 0;
: long a = Math.abs((long)dividend);
: long b = Math.abs((long)divisor);
: long[] result = div(a,b);
: long r = ((dividend>0&&divisor<0)||(dividend<0&&divisor>0))?-result[
: 0]:result[0];

1 (共1页)
进入JobHunting版参与讨论
相关主题
两整数相除问题divide two integers
一道qualcomm面試題Help, Algorithms questions
Leetcode Divide two integers 的题关于Divide a integer
Divide Two Integers讨论一道面试题
leecode上的divide two integers问题问一个facebook的电面题
Divide Two Integers OJ和CCP150的做法Divide Two Integers
M 家电面G等消息中 求bless
leetcode上的2个整数相除最近onsite的时候刚拿到一道面试题?
相关话题的讨论汇总
话题: long话题: divisor话题: dividend话题: ret话题: int