暑期前端训练day1

js——记忆函数

2025-06-19
day1

一、记忆函数Ⅰ：

链接：https://leetcode.cn/problems/memoize/?envType=problem-list-v2&envId=GR5hbGen

(1) 题意：给定一个函数，返回一个记忆版的函数，其中你只会包含三个可能输入的函数，sum(a, b) { return a + b}；fib(n) = fib(n - 1) + fib(n - 2)；fac(n) = n * fac(n - 1)；最终希望每次相同的参数都缓存下来。
(2) 题解：可以动态开点，去存map套map，因为三个函数都有不可能为undefined的性质，所以我们可以以undefined为判断条件

code:

function memoize(fn) {
    let mp = new Map()  
    function setFn(L, v) {
        let tmp = mp 
        for(let i = 0; i < L.length; ++ i ) {
            if(i < L.length - 1) {
                if(!tmp.get(L[i])) tmp.set(L[i], new Map())
                tmp = tmp.get(L[i])   
                continue 
            }
            // console.log(tmp)
            tmp.set(L[i], v) 
        }
    }
    function get(L) {
        let tmp = mp
        for(let i = 0; i < L.length; ++ i ) {
            if(tmp.get(L[i]) !== undefined) {
                tmp = tmp.get(L[i]) 
            }
            else {
                return undefined
            }
        }
        return tmp 
    }
    return function(...args) {
        const res = get(args) 
        if(res != undefined) return res
        const aim = fn(...args)
        setFn(args, aim) 
        return aim 
    }
}
/** 
 * 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 
 */

二、记忆函数Ⅱ：升级版本，需要适用于所有可能的函数

链接: https://leetcode.cn/problems/memoize-ii/

题解：这里我们可以考虑参数，需要考虑的是有些函数[1, 1, 1], [1], [1, 1]三种不同的参数可以算出不同的值，所以上面的方案已经不适用了，我们可以从参数的特征下手，可以发现参数列表的长度是区分它们的关键，所以我们在用set和get的时候，最前面加入一个参数列表的长度。
还有一个很重要的就是，函数可能会返回undefined，null之类的东西，所以我们需要多记录一个map，来确定我们是否已经开点了。

code:

/**
 * @param {Function} fn
 * @return {Function}
 */
function memoize(fn) {
    let mp = new Map()  
    let st = new Map() 
    function setFn(L, v) {
        let tmp = mp, stp = st 
        for(let i = 0; i < L.length; ++ i ) {
            if(i < L.length - 1) {
                if(!stp.get(L[i])) {
                    tmp.set(L[i], new Map())
                    stp.set(L[i], new Map()) 
                }
                tmp = tmp.get(L[i])   
                stp = stp.get(L[i]) 
                continue 
            }
            // console.log(tmp)
            tmp.set(L[i], v) 
            stp.set(L[i], true) 
        }
    }

    function get(L) {
        let tmp = mp
        let stp = st 
        for(let i = 0; i < L.length; ++ i ) {
            if(stp.get(L[i])) {
                tmp = tmp.get(L[i])
                stp = stp.get(L[i])  
            }
            else {
                return "无解"
            }
        }
        return tmp 
    }

    return function(...args) {
        const cs = [args.length]
        cs.push(...args) 
        const res = get(cs) 
        if(res != "无解") return res
        const aim = fn(...args)
        setFn(cs, aim)  
        return aim 
    }
}


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