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