What is the Memoize pattern in this LeetCode problem?

The Memoize pattern involves caching the results of function calls with specific inputs so repeated calls with the same arguments return the stored result without recomputation.

How do I handle variable numbers of function arguments?

Spread the arguments into an array and convert the array into a string or tuple to use as a cache key, ensuring all argument combinations are memoized correctly.

Why is tracking the actual function call count important?

It measures efficiency by counting only when the original function is executed, differentiating between cached and new computations.

Can memoization be used for recursive functions like fib?

Yes, memoization dramatically improves recursive calls like fib by storing previously computed results, preventing exponential recalculation.

What common mistakes should I avoid implementing Memoize?

Avoid missing cache hits due to improper key creation, incrementing call counts on cached returns, and assuming fixed argument lengths.

#2623

Medium

auto_awesomeMemoize core interview pattern

LeetCode 题解工作台

记忆函数

请你编写一个函数 fn ，它接收另一个函数作为输入，并返回该函数的记忆化后的结果。记忆函数是一个对于相同的输入永远不会被调用两次的函数。相反，它将返回一个缓存值。你可以假设有 3 个可能的输入函数： sum 、 fib 和 factorial 。 sum 接收两个整型参数 a 和 b ，并…

题目描述

请你编写一个函数 fn，它接收另一个函数作为输入，并返回该函数的 记忆化 后的结果。

记忆函数 是一个对于相同的输入永远不会被调用两次的函数。相反，它将返回一个缓存值。

你可以假设有 3 个可能的输入函数：sum 、fib 和 factorial 。

sum 接收两个整型参数 a 和 b ，并返回 a + b 。假设如果参数 (b, a) 已经缓存了值，其中 a != b，它不能用于参数 (a, b)。例如，如果参数是 (3, 2) 和 (2, 3)，则应进行两个单独的调用。
fib 接收一个整型参数 n ，如果 n <= 1 则返回 1，否则返回 fib (n - 1) + fib (n - 2)。
factorial 接收一个整型参数 n ，如果 n <= 1 则返回 1 ，否则返回 factorial(n - 1) * n 。

示例 1：

输入：
fnName = "sum"
actions = ["call","call","getCallCount","call","getCallCount"]
values = [[2,2],[2,2],[],[1,2],[]]
输出：[4,4,1,3,2]
解释：
const sum = (a, b) => a + b;
const memoizedSum = memoize(sum);
memoizedSum (2, 2);// "call" - 返回 4。sum() 被调用，因为之前没有使用参数 (2, 2) 调用过。
memoizedSum (2, 2);// "call" - 返回 4。没有调用 sum()，因为前面有相同的输入。
// "getCallCount" - 总调用数： 1
memoizedSum(1, 2);// "call" - 返回 3。sum() 被调用，因为之前没有使用参数 (1, 2) 调用过。
// "getCallCount" - 总调用数： 2

示例 2：

输入：
fnName = "factorial"
actions = ["call","call","call","getCallCount","call","getCallCount"]
values = [[2],[3],[2],[],[3],[]]
输出：[2,6,2,2,6,2]
解释：
const factorial = (n) => (n <= 1) ? 1 : (n * factorial(n - 1));
const memoFactorial = memoize(factorial);
memoFactorial(2); // "call" - 返回 2。
memoFactorial(3); // "call" - 返回 6。
memoFactorial(2); // "call" - 返回 2。 没有调用 factorial()，因为前面有相同的输入。
// "getCallCount" -  总调用数：2
memoFactorial(3); // "call" - 返回 6。 没有调用 factorial()，因为前面有相同的输入。
// "getCallCount" -  总调用数：2

示例 3：

输入：
fnName = "fib"
actions = ["call","getCallCount"]
values = [[5],[]]
输出：[8,1]
解释：
fib(5) = 8 // "call"
// "getCallCount" - 总调用数：1

提示：

0 <= a, b <= 10⁵
1 <= n <= 10
1 <= actions.length <= 10⁵
actions.length === values.length
actions[i] 为 "call" 和 "getCallCount" 中的一个
fnName 为 "sum", "factorial" 和 "fib" 中的一个

lightbulb

解题思路

方法一：哈希表

我们可以使用哈希表来存储函数的参数和返回值，当再次调用函数时，如果参数已经存在于哈希表中，则直接返回哈希表中的值，否则调用函数并将返回值存入哈希表中。

时间复杂度 $O(1)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为函数的参数个数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

type Fn = (...params: any) => any;

function memoize(fn: Fn): Fn {
    const cache: Record<any, any> = {};

    return function (...args) {
        if (args in cache) {
            return cache[args];
        }
        const result = fn(...args);
        cache[args] = result;
        return result;
    };
}

/**
 * let callCount = 0;
 * const memoizedFn = memoize(function (a, b) {
 *	 callCount += 1;
 *   return a + b;
 * })
 * memoizedFn(2, 3) // 5
 * memoizedFn(2, 3) // 5
 * console.log(callCount) // 1
 */

speed

复杂度分析

指标	值
时间	and space complexity depend on how many unique input combinations are called. Each unique call requires storing its result, while repeated calls fetch cached results in constant time. Space grows with the number of unique calls.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Watch for correctly caching inputs to avoid duplicate computation.
question_mark
Check if the candidate can handle variable argument lengths in memoization.
question_mark
Ensure the solution tracks the actual function call count, not total calls to the wrapper.

warning

常见陷阱

外企场景

error
Failing to convert argument arrays to a cacheable key, causing missed cache hits.
error
Incrementing the call count even when returning cached results.
error
Assuming only fixed numbers of arguments rather than supporting arbitrary input lengths.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Memoize functions with multiple arguments including objects or arrays.
arrow_right_alt
Implement a time-limited cache where results expire after a set duration.
arrow_right_alt
Track both cache hits and misses to analyze memoization efficiency.

help

常见问题

外企场景

探索更多题目 →

auto_awesome

继续模式

Memoize core interview pattern

用同一解题框架扩展到更多题目。

arrow_forward signal_cellular_alt

同难度题单

中等

按当前难度继续强化稳定输出。

arrow_forward