LeetCode 面试题 08.05. 递归乘法

文章目录

一、题目

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

示例1:

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

示例2:

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

提示:

• 保证乘法范围不会溢出

。

二、C# 题解

题目比较简单，直接上答案。

public class Solution {
    public int Multiply(int A, int B) {
        if (A < B) return Multiply(B, A);
        if (B == 0) return 0;
        return Multiply(A, B >> 1) + Multiply(A, B >> 1) + (B % 2 == 0 ? 0 : A);
    }
}

• 时间：12 ms，击败 94.12% 使用 C# 的用户
• 内存：25.40 MB，击败 58.82% 使用 C# 的用户