leetcode
leetcode 2901 ~ 2950
两数相除

两数相除

难度:

标签:

题目描述

English description is not available for the problem. Please switch to Chinese.

代码结果

运行时间: 22 ms, 内存: 15.9 MB


/* 
 题目思路: 
 1. 由于使用 Java Stream 不太适合处理这种逻辑复杂的操作,这里提供一种非传统的方式,使用 Stream API 中的 iterate 方法来模拟除法。 
 2. 使用类似的移位和减法操作来实现除法的功能。 
 */ 
import java.util.stream.Stream; 
public class Solution { 
    public int divide(int a, int b) { 
        if (b == 0) { 
            return Integer.MAX_VALUE; 
        } 
        if (a == Integer.MIN_VALUE && b == -1) { 
            return Integer.MAX_VALUE; 
        } 
        boolean negative = (a > 0 && b < 0) || (a < 0 && b > 0); 
        a = -Math.abs(a); 
        b = -Math.abs(b); 
        int[] result = new int[1]; 
        Stream.iterate(new int[]{a, b, 1}, x -> x[0] <= x[1] << 1, x -> new int[]{x[0], x[1] << 1, x[2] << 1}) 
                .forEach(x -> { 
                    if (x[0] <= x[1]) { 
                        x[0] -= x[1]; 
                        result[0] += x[2]; 
                    } 
                }); 
        return negative ? -result[0] : result[0]; 
    } 
}

解释

方法:

此题解采用位操作和减法来实现除法。首先,确定结果的符号(正或负),接着将被除数和除数都转化为绝对值。利用循环和位移操作(左移相当于乘以2),动态地增加除数,使其尽可能接近被除数,同时累积对应的倍数。每次循环结束时,从被除数中减去当前增加的除数,并累加计算得到的商。最后,根据最初确定的符号调整结果。如果结果溢出32位整型范围,则返回最大或最小值。

时间复杂度:

O((log(n))^2)

空间复杂度:

O(1)

代码细节讲解

🦆
题解中提到'每次循环中,被除数a通过位移被减少至少一半',能否详细解释为什么每次位移操作后,t的值就能保证是a的一半?
题解中的表述可能有误导,事实上位移操作是为了快速找到不超过a的最大的t的倍数。在每次循环中,t从除数b开始,通过左移(乘以2)逐步增加,直到t的下一个翻倍会超过a。因此,当找到最大的不超过a的t时,这个t不一定是a的一半,而是在不超过a的范围内最接近a的t的倍数。每次减去这样的t后,a至少减少了原来的b,而不是减少到原来的一半。
🦆
在这个算法中使用位移操作来模拟乘法,请问如果位移后的t值超过了被除数a,这种情况是如何处理的?
在算法中,如果位移后的t值超过了被除数a,位移操作会停止,并退回到最后一次未超过a的t值。随后,这个t值会从a中被减去,相应的倍数n也累加到结果res中。之后,a和t都会重新调整,t重新设置为除数b,n重置为1,再次进行循环和位移操作,直到a小于b为止。
🦆
在处理符号的逻辑中,如果输入的a或b是最小的32位整数,如-2^31,转换为绝对值时可能会出现什么问题?
在Python中,整数类型可以自动扩展,因此理论上不会直接溢出。但在其他一些编程语言中,如C++或Java,32位整数的范围是从-2^31到2^31-1。当尝试将-2^31转换为其正数形式时,由于2^31超出了正数的最大范围,会导致溢出。在Python中,虽然不会溢出,但这种情况需要特别注意,因为它可能在其他语言的实现中引发问题。

相关问题