2623. 记忆函数

🟠   🔗 力扣 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.

You can assume there are 3 possible input functions: sum, fib, and factorial.

• sum accepts two integers a and b and returns a + b. Assume that if a value has already been cached for the arguments (b, a) where a != b, it cannot be used for the arguments (a, b). For example, if the arguments are (3, 2) and (2, 3), two separate calls should be made.
• fib accepts a single integer n and returns 1 if n <= 1 or fib(n - 1) + fib(n - 2) otherwise.
• factorial accepts a single integer n and returns 1 if n <= 1 or factorial(n - 1) * n otherwise.

Example 1:

Input:

fnName = "sum"

actions = ["call","call","getCallCount","call","getCallCount"]

values = [[2,2],[2,2],[],[1,2],[]]

Output: [4,4,1,3,2]

Explanation:

const sum = (a, b) => a + b;

const memoizedSum = memoize(sum);

memoizedSum(2, 2); // "call" - returns 4. sum() was called as (2, 2) was not seen before.

memoizedSum(2, 2); // "call" - returns 4. However sum() was not called because the same inputs were seen before.

// "getCallCount" - total call count: 1

memoizedSum(1, 2); // "call" - returns 3. sum() was called as (1, 2) was not seen before.

// "getCallCount" - total call count: 2

Example 2:

Input: fnName = "factorial"

actions = ["call","call","call","getCallCount","call","getCallCount"]

values = [[2],[3],[2],[],[3],[]]

Output: [2,6,2,2,6,2]

Explanation:

const factorial = (n) => (n <= 1) ? 1 : (n * factorial(n - 1));

const memoFactorial = memoize(factorial);

memoFactorial(2); // "call" - returns 2.

memoFactorial(3); // "call" - returns 6.

memoFactorial(2); // "call" - returns 2. However factorial was not called because 2 was seen before.

// "getCallCount" - total call count: 2

memoFactorial(3); // "call" - returns 6. However factorial was not called because 3 was seen before.

// "getCallCount" - total call count: 2

Example 3:

Input: fnName = "fib"

actions = ["call","getCallCount"]

values = [[5],[]]

Output: [8,1]

Explanation: fib(5) = 8 // "call"

// "getCallCount" - total call count: 1

Constraints:

• 0 <= a, b <= 10^5
• 1 <= n <= 10
• 0 <= actions.length <= 10^5
• actions.length === values.length
• actions[i] is one of "call" and "getCallCount"
• fnName is one of "sum", "factorial" and "fib"

题目大意

请你编写一个函数 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 。

提示：

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

解题思路

记忆化 (Memoization) 是一种优化技术，用于加速函数的执行，特别是对于有相同输入时可以重用结果的函数。其核心思想是使用一个缓存结构来存储之前的计算结果，以避免对相同的输入进行多次计算。

1. 创建一个哈希表 cache 来存储已经计算过的结果，键是输入参数，值是对应的输出结果。
2. 将输入参数通过 JSON 序列化转换为字符串，用作缓存的键 key = JSON.stringify(args)。
3. 每次调用函数时，检查该输入参数是否已经存在于缓存中：
   • 如果存在，直接返回缓存中的结果。
   • 如果不存在，计算该输入的结果，并将其存入缓存以供下次使用。

复杂度分析

• 时间复杂度：O(1)，每次调用时都会在缓存中进行查找（Map 的查找时间复杂度为 O(1)）。如果缓存命中，直接返回；如果没有命中，进行一次计算并存储结果。
• 空间复杂度：O(n)，取决于不同输入的数量。缓存会根据函数的输入参数存储结果，因此空间消耗随调用的不同输入增多。

代码

/**
 * @param {Function} fn
 * @return {Function}
 */
function memoize(fn) {
	const cache = new Map(); // 创建缓存

	return function (...args) {
		const key = JSON.stringify(args); // 将参数序列化作为键

		if (cache.has(key)) {
			return cache.get(key); // 如果缓存存在结果，直接返回
		}

		const result = fn(...args); // 计算结果
		cache.set(key, 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
 */

相关题目

题号	标题	题解	标签	难度
2620	计数器	[✓]
2629	复合函数	[✓]
2630	记忆函数 II	[✓]
2632	柯里化 🔒	[✓]