2630. 记忆函数 II

🔴   🔗 力扣 LeetCode

题目

Given a function fn, return a memoized version of that function.

A **memoized **function is a function that will never be called twice with the same inputs. Instead it will return a cached value.

fn can be any function and there are no constraints on what type of values it accepts. Inputs are considered identical if they are === to each other.

Example 1:

Input:

getInputs = () => [[2,2],[2,2],[1,2]]

fn = function (a, b)

Output: [{"val":4,"calls":1},{"val":4,"calls":1},{"val":3,"calls":2}]

Explanation:

const inputs = getInputs();

const memoized = memoize(fn);

for (const arr of inputs) {

memoized(...arr);

}

For the inputs of (2, 2): 2 + 2 = 4, and it required a call to fn().

For the inputs of (2, 2): 2 + 2 = 4, but those inputs were seen before so no call to fn() was required.

For the inputs of (1, 2): 1 + 2 = 3, and it required another call to fn() for a total of 2.

Example 2:

Input:

getInputs = () => [[{},{}],[{},{}],[{},{}]]

fn = function (a, b) { return ({...a, ...b}); }

Output: [{"val":{},"calls":1},{"val":{},"calls":2},{"val":{},"calls":3}]

Explanation:

Merging two empty objects will always result in an empty object. It may seem like there should only be 1 call to fn() because of cache-hits, however none of those objects are === to each other.

Example 3:

Input:

getInputs = () => { const o =

fn = function (a, b) { return ({...a, ...b}); }

Output: [{"val":{},"calls":1},{"val":{},"calls":1},{"val":{},"calls":1}]

Explanation:

Merging two empty objects will always result in an empty object. The 2nd and 3rd third function calls result in a cache-hit. This is because every object passed in is identical.

Constraints:

• 1 <= inputs.length <= 10^5
• 0 <= inputs.flat().length <= 10^5
• inputs[i][j] != NaN

题目大意

现给定一个函数 fn ，返回该函数的一个 记忆化 版本。

一个 记忆化 的函数是一个函数，它不会被相同的输入调用两次。而是会返回一个缓存的值。

函数 fn 可以是任何函数，对它所接受的值类型没有任何限制。如果两个输入值在 JavaScript 中使用 === 运算符比较时相等，则它们被视为相同。

示例 1：

输入：

getInputs = () => [[2,2],[2,2],[1,2]]

fn = function (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)

输出：[{"val":{},"calls":1},{"val":{},"calls":2},{"val":{},"calls":3}]

解释：

将两个空对象合并总是会得到一个空对象。尽管看起来应该缓存命中并只调用一次 fn()，但是这些空对象彼此之间都不是 === 相等的。

示例 3：

输入：

getInputs = () => { const o =

fn = function (a, b) { return ({...a, ...b}); }

输出：[{"val":{},"calls":1},{"val":{},"calls":1},{"val":{},"calls":1}]

解释：

将两个空对象合并总是会得到一个空对象。因为传入的每个对象都是相同的，所以第二个和第三个函数调用都会命中缓存。

提示：

• 1 <= inputs.length <= 10^5
• 0 <= inputs.flat().length <= 10^5
• inputs[i][j] != NaN

解题思路

本道题的难点在于，仅当两个输入值使用 === 运算符比较时相等被视为相同，因此不能使用 JSON.stringify 来做缓存的 key，而是要采用一种树形嵌套缓存，以支持对对象引用的严格比较：

• 使用 Map 作为缓存数据结构，支持对对象引用的严格比较。
• 由于 JavaScript 中的对象和数组引用是通过引用来判断相等的，所以我们可以直接将这些引用作为 Map 的键。
• 使用递归地遍历参数，构建一个嵌套的 Map，每个层级的键都是当前参数的引用。
• 在每个参数的最终 Map 中存储一个特殊的值（如 Symbol('__res')）以表示计算结果。
• 在每层中，检查是否存在结果。如果存在，直接返回；如果不存在，调用原函数并缓存结果。

复杂度分析

• 时间复杂度：O(n)，n 是输入参数的数量，但由于缓存机制，实际调用次数通常会更少。
• 空间复杂度：O(n)，取决于参数的种类和数量。

代码

/**
 * @param {Function} fn
 * @return {Function}
 */
function memoize(fn) {
	let cache = new Map();
	const RES = Symbol('__res');
	return function (...params) {
		let curCache = cache;
		for (let param of params) {
			if (!curCache.has(param)) {
				curCache.set(param, new Map());
			}
			curCache = curCache.get(param);
		}
		if (curCache.has(RES)) return curCache.get(RES);
		const result = fn(...params);
		curCache.set(RES, 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
 */

相关题目

题号	标题	题解	标签	难度	力扣
2623	记忆函数	[✓]		🟠	🀄️ 🔗
2632	柯里化 🔒	[✓]		🟠	🀄️ 🔗