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 = mpfor(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 resconst 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 = mplet 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 resconst 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 */