Given a function fn, return a memoized version of that function.
A memoized function is a function that will never be called twice with the same inputs. Instead it will return a cached value.
You can assume there are 3 possible input functions: sum, fib, and factorial.
– sum accepts two integers a and b and returns a + b.
– fib accepts a single integer n and returns 1 if n <= 1 or fib(n - 1) + fib(n - 2) otherwise.
- factorial accepts a single integer n and returns 1 if n <= 1 or factorial(n - 1) * n otherwise.
給定一個函式 fn,回傳該函數的一個記憶化版本。 一個記憶化函式是一個永遠不會以相同的輸入調用兩次的函數。反之,它會返回一個緩存的值。 你可以假設有三個可能的輸入函式: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。
Example 1:
Input "sum" ["call","call","getCallCount","call","getCallCount"] [[2,2],[2,2],[],[1,2],[]] Output [4,4,1,3,2]
Example 2:
Input "factorial" ["call","call","call","getCallCount","call","getCallCount"] [[2],[3],[2],[],[3],[]] Output [2,6,2,2,6,2]
Example 3:
Input "fib" ["call","getCallCount"] [[5],[]] Output [8,1]
solution:
我們在函式內部中建立一個空的物件 cache 來當作緩存的位置,
然後我們運用展開運算子 …args 來傳送陣列中的元素,
同時運用 JSON.stringify(args) 將元素轉成字串 key,
且將此字串 key 當作緩存物件 cache 的鍵,
如果 key 不存在於 cache 中,表示這是一個新的輸入,我們需要執行原始函式 fn(…args) 來計算結果。
並將結果存入緩存 cache[key] 中,以便下次使用同樣的輸入時可以直接返回結果。
這樣,每當你使用 memoize 函式來執行一個原始函式,它將會回傳一個具有記憶化功能的新函式。
這個新函式將自動緩存之前計算過的輸入和結果,以避免重複計算,從而提高執行效率。
Code 1: BigO(1)
function memoize(fn) { const cache = {} return function (...args) { const key = JSON.stringify(args) if (key in cache) { return cache[key] } cache[key] = fn(...args) return cache[key] } };
FlowChart:
Example 1
let callCount = 0; const memoizedFn = memoize(function (a, b) { callCount += 1; return a + b; }) console.log(memoizedFn(2, 2)) // 4 console.log(memoizedFn(2, 2)) // 4 console.log(callCount) // 1 console.log(memoizedFn(1, 2))// 3 console.log(callCount) // 1
Example 2
let callCount = 0; const memoizedFactorial = memoize(function (n) { callCount += 1; return (n <= 1) ? 1 : (n * memoizedFactorial(n - 1)) }) console.log(memoizedFactorial(2)) // 2 console.log(memoizedFactorial(3)) // 6 console.log(memoizedFactorial(2)) // 2 console.log(callCount) // 3 console.log(memoizedFactorial(3)) // 6 console.log(callCount) // 3
Example 3
let callCount = 0; const memoizedFib = memoize(function fib(n) { callCount += 1; return (n <= 1 ? 1 : fib(n - 1) + fib(n - 2)) }); console.log(memoizedFib(5)) // 8 console.log(callCount) //1