程序员面试金典 - 面试题 08.05. 递归乘法

题目难度: 中等

原题链接

今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

递归乘法。 写一个递归函数，不使用 * 运算符， 实现两个正整数的相乘。可以使用加号、减号、位移，但要吝啬一些。

示例 1:

• 输入：A = 1, B = 10
• 输出：10

示例 2:

• 输入：A = 3, B = 4
• 输出：12

提示:

• 保证乘法范围不会溢出

题目思考

1. 是否可以从十进制乘法中获取灵感?

解决方案

思路

• 这道题要求只使用加号、减号、位移实现乘法, 这提醒了我们可以利用位运算来解决
• 回顾小学的十进制乘法, 它是将乘数的每一位分别与被乘数相乘, 然后根据乘数位对应的位置移位并相加, 例如 12*34 = 12*4+12*3*10 = 48+360 = 408
• 我们这里也可以用类似的方式, 只不过将十进制变成二进制, 这样乘数的每一位就只有 0 或 1, 就不需要再使用乘法了
• 具体做法如下:
  1. 当 B 的最低位是 1 时, 它对最终乘积的贡献值为 A; 否则贡献值为 0
  2. 然后再将 B 向右移动一位, 递归调用 multiply 得到 A 与 B 的更高位的乘积
  3. 最后再将该乘积左移一位, 并与刚才计算得出的最低位的贡献值相加即可
• 递归出口自然是 B 为 0 时 (此时意味着 B 的每一位都进行了乘法运算), 此时的乘积也为 0

复杂度

• 时间复杂度 O(M): 假设 B 的二进制位数 M, 递归需要遍历 B 的每一个二进制位
• 空间复杂度 O(M): 递归栈的消耗, 递归深度也是 M

代码

Python 3

class Solution:
    def multiply(self, A: int, B: int) -> int:
        # 二进制乘法+乘每一位然后移位
        # 类似十进制乘法逐位相乘的做法:
        #   1. 当B的最低位是1时, 它对最终乘积的贡献值为A; 否则贡献值为0
        #   2. 然后再将B向右移动一位, 递归调用multiply得到A与B的更高位的乘积
        #   3. 最后再将该乘积左移一位, 并与刚才计算得出的最低位的贡献值相加即可
        if not B:
            # 递归出口, B是0时, 乘积为0
            return 0
        return (A if B & 1 else 0) + (self.multiply(A, B >> 1) << 1)

大家可以在下面这些地方找到我~????

我的 GitHub

我的 Leetcode

我的 CSDN

我的知乎专栏

我的头条号

我的牛客网博客

我的公众号: 算法精选, 欢迎大家扫码关注~????

最后

以上就是踏实雪碧为你收集整理的程序员面试金典 - 面试题 08.05. 递归乘法的全部内容，希望文章能够帮你解决程序员面试金典 - 面试题 08.05. 递归乘法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。