LeetCode第[29]题(Java):Divide Two Integers
题目:两整数相除
难度:Medium
题目内容:
Given two integers dividend
and divisor
, divide two integers without using multiplication, division and mod operator.
Return the quotient after dividing dividend
by divisor
.
The integer division should truncate toward zero.
翻译:
给定两个整数,被除数和除数,不使用乘法,除法和mod运算符。
在除以除数后,返回商数。
整数除法应该截断为零。
Example 1:
Input: dividend = 10, divisor = 3
Output: 3
Example 2:
Input: dividend = 7, divisor = -3
Output: -2
我的思路:因为此题需要考虑的边界情况太多,而重点考察的却不是这些,故只做算法分析,不求跑通所有代码。
最笨的方法:直接循环减去除数。。。
方法二:之前印象中好像在哪见过,每次循环都减去能减的最大的除数*2^n,并且每次循环把2次幂都加起来。商就是这些2次幂的和。
举个例子:20/3,
第一次循环,20>3*1,20>3*2,20>3*2*2,已经最大,打住, dividend=20-3*2*2=8, ans = 2*2 = 4
第二次循环,8>3*1,8>3*2,已经最大,打住, dividend=8-3*2=2, ans = 4 + 2 = 6
dividend < 3 退出循环,最后 ans = 6
MyCode:
public int divide(int dividend, int divisor) {
if (dividend != 0 && dividend == -dividend && divisor == -1) {
return -(dividend+1);
}
return div(dividend, divisor);
}
public static int div(int x, int y) {
int tag = 1;
if ((x ^ y) < 0) { // 位运算符优先级很低,记得加括号
tag = -1;
if (x < 0) {
x = -x;
} else {
y = -y;
}
} else if (x < 0) {
x = -x;
y = -y;
} // 都设置成正整数
int ans = 0;
while (x >= y) {
int flag = 1;
while ((x >> 1) >= y * flag) { // 如果使用x >= y * (flag << 1) 则有可能溢出
flag <<= 1;
}
x -= y*flag;
ans += flag;
}
return ans*tag;
}
编码过程中出现问题:
1、bad operand types for binary operator “^”
————位运算符的优先级很低,甚至比==都要低,所以遇见位运算符要记得加括号。
2、溢出
————在23行处,进行了>>1(乘以2)的判断运算,此时可能溢出,所以在进行判断运算时,即先运算再判断是否能如此运算的时候,应该将判断符(==、>=等)两边的运算符平衡一下,如果一边可能溢出,则将此运算符移至另一边。【此处与之前的leetCode的某一题貌似是 数字反转 很像】
答案代码:
public int divide(int dividend, int divisor) {
if(dividend<<1 == 0 && divisor == -1){// x /y = -2^32 / -1, overflow
return (-1) >>> 1;
} if(divisor == 1 || dividend == 0){ // x / y = x / 1 or 0 / y
return dividend;
}
if(divisor == dividend) return 1; // x / y when x == y
else if(divisor<<1 == 0) return 0; // x / y = x / (-2^32) int sign; //sign
if(divisor < 0 && dividend < 0 || divisor > 0 && dividend > 0){
sign = 1;
}else{
sign = -1;
} divisor = divisor < 0 ? -divisor : divisor; // positive divisor
int left = dividend, res = 0;
if(dividend << 1 == 0){ // if x / y = (-2^32) / y, first we add x by y, then -x will not overflow
left += divisor;
res++;
}
left = left > 0 ? left : -left; int tDivisor = divisor, tA = 1;
while(left >= divisor){
tDivisor = divisor;
tA = 1;
while(tDivisor << 1 > 0 && left >= tDivisor << 1){ // max tDivisor = tA * divisor <= left
tDivisor <<= 1;
tA <<= 1;
}
res += tA;
left -= tDivisor;
}
return sign == 1 ? res : -res;
}
其实真正的代码从27行开始,和我代码是一个意思,不过前面多出了很多处理边界的情况,在此不做讨论。
另外一种方法——二分法:
和朋友讨论发现另外一种巧妙地解法,用二分法:
public static int div2(int x, int y) {
int tag = 1;
if ((x ^ y) < 0) { // 位运算符优先级很低,记得加括号
tag = -1;
if (x < 0) {
x = -x;
} else {
y = -y;
}
} else if (x < 0) {
x = -x;
y = -y;
}
int ans = 0; // 算法从此处开始
int low = 1;
int high = x;
while (low <= high) {
int mid = low + ((high-low)>>1);
int rest = x - y*mid;
System.out.println(rest);
if (rest >= 0 && rest < y) {
ans = mid;
break;
}
if (rest < 0) {
high = mid - 1;
} else if (rest >= y) {
low = mid + 1;
}
}
return ans * tag;
}
最新文章
- js执行跨域请求
- JavaScript编码规范[百度]
- Codeforces Round #260 (Div. 2)AB
- (转)javascript中event对象详解
- Ubuntu ENet 的下载和编译
- K3Cloud单据转换获取源单数据
- 超级强大的vim配置(vimplus)
- 重写session
- Windows 环境下基于 nginx 的本地 PyPI 源
- Struts2 学习笔记20 类型转换part2 写自己的转换器
- BootStrap入门教程 (四)
- Jquery总结图
- 【一天一道LeetCode】#68. Text Justification
- JavaScript中var、let和const的区别(转载)
- webstorm快捷键 webstorm keymap内置快捷键英文翻译、中英对照说明
- 数据库启动windows
- Java访问文件夹中文件的递归遍历代码Demo
- 【图像基础】图像不变性特征HU矩和Zernike矩
- 315道Python面试题答案
- SQL Server中float转字符串进度丢失