【剑指Offer】整数（一）整数除法 - 两数相除 - JavaScript

时间：2024-12-20 07:36:46

嗨！~ 大家好，我是YK菌 ???? ，一个微系前端 ✨，爱思考，爱总结，爱记录，爱分享 ????，欢迎关注我呀 ???? ~ [微信公众号：YK菌]

在这里插入图片描述

从今天开始我们一起来刷《剑指offer（专项突破版）》，原书是Java版本的，这里就是以JavaScript角度来看这些算法题。

剑指 Offer II 001. 整数除法

此题与LeetCode主站的 29. 两数相除 相同

题目描述

给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%' 。

  • 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
  • 假设我们的环境只能存储 32 32 32 位有符号整数，其数值范围是 [ − 2 31 , 2 31 − 1 ] [−2^{31}, 2^{31}−1] [−231,231−1]。
  • 本题中，如果除法结果溢出，则返回 2 31 − 1 2^{31} − 1 231−1

回顾JavaScript中的数字类型

不像别的语言数字分整数和浮点数，在JavaScript中只有一个数字类型。它是一个双精度的64位的number。Number 类型使用IEEE 754格式表示整数和浮点值。

由内置数字类型表示的整数限制最大值是 2 53 − 1 2^{53} - 1 253−1 用Number.MAX_SAFE_INTEGER来表示；最小值是 − 2 53 + 1 -2^{53} + 1 −253+1 Number.MIN_SAFE_INTEGER。

Number.MAX_SAFE_INTEGER === 9007199254740991
Number.MIN_SAFE_INTEGER === -9007199254740991
  • 1
  • 2

在这种情况下，安全性指的是该值不能是存在舍入（round）误差的结果。

这些不安全的值在 +1或者-1（舍入）之后，会远离安全的值。任何加法或减法都会导致结果的舍入。

let a = Number.MAX_SAFE_INTEGER
console.log(a + 1 === a + 2) // true

let b = Number.MIN_SAFE_INTEGER
console.log(b - 1 === b - 2) // true
  • 1
  • 2
  • 3
  • 4
  • 5

为了检查是否安全，可以使用ES6的 。

Number.isSafeInteger(a) // true
Number.isSafeInteger(a + 1) // false
  • 1
  • 2

分析（朴素解法）

这题限制我们不能使用 *、/、% 运算符，所以比较容易想到的就是使用 减法 来模拟 除法

要计算 a/b，可以使用 a-b 得到结果与 b 进行判断，比 b 大就继续减，比 b 小就停止操作，计算减的次数就是所求的商

例如 计算 9/2： ① 9-2=7>2 ② 7-2=5>2 ③ 5-2=3>2 ④ 3-2=1<2 所以商是4

/**
 * @param {number} a
 * @param {number} b
 * @return {number}
 */
var divide = function(a, b) {
    let result = 0
    while(a >= b){
        a -= b
        result++
    }
    return result
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

考虑正负问题

上述讨论假设被除数和除数都是正整数。如果有负数则可以将它们先转换成正数，计算正数的除法之后再根据需要调整商的正负号。

由于题目要求不能使用乘法，所以我们使用异或操作符^来判断结果的正负符号sign

var divide = function(a, b) {

    let sign = (a>0) ^ (b>0) // 同（正）0 异（负）1

    a = a > 0 ? a : -a
    b = b > 0 ? b : -b

    let result = 0
    while(a >= b){
        a -= b
        result++
    }
    
    return sign ? -result : result
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

我们还没有考虑溢出问题，因为题目要求 假设我们的环境只能存储 32 位有符号整数

考虑溢出问题

对于32位的整数而言，最小的整数是 − 2 31 -2^{31} −231，最大的整数是 2 31 − 1 2^{31}-1 231−1。

由于是整数的除法并且除数不等于0，因此商的绝对值一定小于或等于被除数的绝对值。因此，int型整数的除法只有一种情况会导致溢出：即 − 2 31 -2^{31} −231/ − 1 -1 −1。这是因为最大的正数为 2 31 − 1 2^{31} - 1 231−1，如果将 − 2 31 -2^{31} −231转换为正数则会导致溢出，即 2 31 2^{31} 231超出了正数的范围。

var divide = function(a, b) {
    // 解决溢出问题
    if(a === -(2**31) && b === -1) return 2**31-1

    let sign = (a>0) ^ (b>0) // 同（正）0 异（负）1

    a = a > 0 ? a : -a
    b = b > 0 ? b : -b

    let result = 0
    while(a >= b){
        a -= b
        result++
    }
    
    return sign ? -result : result
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

性能优化

上面这种很直观的解法存在一个问题：当被除数很大但除数很小时，减法操作执行的次数会很多。
如果被除数是N，那么这种解法的时间复杂度为O(N)，所以我们需要对这种解法进行优化。我们要将O(N)的时间复杂度优化到O(logN)

可以将上述解法稍做调整。当被除数大于除数时，继续比较判断被除数是否大于除数的2倍，如果是，则继续判断被除数是否大于除数的4倍、8倍等。

如果被除数最多大于除数的 2 k 2^k 2k倍，那么将被除数减去除数的 2 k 2^k 2k倍，然后将剩余的被除数重复前面的步骤。

由于每次将除数翻倍，因此优化后的时间复杂度是O(logN)。

下面以15/2为例：

  1. 15 15 15大于 2 2 2，也大于 2 ∗ 2 1 = 4 2*2^1=4 2∗21=4，还大于 2 ∗ 2 2 = 8 2*2^2=8 2∗22=8，但小于 2 ∗ 2 3 = 16 2*2^3=16 2∗23=16。将 15 15 15 减去 2 ∗ 2 2 = 8 2*2^2=8 2∗22=8，剩 7 7 7。由于减去的是除数的 2 2 = 4 2^2=4 22=4倍，减去这部分对应的商是4

  2. 接下来对剩余的 7 7 7和除数 2 2 2进行比较， 7 7 7大于 2 2 2，大于 2 ∗ 2 = 4 2*2=4 2∗2=4，但小于 2 ∗ 2 2 = 8 2*2^2=8 2∗22=8，于是将 7 7 7减去 4 4 4，还剩余 3 3 3。这次减去的是除数 2 2 2的 2 2 2倍，对应的商是2

  3. 然后对剩余的 3 3 3和除数 2 2 2进行比较， 3 3 3大于 2 2 2，但 2 ∗ 2 = 4 2*2=4 2∗2=4，于是将 3 3 3减去 2 2 2，还剩余 1 1 1。这一次减去的是除数的 1 1 1倍，对应的商是1

  4. 最后剩余的数字是 1 1 1，比除数 2 2 2小，不能再减去除数了

  5. 于是15/2的商是4+2+1，即7

题解

下面用代码实现，由于题目要求不能使用 * ，所以这里使用加法代替乘法

/**
 * @param {number} a
 * @param {number} b
 * @return {number}
 */
var divide = function(a, b) {
    // 解决溢出问题
    if(a === -(2**31) && b === -1) return 2**31-1

    let sign = (a>0) ^ (b>0) // 同（正）0 异（负）1

    a = a > 0 ? a : -a
    b = b > 0 ? b : -b

    let result = 0

    while(a >= b){

        let value = b
        let k = 1

        while(value >= -(2**30) && a >= value + value){
            k += k
            value += value
        }

        result += k
        a -= value
    }

    return sign ? -result : result
};
  • 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

提交

可以看到效率提高很多！！！

最后，欢迎关注我的专栏，和YK菌做好朋友

相关文章