# 2623. Memoize ###### tags: `leetcode 30 days js challenge` `Medium` [2623. Memoize](https://leetcode.com/problems/memoize/) ### 題目描述 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. ### 範例 **Example 1:** ``` Input "sum" ["call","call","getCallCount","call","getCallCount"] [[2,2],[2,2],[],[1,2],[]] Output [4,4,1,3,2] Explanation const sum = (a, b) => a + b; const memoizedSum = memoize(sum); memoizedSum(2, 2); // Returns 4. sum() was called as (2, 2) was not seen before. memoizedSum(2, 2); // Returns 4. However sum() was not called because the same inputs were seen before. // Total call count: 1 memoizedSum(1, 2); // Returns 3. sum() was called as (1, 2) was not seen before. // Total call count: 2 ``` **Example 2:** ``` Input "factorial" ["call","call","call","getCallCount","call","getCallCount"] [[2],[3],[2],[],[3],[]] Output [2,6,2,2,6,2] Explanation const factorial = (n) => (n <= 1) ? 1 : (n * factorial(n - 1)); const memoFactorial = memoize(factorial); memoFactorial(2); // Returns 2. memoFactorial(3); // Returns 6. memoFactorial(2); // Returns 2. However factorial was not called because 2 was seen before. // Total call count: 2 memoFactorial(3); // Returns 6. However factorial was not called because 3 was seen before. // Total call count: 2 ``` **Example 3:** ``` Input "fib" ["call","getCallCount"] [[5],[]] Output [8,1] Explanation fib(5) = 8 // Total call count: 1 ``` **Constraints**: - 0 <= a, b <= 10<sup>5</sup> - `1 <= n <= 10` - `at most 105 function calls` - `at most 105 attempts to access callCount` - `input function is sum, fib, or factorial` ### 解答 #### TypeScript ```typescript= type Fn = (...params: any) => any; function memoize(fn: Fn): Fn { const map = new Map(); return (...args) => { const paramsKey = JSON.stringify(args); if (map.has(paramsKey)) { return map.get(paramsKey); } map.set(paramsKey, fn(...args)); return map.get(paramsKey); }; } // one liner const memoize = (fn: Fn, cache = {}): Fn => (...args) => (cache[args.join()] = cache[args.join()] ?? fn(...args)); ``` > [name=Sheep][time=Sat, May 13, 2023] ### Reference [回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)