LeetCode JavaScript 30 Days Challenge – Day9 – 2623. Memoize

    AllenLi
    LeetCode JavaScript 30 Days ChallengeLeetCode Js-Hash Table

    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

    Related Posts