Justice's Site

两数相除

 滴水穿石  189  1 分钟

两数相除

CategoryDifficultyLikesDislikes
algorithmsMedium (22.21%)1147-
Tags

math | binary-search

Companies

Unknown

给你两个整数，被除数 dividend 和除数 divisor。将两数相除，要求 不使用 乘法、除法和取余运算。

整数除法应该向零截断，也就是截去（truncate）其小数部分。例如，8.345 将被截断为 8 ，-2.7335 将被截断至 -2 。

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

注意： 假设我们的环境只能存储 32 位 有符号整数，其数值范围是 [−2<sup>31</sup>,  2<sup>31 </sup>− 1] 。本题中，如果商 严格大于 2<sup>31 </sup>− 1 ，则返回 2<sup>31 </sup>− 1 ；如果商 严格小于 -2<sup>31</sup> ，则返回 -2<sup>31</sup> ^ ^ 。

示例 1:

1
2
3

输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = 3.33333.. ，向零截断后得到 3 。

示例 2:

1
2
3

输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = -2.33333.. ，向零截断后得到 -2 。

提示：

  • -2<sup>31</sup> <= dividend, divisor <= 2<sup>31</sup> - 1
  • divisor != 0

Discussion | Solution

解法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

struct Solution;

// @lc code=start
impl Solution {
    /// ## 解题思路
    /// - 二分
    /// 1. 先处理符号，被除数、除数都取绝对值；
    /// 2. 试着将除数逐渐翻倍，直到比被除数大为止，记翻倍次数为n，此时结果应该在(n/2, n)之间;
    /// 3. 从n/2开始，依次
    pub fn divide(dividend: i32, divisor: i32) -> i32 {
        let negative = (dividend < 0) != (divisor < 0);
        let (mut dividend, mut divisor) = (i64::from(dividend).abs(), i64::from(divisor).abs());
        let mut n = 1;
        let mut res = 0_i64;
        //将divisor依次左移，直到大于diviend（快增长）
        while (divisor << 1) <= dividend {
            divisor <<= 1;      //除数
            n <<= 1;            //记录倍数
        }
        //(慢试探)
        while n > 0 {
            if dividend >= divisor {
                res += n;
                dividend -= divisor;
            }
            divisor >>= 1;
            n >>= 1;
        }

        if negative {
            -res as i32
        } else {
            res.min(i64::from(i32::MAX)) as i32
        }
    }
}
// @lc code=end

相关文章：