做网站的企业广州,wordpress恢复数据库文件,wordpress 项目,自动下单网站开发内容介绍 给你两个整数#xff0c;被除数 dividend 和除数 divisor。将两数相除#xff0c;要求 不使用 乘法、除法和取余运算。 整数除法应该向零截断#xff0c;也就是截去#xff08;truncate#xff09;其小数部分。例如#xff0c;8.345 将被截断为 8 #xff0c;-…内容介绍 给你两个整数被除数 dividend 和除数 divisor。将两数相除要求 不使用 乘法、除法和取余运算。 整数除法应该向零截断也就是截去truncate其小数部分。例如8.345 将被截断为 8 -2.7335 将被截断至 -2 。 返回被除数 dividend 除以除数 divisor 得到的 商 。 注意假设我们的环境只能存储 32 位 有符号整数其数值范围是 [−231, 231 − 1] 。本题中如果商 严格大于 231 − 1 则返回 231 − 1 如果商 严格小于 -231 则返回 -231 。 示例 1: 输入: dividend 10, divisor 3
输出: 3
解释: 10/3 3.33333.. 向零截断后得到 3 。 示例 2: 输入: dividend 7, divisor -3
输出: -2
解释: 7/-3 -2.33333.. 向零截断后得到 -2 。 提示 -231 dividend, divisor 231 - 1divisor ! 0 完整代码 class Solution {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;}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) {int result 0, add y;while (z ! 0) {if ((z 1) ! 0) {if (result x - add) {return false;}result add;}if (z ! 1) {if (add x - add) {return false;}add add;}z 1;}return true;}
}
思路详解
整体思路
该代码实现了一个整数除法功能主要解决以下问题
处理特殊边界情况如被除数或除数为整数最小值。处理除数为0的情况。通过二分查找确定商的大小。使用快速乘法判断二分查找中的中间值是否满足条件。
详细步骤 处理特殊边界情况 当被除数为Integer.MIN_VALUE时需要单独处理除数为1和-1的情况因为直接计算会导致溢出。当除数为Integer.MIN_VALUE时只有当被除数也是Integer.MIN_VALUE时商为1否则为0。 处理除数为0的情况 当被除数为0时直接返回0。 统一处理负数 将被除数和除数都转换为负数这样只需考虑一种情况。同时记录转换次数最后根据转换次数确定返回值的正负。 二分查找确定商的大小 初始化左边界为1右边界为Integer.MAX_VALUE。在二分查找过程中计算中间值mid并使用快速乘法判断mid * divisor是否大于等于dividend。如果满足条件更新答案ans并将左边界更新为mid 1否则将右边界更新为mid - 1。 快速乘法 由于不能使用除法使用快速乘法来判断mid * divisor是否大于等于dividend。通过位运算和加法模拟乘法操作同时避免溢出。
代码注释说明
rev记录被除数和除数转换为负数的次数用于最后确定返回值的正负。quickAdd快速乘法函数用于判断y * z是否大于等于x。left、right、ans二分查找的左边界、右边界和当前答案。mid二分查找的中间值。check用于判断mid * divisor是否大于等于dividend。
知识点精炼
特殊情况处理
整数最小值处理Integer.MIN_VALUE作为被除数或除数的情况防止溢出。除数为0明确除数为0时结果为0。
负数统一处理
符号转换将被除数和除数统一转换为负数简化问题处理。符号记录使用布尔变量记录被除数和除数的符号转换次数以确定最终结果的符号。
二分查找
查找范围初始化左边界为1右边界为Integer.MAX_VALUE。中间值计算使用位运算计算中间值避免溢出。条件判断通过快速乘法判断中间值是否满足条件。
快速乘法
位运算利用位运算模拟乘法操作避免直接使用乘法导致溢出。加法替代通过加法累加结果判断是否满足条件。
防溢出
边界检查在计算过程中确保不发生溢出。无除法全程不使用除法操作避免因除法导致的精度问题。
