LeetCode 面试题 08.05. 递归乘法

Categories:

题目描述
思路分析
1. 解法一：递归 + 位运算（推荐）
相似题目

题目描述

✅ 面试题 08.05. 递归乘法

思路分析

解法一：递归 + 位运算（推荐）

核心思路：

用较小数递归分解：a * b = (a/2) * b * 2。

若 a 为奇数，多加一次 b。

递归深度为 O(log a)。

复杂度分析：

时间复杂度：O(log n)，其中 n 为较小的乘数。

空间复杂度：O(log n)，递归栈深度。

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

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

        int half = smaller >> 1;
        int halfProd = helper(half, bigger);

        if (smaller % 2 == 0) {
            return halfProd + halfProd;
        }
        return halfProd + halfProd + bigger;
    }
}

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

func helperMultiply(smaller int, bigger int) int {
	if smaller == 0 {
		return 0
	}
	if smaller == 1 {
		return bigger
	}

	half := smaller >> 1
	halfProd := helperMultiply(half, bigger)

	if smaller%2 == 0 {
		return halfProd + halfProd
	}
	return halfProd + halfProd + bigger
}

相似题目

题目	难度	考察点
面试题 08.05. 递归乘法	中等	递归
43. 字符串相乘	中等	模拟
50. Pow(x, n)	中等	递归
371. 两整数之和	中等	位运算
29. 两数相除	中等	位运算
191. 位 1 的个数	简单	位运算

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/47196357