力扣题 - 29 解析大佬题解

用户头像
Geek_663541
关注
发布于: 2020 年 08 月 21 日
力扣题 - 29  解析大佬题解

题目:

给定两个整数,被除数 dividend 和除数 divisor。

将两数相除,要求不使用乘法、除法和 mod 运算符

返回被除数 dividend 除以除数 divisor 得到的商。

整数除法的结果应当截去(truncate)其小数部分,例如:truncate(8.345) = 8 以及 truncate(-2.7335) = -2

示例 1:

输入: dividend = 10, divisor = 3

输出: 3

解释: 10/3 = truncate(3.33333..) = truncate(3) = 3

示例 2:



输入: dividend = 7, divisor = -3

输出: -2

解释: 7/-3 = truncate(-2.33333..) = -2

提示:

被除数和除数均为 32 位有符号整数。

除数不为 0。

假设我们的环境只能存储 32 位有符号整数,其数值范围是 [−231,  231 − 1]。本题中,如果除法结果溢出,则返回 231 − 1。



来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/divide-two-integers



思考:

1.观察 题目 题目要求 要求不使用乘法、除法和 mod 运算符。 加法 减法没 限制

2.既然 是 做 除法 就 有 除数 得 整数除法的结果应当截去(truncate)其小数部分

3.除数不为 0 但是 被除数 小于 除数 返回 0

4.范围 也是 十分 重要 的

5.关键怎么不用 除法 做 除法

题目表示不能用乘法、除法, 那加法 和 减法 没限制

怎么实现 :

例如: 11-3 -> 11 - (3+3) -> 11-(3+3+3) -> { 11-(3+3+3+3) 超过}

得 11/3 = 3



大神题解:https://leetcode-cn.com/problems/divide-two-integers/solution/po-su-de-xiang-fa-mei-you-wei-yun-suan-mei-you-yi-/



下面也不是原创,解析评论区:

/**
* 如何实现除法 保留 整数 可以 11/2 -> (11/2+2) -> (11/(2+2+2)) ....
* 参考: https://leetcode-cn.com/problems/divide-two-integers/solution/po-su-de-xiang-fa-mei-you-wei-yun-suan-mei-you-yi-/
*/
public int divide(int dividend, int divisor) { // 被除数 除数
// 负 / 负 = 正 负数最大 值超过 整数 最大
if (divisor == -1 && dividend == Integer.MIN_VALUE)
return Integer.MAX_VALUE;
//正负
int sign = 1;
//判断 异号
if ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0))
sign = -1;
//判断 除数是否 等于 1或-1 1除以任何数都是任何数
if (divisor == 1) return dividend;
if (divisor == -1) return -dividend;
//都变成负号 因为不会越界 前面已经 判断过了 防止溢出
//都改为负号是因为int 的范围是[-2^32, 2^32-1],如果a是-2^32,转为正数时将会溢出
int a = dividend > 0 ? -dividend : dividend;
int b = divisor > 0 ? -divisor : divisor;
//除数 大于 被除数 很小
if (a > b) return 0;//a>b 都是负数 例如 -1>-2 = 0
int ans = div(a, b);//调用div方法
//判断 进行 给符号
return sign == -1 ? -ans : ans;
}
//a,b 是负数 正数例子:11/3 -> 11>3 -> 11>(3+3) -> 11>(3+3+3) -> 11<(3+3+3+3)
//快一点的方法 11/3-> 11>3 -> 11>(3+3) -> 11>((3+3)+(3+3)) ? 没有 11 - (上一次没超过的值) (3+3)= 5
// a=5 5/3 5> (3+3) ? 没有 1
int div(int a, int b) {
//-3>-8 =0
if (a > b) return 0;//递归 停止 条件
int count = 1;//为什么次数默认是1 例如:4/3 =1 所以小于就是必须默认是 1
int tb = b;//tb 是 相对 负数是大的
//每次 b的进阶版 b+b -> 2b+2b tb+tb 就是 负数+负数 会接近 a >=a 的意思 因为是负数 被除数是小的
while (tb + tb >= a && tb + tb < 0) { // 溢出之后不再小于0
tb += tb;//加倍
count += count;//count 次数?
}
//为什么还要递归 a-tb 因为 tb +tb 大于 a
return count + div(a - tb, b);
}



本篇结束---

用户头像

Geek_663541

关注

游离的魂 2020.08.15 加入

游离的魂 悬浮行尸上

评论

发布
暂无评论
力扣题 - 29  解析大佬题解