Given two integersExample：dividendanddivisor, divide two integers without using multiplication, division and mod operator.
Return the quotient after dividingdividendbydivisor.
The integer division should truncate toward zero.
Input: dividend = 10, divisor = 3
Output: 3
Input: dividend = 7, divisor = -3Note：
Output: -2
Both dividend and divisor will be解释下题目：32-bitsigned integers.
The divisor will never be0.
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [?2^31, 2^31 ? 1]. For the purpose of this problem, assume that your function returns 2^31 ? 1 when the division result overflows.
实现计算机除法，用int足够了，而且除数不会是01. 老实做 实际耗时：超时
public int divide(int dividend, int divisor) {
int result = 0;
if (0 == dividend) {
return 0;
}
if (dividend == Integer.MIN_VALUE && divisor == -1) {
return Integer.MAX_VALUE;
}if (dividend > 0 && divisor > 0) {
//相当于 10/3
while (dividend >= 0) {
dividend -= divisor;
result++;
}
result--;
} else if (dividend < 0 && divisor > 0) {
//相当于 -10/3
while (dividend <= 0) {
dividend += divisor;
result--;
}
result++;
} else if (dividend > 0 && divisor < 0) {
//相当于 10/-3
while (dividend >= 0) {
dividend += divisor;
result--;
}
result++;
} else {
//相当于 -10/-3
while (dividend <= 0) {
dividend -= divisor;
result++;
}
result--;
}
return result;
}
??思路很简单，就是把除数化为减法，不停去做就行了。当然这么暴力，显然没过。。。。
时间复杂度O(a) a=答案 空间复杂度O(1) 2. 类似二分法的思想 实际耗时：xxms
public int divide(int dividend, int divisor) {
if (dividend == Integer.MIN_VALUE && divisor == -1) {
return Integer.MAX_VALUE;
}
if (dividend > 0 && divisor > 0) {
return divideHelper(-dividend, -divisor);
} else if (dividend > 0) {
return -divideHelper(-dividend, divisor);
} else if (divisor > 0) {
return -divideHelper(dividend, -divisor);
} else {
return divideHelper(dividend, divisor);
}
}private int divideHelper(int dividend, int divisor) {
//首先处理被除数小于除数的问题
if (divisor < dividend) {
return 0;
}
//得到可以除的最大的
int cur = 0, res = 0;
while ((divisor << cur) >= dividend && divisor << cur < 0 && cur < 31) {
cur++;
}
res = dividend - (divisor << cur - 1);
if (res > divisor) {
return 1 << cur - 1;
}
return (1 << cur - 1) + divide(res, divisor);
}
【029|029 Divide Two Integers】??思路就是我先不断扩大除数，然后就把这个最大的除数去除被除数，剩下的余数我在用相同的方法去做，把它们相加即可。
时间复杂度O(logn) 空间复杂度O(1)
