LeetCode 面试题 08.05. 递归乘法

2022-08-11 HGNULB 约 9 分钟

文章信息 8 个分类 3 个标签

分类

LeetCode CodeTop 中等未解决 5-10 字节跳动亚马逊程序员面试金典（第 6 版）

题目描述

✅ 面试题 08.05. 递归乘法

题意分析

给定两个正整数 A 和 B，要求返回它们的乘积，但不许使用 * 运算符，并且要尽量少做运算。题目保证结果落在 32 位整数范围内，所以不需要为溢出设计额外机制。

「不许用乘法」这条限制把可用的原子操作压缩到了加法、减法、比较和位移。加法能直接表达乘法的定义——A * B 就是把 B 累加 A 次；位移则免费提供了「乘 2 / 除 2」，因为 x << 1 等价于 x + x、x >> 1 对正数等价于取一半。这两件工具凑在一起，就有机会把「累加 A 次」这个线性代价压成对折的对数代价。

「尽量减少运算次数」是本题真正的考点，也是它被归到中等难度的原因。如果只想拿到正确答案，写一个循环加 A 次就够了；题目额外要求的是把运算量降到与输入的二进制位数同阶。凡是看到「禁用某个运算符 + 最小化操作次数」这种组合，基本都在暗示要按二进制拆解输入。

边界方面有两处需要留心：其一是某个乘数为 1 时答案就是另一个数，这是自然的收敛终点；其二是把哪个数当作「被拆解的那个」会直接决定运算量，拆小的那个显然比拆大的那个划算。至于零，题目限定了正整数，但一个健壮的实现应当让 0 也能安全落地，而不是陷入死循环。

解法：递归折半相加

核心思路

先看暴力：把 larger 累加 smaller 次。这完全正确，但当 smaller 达到百万量级时就要做百万次加法，瓶颈在于每一步只消化掉「一份」。

瓶颈的根源是把 smaller 当成了一个每次减 1 的计数器。换个角度观察：如果已经知道 half = (smaller / 2) * larger，那么 half + half 就直接得到了 (smaller - smaller % 2) * larger——一次加法把规模砍掉一半，而不是砍掉一。剩下的零头只可能是 0 或 1 个 larger，取决于 smaller 的奇偶。

于是得到递推关系：smaller 为偶数时 f(smaller) = f(smaller >> 1) + f(smaller >> 1)，为奇数时 f(smaller) = f(smaller >> 1) + f(smaller >> 1) + larger。注意式子里两个 f(smaller >> 1) 必须只算一次并复用，否则递归会展开成满二叉树，规模退回线性。

显式写出递归的语义：helper(smaller, larger) 返回「smaller 个 larger 相加的和」，其中 larger 在整个递归过程中恒定不变，唯一在缩小的量是 smaller，且每层严格减半。这个「只有一个参数在动，且以二分速度收敛」的结构，就是递归层数为 $O(\log \text{smaller})$ 的保证。

最后一步优化是选择拆谁：既然层数由被拆解的那个数决定，就应该拆两者中较小的那个。所以入口先做一次比较，令 smaller = min(A, B)、larger = max(A, B)。这一步不影响正确性（乘法可交换），只影响运算次数，但恰恰是题目「最小化运算次数」的要求所在。

递归基取两个：smaller == 1 时答案就是 larger，这是正常的收敛出口；smaller == 0 时返回 0，它既是数学上正确的答案，也是防止 0 >> 1 恒等于 0 而无限递归的安全阀。

解题步骤

归一化两个乘数：令 smaller = min(A, B)、larger = max(A, B)。为什么要做：递归层数等于 log2(smaller)，拿小的那个去折半才能把层数压到最低，这正是本题「最少运算次数」的得分点。

递归基一，smaller == 0 返回 0。为什么要写：0 >> 1 仍然是 0，没有这条出口的话，一旦 smaller 取到 0 就会无限递归直到栈溢出。

递归基二，smaller == 1 返回 larger。为什么要写：一个 larger 相加就是 larger 本身，这是递归真正的收敛点；正整数每次右移最终必定落到 1，这条出口一定会被命中。

递归求半：half = helper(smaller >> 1, larger)。为什么用 >> 而不是 / 2：对正数两者等价，但位移更直白地表达了「按二进制降一位」这个意图；更关键的是结果只求一次并存进变量，供下面重复使用。

按奇偶合并：smaller 是偶数时返回 half + half；是奇数时返回 half + half + larger。为什么奇数要补一个 larger：smaller >> 1 对奇数是向下取整，(smaller >> 1) * 2 等于 smaller - 1，刚好少算了一份 larger。

全程只出现了 +、>>、& 和比较，没有任何一次 *，符合题目限制。

以 A = 5、B = 11 走一遍完整流程。

入口：smaller = 5、larger = 11，调用 helper(5, 11)。

下降阶段：helper(5, 11) 不命中任何递归基，调用 helper(2, 11)；helper(2, 11) 也不命中，调用 helper(1, 11)；helper(1, 11) 命中 smaller == 1，返回 11。

回溯到 helper(2, 11)：half = 11，2 & 1 == 0 走偶数分支，返回 11 + 11 = 22，含义是「2 个 11 相加」。

回溯到 helper(5, 11)：half = 22，5 & 1 == 1 走奇数分支，返回 22 + 22 + 11 = 55，含义是「4 个 11 再加上零头的 1 个 11，共 5 个 11」。

最终返回 55。整个过程只有 3 层递归、4 次加法。规模小时优势还不明显，把 smaller 换成 1048576 就一目了然：折半法只需 20 层递归、约 20 次加法，暴力累加需要一百万次加法。

再看一个反例，说明 half 为什么必须存成变量：如果奇数分支写成 return helper(smaller >> 1, larger) + helper(smaller >> 1, larger) + larger，看似只是没有复用，实则递归每层分裂成两支，调用次数变成 $2^{\log \text{smaller}}$ 即 smaller 量级，复杂度直接退回 $O(\min(A, B))$，优化全部作废。

代码实现

class Solution {
    public int multiply(int A, int B) {
        int smaller = Math.min(A, B);
        int larger = Math.max(A, B);
        return helper(smaller, larger);
    }

    private int helper(int smaller, int larger) {
        if (smaller == 0) {
            return 0;
        }
        if (smaller == 1) {
            return larger;
        }

        int half = helper(smaller >> 1, larger);
        if ((smaller & 1) == 0) {
            return half + half;
        }
        return half + half + larger;
    }
}

func multiply(A int, B int) int {
    smaller, larger := A, B
    if smaller > larger {
        smaller, larger = larger, smaller
    }
    return multiplyHelper(smaller, larger)
}

func multiplyHelper(smaller int, larger int) int {
    if smaller == 0 {
        return 0
    }
    if smaller == 1 {
        return larger
    }

    half := multiplyHelper(smaller>>1, larger)
    if smaller&1 == 0 {
        return half + half
    }
    return half + half + larger
}

复杂度分析

时间复杂度：$O(\log \min(A, B))$。每层递归把 smaller 右移一位，从 smaller 降到 1 需要 $\lfloor \log_2 \text{smaller} \rfloor$ 层；每层只做常数次加法、比较和位运算，且 half 被复用，递归调用是一条链而不是一棵树。

空间复杂度：$O(\log \min(A, B))$，来自递归调用栈，深度与层数相同，没有额外数据结构。由于奇数分支在递归返回之后还要再加一个 larger，这不是尾递归，栈帧无法折叠；不过深度最多几十层，不存在爆栈风险。

关键点总结

「禁用某个运算符 + 要求最少操作次数」几乎总是在提示按二进制拆解输入，把线性的重复累加换成对数次的折半合并；这个套路同样适用于快速幂和不用除号的除法。

折半得到的中间结果必须存进变量复用，写两次递归调用会让链退化成满二叉树，复杂度从 $O(\log n)$ 打回 $O(n)$——面试官经常故意在这里挖坑。

拆解较小的那个乘数只影响效率不影响正确性，但主动说出这一点，是在向面试官证明你理解了「最小化运算次数」这条附加要求，而不只是背了个递归模板。

奇偶分支的本质是看二进制最低位：低位为 1 就补一份 larger，为 0 就不补，这与快速幂里「指数二进制位为 1 就乘一次底数」是同一个骨架。

递归基要同时覆盖收敛出口（smaller == 1）和退化输入（smaller == 0），因为 0 在右移下是不动点，缺了它得到的是死循环而不是错误答案。

易错点总结

奇数分支写成两次递归调用：return helper(smaller >> 1, larger) + helper(smaller >> 1, larger) + larger，A = 1048575、B = 2 时调用次数从 20 次膨胀到百万级，复杂度退化成 $O(\min(A, B))$，运行时间与栈开销都急剧上升。

改用逐次减一递归：return helper(smaller - 1, larger) + larger，A = 100000、B = 2 时递归深度十万层，直接 StackOverflowError。

不做 min / max 归一化，固定拿 A 折半：A = 1048576、B = 1 时层数是 20，反过来拿 B 折半只要 1 层。答案仍对，但违背了「最小化运算次数」的要求，面试中会被追问为什么不先比较。

只写 smaller == 1 一个递归基：入参一旦出现 0，0 >> 1 恒为 0，helper(0, larger) 会无限递归到爆栈，而不是返回 0。

奇数分支忘记补 larger：A = 3、B = 5 时 half = helper(1, 5) = 5，返回 10 而不是 15，所有奇数乘数的用例全部少算一份。

递归基返回 smaller 而不是 larger：A = 1、B = 9 直接返回 1，任何一边为 1 的用例都错。

用 half * 2 或 larger * 2 代替 half + half：结果正确、OJ 也能过，但用上了被禁的 *，属于绕开考点，面试当场判失败。

直接 return A * B 交卷：所有测试用例都通过，但这道题的全部意义就是不许用乘号，等同于没做。

改写成循环把 larger 累加 smaller 次：A = 65536、B = 65536 时要做六万多次加法，既不满足题面「递归」的提示，也不满足最少运算次数的要求。

奇偶判断写成 smaller % 2 == 1：正整数下没问题，但一旦把函数扩展到负数，Java 的 % 对负奇数返回 -1，奇数分支不再命中，零头被吞掉；用 (smaller & 1) == 1 才没有这个坑。

相似题目

题目	难度	考察点
50. Pow(x, n)	中等	把折半相加换成折半相乘，额外要处理负指数与 `INT_MIN` 取反溢出
29. 两数相除	中等	反过来禁除号，用倍增减法逼近商，还要单独处理商溢出的边界
371. 两整数之和	中等	连加号都禁掉，只能用异或求无进位和、与运算左移求进位
面试题 17.01. 不用加号的加法	简单	与 371 同题，位运算模拟全加器
面试题 16.09. 运算	中等	只给一个运算符实现加减乘除，是本题思路的综合放大版
372. 超级次方	中等	指数以数组形式给出，要按十进制位逐位递归并配合取模
43. 字符串相乘	中等	大数场景走竖式模拟与进位处理，不能折半，考的是下标对应关系
面试题 08.06. 汉诺塔问题	简单	同样把规模缩小后合并，但子问题是「移动 n-1 个盘」而非折半
剑指 Offer 16. 数值的整数次方	中等	与 50 同题，可直接套用折半骨架
剑指 Offer 64. 求1+2+…+n	中等	同为「禁用某类语法」的构造题，靠逻辑运算短路代替 `if` 终止递归