LeetCode 题解工作台
记忆函数 II
现给定一个函数 fn ，返回该函数的一个 记忆化 版本。 一个 记忆化 的函数是一个函数，它不会被相同的输入调用两次。而是会返回一个缓存的值。 函数 fn 可以是任何函数，对它所接受的值类型没有任何限制。如果两个输入值在 JavaScript 中使用 === 运算符比较时相等，则它们被视为相同。 示…
0
题型
1
代码语言
0
相关题
当前训练重点
困难 · Memoize II core interview pattern
答案摘要
我们用两个哈希表，其中： - `idxMap` 用于记录每个参数对应的索引，索引从 开始逐渐递增；
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 Memoize II core interview pattern 题型思路
题目描述
现给定一个函数 fn ，返回该函数的一个 记忆化 版本。
一个 记忆化 的函数是一个函数，它不会被相同的输入调用两次。而是会返回一个缓存的值。
函数 fn 可以是任何函数，对它所接受的值类型没有任何限制。如果两个输入值在 JavaScript 中使用 === 运算符比较时相等，则它们被视为相同。
示例 1：
输入：
getInputs = () => [[2,2],[2,2],[1,2]]
fn = function (a, b) { return a + b; }
输出：[{"val":4,"calls":1},{"val":4,"calls":1},{"val":3,"calls":2}]
解释：
const inputs = getInputs();
const memoized = memoize(fn);
for (const arr of inputs) {
memoized(...arr);
}
对于参数为 (2, 2) 的输入: 2 + 2 = 4，需要调用 fn() 。
对于参数为 (2, 2) 的输入: 2 + 2 = 4，这些输入之前已经出现过，因此不需要再次调用 fn()。
对于参数为 (1, 2) 的输入: 1 + 2 = 3，需要再次调用 fn()，总共调用了 2 次。
示例 2：
输入：
getInputs = () => [[{},{}],[{},{}],[{},{}]]
fn = function (a, b) { return a + b; }
输出：[{"val":{},"calls":1},{"val":{},"calls":2},{"val":{},"calls":3}]
解释：
将两个空对象合并总是会得到一个空对象。尽管看起来应该缓存命中并只调用一次 fn()，但是这些空对象彼此之间都不是 === 相等的。
示例 3：
输入：
getInputs = () => { const o = {}; return [[o,o],[o,o],[o,o]]; }
fn = function (a, b) { return ({...a, ...b}); }
输出：[{"val":{},"calls":1},{"val":{},"calls":1},{"val":{},"calls":1}]
解释：
将两个空对象合并总是会得到一个空对象。因为传入的每个对象都是相同的，所以第二个和第三个函数调用都会命中缓存。
提示：
1 <= inputs.length <= 1050 <= inputs.flat().length <= 105inputs[i][j] != NaN
解题思路
方法一：双哈希表
我们用两个哈希表，其中：
idxMap用于记录每个参数对应的索引，索引从 开始逐渐递增；cache用于记录每个函数参数调用的结果。
对于每个函数参数，我们将其转换为索引序列，然后将其转换为字符串作为 cache 的键，将函数调用的结果作为 cache 的值。每一次函数调用，我们都先判断 cache 中是否存在该键，如果存在，则直接返回对应的值，否则调用函数并将结果存入 cache 中。
时间复杂度 ，空间复杂度 。其中 为函数参数的个数。
type Fn = (...params: any) => any;
function memoize(fn: Fn): Fn {
const idxMap: Map<string, number> = new Map();
const cache: Map<string, any> = new Map();
const getIdx = (obj: any): number => {
if (!idxMap.has(obj)) {
idxMap.set(obj, idxMap.size);
}
return idxMap.get(obj)!;
};
return function (...params: any) {
const key = params.map(getIdx).join(',');
if (!cache.has(key)) {
cache.set(key, fn(...params));
}
return cache.get(key)!;
};
}
/**
* 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
*/
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(N) as we are processing each input once, with the caching mechanism providing O(1) lookup time. Space complexity is O(NL), where N is the number of function calls and L is the size of the input, since the cache needs to store results for each unique input combination. |
| 空间 | O(NL) |
面试官常问的追问
外企场景- question_mark
Look for an efficient cache lookup mechanism.
- question_mark
Evaluate how the candidate handles object equality and memoization with non-primitive inputs.
- question_mark
Check for understanding of performance optimizations and memory management in memoization.
常见陷阱
外企场景- error
Failing to account for object equality with non-primitive values like objects or arrays.
- error
Incorrect cache management leading to memory overflow or incorrect cache hits.
- error
Assuming that JSON.stringify can reliably determine input equality for non-primitive types.
进阶变体
外企场景- arrow_right_alt
Handle inputs with large datasets efficiently.
- arrow_right_alt
Implement the cache with weak references to avoid memory bloat.
- arrow_right_alt
Extend the solution to handle asynchronous functions.