题目出处
题目描述
个人解法
思路：
todo
代码示例：（Java）
todo
复杂度分析
todo
官方解法
方法1：二分查找
思路：
代码示例：（Java）
public class Solution1 {
public int divide(int dividend, int divisor) {
// 考虑被除数为最小值的情况
if (dividend == Integer.MIN_VALUE) {
if (divisor == 1) {
return Integer.MIN_VALUE;
}
if (divisor == -1) {
return Integer.MAX_VALUE;
}
}
// 考虑除数为最小值的情况
if (divisor == Integer.MIN_VALUE) {
return dividend == Integer.MIN_VALUE ? 1 : 0;
}
// 考虑被除数为 0 的情况
if (dividend == 0) {
return 0;
}
// 一般情况，使用二分查找
// 将所有的正数取相反数，这样就只需要考虑一种情况
boolean rev = false;
if (dividend > 0) {
dividend = -dividend;
rev = !rev;
}
if (divisor > 0) {
divisor = -divisor;
rev = !rev;
}
int left = 1, right = Integer.MAX_VALUE, ans = 0;
while (left <= right) {
// 注意溢出，并且不能使用除法
int mid = left + ((right - left) >> 1);
boolean check = quickAdd(divisor, mid, dividend);
if (check) {
ans = mid;
// 注意溢出
if (mid == Integer.MAX_VALUE) {
break;
}
left = mid + 1;
} else {
right = mid - 1;
}
}
return rev ? -ans : ans;
}
// 快速乘
public boolean quickAdd(int y, int z, int x) {
// x 和 y 是负数，z 是正数
// 需要判断 z * y >= x 是否成立
int result = 0, add = y;
while (z != 0) {
if ((z & 1) != 0) {
// 需要保证 result + add >= x
if (result < x - add) {
return false;
}
result += add;
}
if (z != 1) {
// 需要保证 add + add >= x
if (add < x - add) {
return false;
}
add += add;
}
// 不能使用除法
z >>= 1;
}
return true;
}
}
复杂度分析
方法2:类二分查找
思路：
代码示例：（Java）
public class Solution2 {
public int divide(int dividend, int divisor) {
// 考虑被除数为最小值的情况
if (dividend == Integer.MIN_VALUE) {
if (divisor == 1) {
return Integer.MIN_VALUE;
}
if (divisor == -1) {
return Integer.MAX_VALUE;
}
}
// 考虑除数为最小值的情况
if (divisor == Integer.MIN_VALUE) {
return dividend == Integer.MIN_VALUE ? 1 : 0;
}
// 考虑被除数为 0 的情况
if (dividend == 0) {
return 0;
}
// 一般情况，使用类二分查找
// 将所有的正数取相反数，这样就只需要考虑一种情况
boolean rev = false;
if (dividend > 0) {
dividend = -dividend;
rev = !rev;
}
if (divisor > 0) {
divisor = -divisor;
rev = !rev;
}
List<Integer> candidates = new ArrayList<Integer>();
candidates.add(divisor);
int index = 0;
// 注意溢出
while (candidates.get(index) >= dividend - candidates.get(index)) {
candidates.add(candidates.get(index) + candidates.get(index));
++index;
}
int ans = 0;
for (int i = candidates.size() - 1; i >= 0; --i) {
if (candidates.get(i) >= dividend) {
ans += 1 << i;
dividend -= candidates.get(i);
}
}
return rev ? -ans : ans;
}
}
复杂度分析
考察知识点
1.对数运算
2.位运算
收获
1.算法的高度是和jdk等源码是一个高度的，用最朴素的方法实现想要的功能，而不是简单的api使用工程师
2.排序算法是很多算法的基础
3.软件行业的很多思想放在生活中也很实用，比如分治法、中间层法（没有什么问题是加一层解决不了的）等
4.理论和实践都很重要，相对于枯燥的理论，我更喜欢用代码说话。俗话说：Talk is cheap，show me the code！
这也是我每一篇文章坚持都有代码的原因。
