题目难度: 中等
今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~
题目描述
递归乘法。 写一个递归函数，不使用 * 运算符， 实现两个正整数的相乘。可以使用加号、减号、位移，但要吝啬一些。
示例 1:
- 输入：A = 1, B = 10
- 输出：10
示例 2:
- 输入：A = 3, B = 4
- 输出：12
提示:
- 保证乘法范围不会溢出
题目思考
- 是否可以从十进制乘法中获取灵感?
解决方案
思路
- 这道题要求只使用加号、减号、位移实现乘法, 这提醒了我们可以利用位运算来解决
- 回顾小学的十进制乘法, 它是将乘数的每一位分别与被乘数相乘, 然后根据乘数位对应的位置移位并相加, 例如
12*34=12*4+12*3*10=48+360=408 - 我们这里也可以用类似的方式, 只不过将十进制变成二进制, 这样乘数的每一位就只有 0 或 1, 就不需要再使用乘法了
- 具体做法如下:
- 当 B 的最低位是 1 时, 它对最终乘积的贡献值为 A; 否则贡献值为 0
- 然后再将 B 向右移动一位, 递归调用 multiply 得到 A 与 B 的更高位的乘积
- 最后再将该乘积左移一位, 并与刚才计算得出的最低位的贡献值相加即可
- 递归出口自然是 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) 大家可以在下面这些地方找到我~😊
我的公众号: 算法精选, 欢迎大家扫码关注~😊
京公网安备 11010502036488号