2623. 记忆函数

说在前面

🎈实现一个记忆化函数，可以对传入的函数进行缓存，以提高函数的执行效率

题目描述

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

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

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

sum 接收两个整型参数 a 和 b ，并返回 a + b 。
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 <= 105
• 1 <= n <= 10
• actions.length === values.length
• actions[i] 为 “call” 和 “getCallCount” 中的一个
• fnName 为 “sum”, “factorial” 和 “fib” 中的一个

解题思路

这道题目的难点主要是在与对题目描述的理解，理解了题目之后这其实就是一道比较简单的题目。重点在于题目中的这一句描述记忆函数 是一个对于相同的输入永远不会被调用两次的函数。相反，它将返回一个缓存值。,也就是说我们需要将调用过的参数值和结果缓存起来，在后面输入相同的参数时，直接将缓存中的结果返回即可，这样可以避免函数的重复调用，这种方式可以避免重复计算相同输入的函数，提高了函数的执行效率。

在函数体内部，创建了一个 Map 对象 map，用于存储已计算过的结果。

返回一个新的函数，该函数使用 rest 参数 …args 接收任意数量的参数。

使用 JSON.stringify(args) 将参数转换为字符串形式，作为缓存的键。

检查 map 中是否存在该键：

• 如果存在，则直接返回缓存中的值。
• 如果不存在，则调用原始函数 fn(…args) 计算值，并将结果存入到 map 中，然后返回该值。

AC代码

/**
 * @param {Function} fn
 * @return {Function}
 */
function memoize(fn) {
  const map = new Map();
  return function (...args) {
    const key = JSON.stringify(args);
    if (map.has(key)) return map.get(key);
    const value = fn(...args);
    map.set(key, value);
    return value;
  };
}

/**
 * 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
 */

公众号

关注公众号『前端也能这么有趣』，获取更多有趣内容。

说在后面

🎉 这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打羽毛球 🏸 ，平时也喜欢写些东西，既为自己记录 📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解 🙇，写错的地方望指出，定会认真改进 😊，偶尔也会在自己的公众号『前端也能这么有趣』发一些比较有趣的文章，有兴趣的也可以关注下。在此谢谢大家的支持，我们下文再见 🙌。