企业官网网站建设上海,网站开发人员趋势,怎么从阿里巴巴做网站,网页设计如何报价题意 给你两个整数#xff0c;被除数 dividend 和除数 divisor。将两数相除#xff0c;要求不使用乘法、除法和取余运算。 整数除法应该向零截断#xff0c;也就是截去#xff08;truncate#xff09;其小数部分。例如#xff0c;8.345 将被截断为 8 #xff0c;-2.7335…题意 给你两个整数被除数 dividend 和除数 divisor。将两数相除要求不使用乘法、除法和取余运算。 整数除法应该向零截断也就是截去truncate其小数部分。例如8.345 将被截断为 8 -2.7335 将被截断至 -2 。 返回被除数 dividend 除以除数 divisor 得到的商。 难度 中等 示例 输入: dividend 10, divisor 3 输出: 3 解释: 10/3 3.33333.. 向零截断后得到 3 。 输入: dividend 7, divisor -3 输出: -2 解释: 7/-3 -2.33333.. 向零截断后得到 -2 。 分析 1 题目要求不能用除法/也不能用乘法*还有 “取余%”如果我们偏要用除法会怎么样呢
class Solution {public int divide(int dividend, int divisor) {// 直接使用除法计算结果long result (long) dividend / divisor;// 处理溢出情况if (result Integer.MAX_VALUE) {return Integer.MAX_VALUE;}if (result Integer.MIN_VALUE) {return Integer.MIN_VALUE;}return (int) result;}} 来看一下运行结果 其实有时候我们真解不出来的话多多少少先把答案写上去运行通过但遇到大数就不会成功。 分析 2 题目要求不能用除法不过我们处理溢出情况的写法后面还是要用到的尤其是 (long) dividend 这个强转的处理其实就考察了基本数据类型的转换问题包括最后返回的 (int) result都是很细节的问题但却很重要。 那既然不能用除法我们应该怎么去计算两数相除呢 用减法。 除法基本上是减法的逆运算它表示将一个数被除数分成几个相等的部分除数时可以得到多少个这样的部分商。如果用减法来实现除法本质上是在问“我可以从被除数中减去多少次除数”每减去一次就相当于得到了一个单位的商。 假设我们要计算 dividend / divisor quotient被除数 / 除数 商其中 dividend 和 divisor 是已知的我们要找到 quotient。 ①、初始化计数器设置一个计数器 count初始值为 0。这个计数器将用来记录我们能从被除数中减去多少次除数。 ②、循环减除数只要被除数 dividend 大于或等于除数 divisor就从被除数中减去除数并且计数器 count 加一。
while (dividend divisor) {dividend - divisor;count;
} ③、处理剩余部分当被除数小于除数时循环结束。此时count 的值就是整数除法的结果商而此时的 dividend 是除法的余数。
假设我们要计算 10 / 3 初始时dividend 10divisor 3count 0。10 3执行减法 10 - 3 7count 1。7 3再次执行减法 7 - 3 4count 2。4 3再次执行减法 4 - 3 1count 3。此时1 3循环结束count 3 是商1 是余数。 我们来试一下直接用 ACM 的模式在 Intellij IDEA 中打印结果 public class TwoDivide {public static void main(String[] args) {// int divide divide1(10, 3);
// System.out.println(divide);System.out.println(divide1(10, 3));System.out.println(divide1(7, -3));System.out.println(divide1(0, 1));System.out.println(divide1(1, 1));System.out.println(divide1(1, 0));System.out.println(divide1(-2147483648, -1));}public static int divide1( int dividend , int divisor){// 处理特殊情况if (dividend Integer.MIN_VALUE divisor -1) {return Integer.MAX_VALUE;}// 符号处理boolean negative (dividend 0) ^ (divisor 0);long ldividend Math.abs((long)dividend);long ldivisor Math.abs((long)divisor);long result 0;while (ldividend ldivisor) {ldividend - ldivisor;result;}return negative ? (int)-result : (int)result;} 很遗憾前 5 个测试用例都是可以顺利通过的但最后 1 个测试用例耗时会特别长因为要计算 2147483648 / 1次这个数太大了所以我们要想办法优化一下。 优化减法实现除法的关键在于减少需要执行的减法操作次数对吧 我们可以结合减法和倍增思想每次减去 divisor 的倍数这样就可以减少减法的次数。 初始时令一个临时除数等于除数每次尝试从被除数中减去临时除数。如果可以减去更新被除数减去临时除数临时除数倍增乘以 2同时记录下减去的次数。如果不可以减去则临时除数回退到除数继续尝试减去直到被除数小于除数。 public static int divide2( int dividend , int divisor){// 处理特殊情况if (dividend Integer.MIN_VALUE divisor -1) {return Integer.MAX_VALUE;}// 符号处理boolean negative (dividend 0) ^ (divisor 0);long ldividend Math.abs((long)dividend);long ldivisor Math.abs((long)divisor);long result 0;while (ldividend ldivisor){long tempDivisor ldivisor , multilpe 1;//将除数加倍并记录加的倍数while (ldividend tempDivisortempDivisor){tempDivisor tempDivisor; //加倍除数multilpe multilpe; //累加倍数}ldividend-tempDivisor; //减去加倍后的除数resultmultilpe;}return negative ? (int)-result : (int)result;} 内层 while 循环确定能够从被除数中减去的最大的除数的倍数。 这个循环通过不断地加倍除数乘以 2寻找最接近且不超过被除数的那个除数的倍数。这个过程实际上是在模拟除法的过程尝试找到一个合适的倍数使得除数 × 倍数 ≤ 被除数且尽可能地大。 while (ldividend tempDivisor tempDivisor) {tempDivisor tempDivisor; // 加倍除数multiple multiple; // 记录加倍次数
}
tempDivisor 从原始的除数开始每次循环加倍相当于tempDivisor * 2试图接近但不超过 ldividend。multiple 记录了加倍的次数也就是说如果 tempDivisor 加倍了那么 multiple 也加倍表示除数增加了多少倍。
外层 while 循环使用上一个循环确定的最大倍数来更新被除数并累加到最终结果中。 当第一个循环结束后我们找到了最接近且不超过被除数的那个除数的倍数。然后我们从被除数中减去这个加倍后的除数并将对应的倍数累加到最终结果中。如果更新后的被除数仍然大于或等于原始除数这个过程会重复进行。 ldividend-tempDivisor;//减去加倍后的除数
resultmultiple;//累加倍数 ldividend - tempDivisor;更新被除数减去了找到的最大可减的加倍后的除数。result multiple;将这一步中减去的除数的倍数累加到 result 中因为这表示了我们在这一步中“除以了多少个”除数。 来看一下运行效率还挺高 分析 3 减法和倍增的另外一种变体就是使用位移我们来看一下题解 public int divide3(int dividend, int divisor) {if (dividend Integer.MIN_VALUE divisor -1) {return Integer.MAX_VALUE; // 防止溢出}boolean negative (dividend 0) ^ (divisor 0);long ldividend Math.abs((long)dividend);long ldivisor Math.abs((long)divisor);long result 0;while (ldividend ldivisor) {long temp ldivisor, multiple 1;while (ldividend (temp 1)) {temp 1;multiple 1;}ldividend - temp;result multiple;}return negative ? (int)-result : (int)result;}
在二进制表示中每向左移动一位其实就等价于将这个数乘以 2。所以我们可以通过位移来实现倍增。
while (ldividend (temp 1)) {temp 1;multiple 1;
} 假设 temp 的值为 3其二进制表示为 0011这里为了简化只展示了四位二进制。当执行 temp 1 操作时temp 的二进制表示会向左移动一位变为 0110此时 temp 的值就变成了 6。可以看到3 * 2 6这正是位左移一位的效果。 分析 4 我们还可以使用二分法来实现除法这个方法是最优的也是最常用的。 二分法的思路是我们可以将除数不断地向左移位直到它大于被除数。因为这样可以最大限度地减小被除数使得被除数减去除数的次数最少。 我们来看一下题解
class Solution {public int divide(int dividend, int divisor) {// 处理特殊情况Integer.MIN_VALUE除以-1会溢出if (dividend Integer.MIN_VALUE divisor -1) {return Integer.MAX_VALUE;}// 使用异或运算确定结果的正负性不同号为负boolean negative (dividend 0) ^ (divisor 0);// 将被除数和除数都转换为正数使用long类型避免溢出long ldividend Math.abs((long)dividend);long ldivisor Math.abs((long)divisor);// 初始化结果变量long result 0;// 从最高位开始检查对32位整数而言这是31位for (int i 31; i 0; i--) {// 检查ldividend右移i位后是否仍然大于等于ldivisorif ((ldividend i) ldivisor) {// 如果是说明在2^i的位置上有一个ldivisor将2^i累加到结果中result 1L i;// 同时从ldividend中减去ldivisor左移i位的值即减去了ldivisor的2^i倍ldividend - ldivisor i;}}// 根据之前确定的正负性返回正确的结果return negative ? (int)-result : (int)result;}
}
public int divide4(int dividend, int divisor) {if (dividend Integer.MIN_VALUE divisor -1) {return Integer.MAX_VALUE; // 防止溢出}boolean negative (dividend 0) ^ (divisor 0);long ldividend Math.abs((long)dividend);long ldivisor Math.abs((long)divisor);long result 0;//从最高位开始检查对32位整数而言这是31位for (int i 31 ;i 0 ; i--){//检查ldividend右移i位后是否仍大于等于ldivisorif (ldividendi ldivisor){//如果是说明在i^2的位置上有一个ldivisor将i^2累加到结果中result1 i ;ldividend- ldivisor i;}}// 根据之前确定的正负性返回正确的结果return negative ? (int)-result : (int)result;}这个题解虽然没有直接采用传统的二分搜索算法框架但它实质上利用了二分思想的核心——每次操作都在减少搜索范围逐步逼近目标值。 在这个问题中目标是找到一个数x使得x * divisor ≈ dividend。通过位操作每次将dividend右移实际上是在缩小搜索范围。 这个过程可以看作是对商的二进制表示的逐位确认 高位到低位逼近从dividend的最高位开始逐步向下检查每一位看在当前位上divisor是否能放入。这里“放入”的意思是看乘以2^i通过左移i位实现后的divisor是否不超过当前的dividend。这相当于在二分搜索的每一步中决定这一位上的商是0还是1。动态调整搜索范围通过不断地调整ldividend即减去已经确定能够放入的divisor的倍数实际上是在缩小搜索范围因为每次操作后的ldividend代表了尚未被除尽的余数。 总结 在数学中加法是加减乘除的基础减法是加法的逆运算乘法是加法的倍增除法是乘法的逆运算。 两数相乘可以用加法来实现两数相除可以用减法来实现这是最基本的思路。 比如说 10/2我们可以用 10-2-2-2-2-20 来实现这样就得到了商 5。 比如说 10/3我们可以用 10-3-3-3-10 来实现这样就得到了商 3 余 1。
