题目要求

力扣2630

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

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

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

示例：

 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 

题目分析

相同的入参则返回缓存的结果。 注意入参是有顺序的，比如一开始可能是 1 2 3，第二次可能是 1 3 2，这是两种不同的入参，那么就要求我们记录入参的顺序，并且同时记录 以这个顺序入参的结果

可以想象一下，调用函数三次，入参分别是 1 2 3 、 1 3 2 、 1 2 4， 是不是可以想象成这是一棵多叉树，根节点是1, 如下图

根据这个特性，我们可以根据每次的入参，构造树，以这些入参为例： 1 2 3，1 3 2， 1 2 4， 2 2 4。 这些子树有一个统一的根节点，代表的是无入参时的缓存结果。

有了这些树，当我们遇到了相同的入参，就顺着这个数来查找节点，找到对应的节点，看看它缓存的结果。

需要注意的是，入参数量是不固定的，可能入参 0 ~ n 个，所以要求我们每个树节点都需要存储对应的缓存值。

所以每个节点应该是这样的构造： [树节点，该节点对应的结果值]

在JS中，符合这样的构造的数据类型就是Map， 键是入参，值是[树Map，该节点对应的结果值]

这棵树实际上就是数据结构中很重要的一种 - 前缀树

定义数据结构

/**树Map，键为入参，值为树节点 */
type CacheMap = Map<any, CacheNode>
/**缓存树的节点类型元组，第一个是Map，若有结果，则第二个为结果  (也就是元组长度为2时代表有结果) */
type CacheNode = [CacheMap] | [CacheMap, any]

这个TS类型定义，绘制成树之后大概长这个样子。树Map的键为参数，方便我们找到节点

敲代码

TypeScirpt版本：

type Fn = (...params: any) => any
/**树Map，键为入参，值为树节点 */
type CacheMap = Map<any, CacheNode>
/**缓存树的节点类型元组，第一个是Map，若有结果，则第二个为结果  (也就是元组长度为2时代表有结果) */
type CacheNode = [CacheMap] | [CacheMap, any]

/**记忆传入的函数，相同的入参只执行一次 - Map树方法 
 * @param fn 需要被记忆的函数
 * @returns 新函数
 */
function memoize<T extends Fn>(fn: T): T {
    /**缓存树 - 当前是根节点，代表无入参时的树以及结果 */
    const cacheRoot: CacheNode = [new Map()]

    return function () {
        /**存储当前遍历到的树节点指针 */
        let node: CacheNode = cacheRoot
        //根据入参，遍历并构造Map树
        for (let param of arguments) {
            const map: CacheMap = node[0]
            //如果发现当前节点的Map中，没有找到这个参数对应的Map键，就需要构建新的节点
            if (!map.has(param)) {
                map.set(param, [new Map()])
            }
            //指针往下移动
            node = map.get(param)!
        }
        // 遍历完毕，需要返回这个节点的结果值 
        //如果当前节点没有返回值，就调用
        if (node.length < 2) { //函数返回值有可能是undefined，所以不能用 node[1] === undefined 来做条件
            node[1] = fn(...arguments)
        }
        // console.log('cache: ', deepClone(cache)); //可以在浏览器控制台打印看看每次的缓存树长什么样，注意需要深拷贝
        return node[1]
    } as T
}

JavaScript 无类型纯净版：

function memoize(fn) {
    /**缓存树 - 当前是根节点，代表无入参时的树以及结果 */
    const cacheRoot = [new Map()];
    return function () {
        /**存储当前遍历到的树节点指针 */
        let node = cacheRoot;
        //根据入参，遍历并构造Map树
        for (let param of arguments) {
            const map = node[0];
            //如果发现当前节点的Map中，没有找到这个参数对应的Map键，就需要构建新的节点
            if (!map.has(param)) {
                map.set(param, [new Map()]);
            }
            //指针往下移动
            node = map.get(param);
        }
        // 遍历完毕，需要返回这个节点的结果值 
        //如果当前节点没有返回值，就调用
        if (node.length < 2) { //函数返回值有可能是undefined，所以不能用 node[1] === undefined 来做条件
            node[1] = fn(...arguments);
        }
        // console.log('cache: ', deepClone(cache));
        return node[1];
    };
}

代码测试

可以用这个代码来模拟力扣的输入测试

//这里填写入参
const inputs = [[], [1], [1], [], [1, 2], [1, 2]] //每次调用的入参
const fn = function (...arr: number[]) { //需要被记忆的函数
    return arr.reduce((a, b) => a + b, 0);
}

//根据入参执行函数，查看结果
let callCount = 0;
const memoizedFn = memoize(function (...params: any[]) {
    callCount++
    return fn(...params)
})
console.log('被记忆函数：\n', fn.toString());
inputs.forEach((k, i) => {
    const res = memoizedFn(...k)
    console.log(`第${i}个输入: fn(${k.join(', ')}) \t 结果`, res, '\t当前fn被调用的次数', callCount);
})

结语

这个实现思路的空间复杂度比较高，对更多解法感兴趣的同学可以去看看力扣里其它同学的题解。如果本思路还有更多优化方法，欢迎大家多多指教