编写记忆化函数

问题描述

编写一个名为 memoize 的函数，它接收另一个函数作为输入，并返回一个记忆化的版本。记忆化函数在接收到相同的输入时，不会重新计算结果，而是从缓存中返回已计算过的值。

假设提供的输入函数有以下三种类型：

• sum(a: number, b: number): number 接收两个整数参数并返回它们的和。
• fib(n: number): number 计算第 n 个斐波那契数列项，遵循递归规则：fib(n) = fib(n - 1) + fib(n - 2)（当 n <= 1 时返回 1）。
• factorial(n: number): number 计算阶乘，遵循递归规则：factorial(n) = n * factorial(n - 1)（当 n <= 1 时返回 1）。

示例

        

          
            
            markdown
          
          
            
            
          
        
        

          
1234567891011121314151617181920212223
          示例 1：
输入：
"sum"
["call","call","getCallCount","call","getCallCount"]
[[2,2],[2,2],[],[1,2],[]]
输出：
[4,4,1,3,2]

示例 2：
输入：
"factorial"
["call","call","call","getCallCount","call","getCallCount"]
[[2],[3],[2],[],[3],[]]
输出：
[2,6,2,2,6,2]

示例 3：
输入：
"fib"
["call","getCallCount"]
[[5],[]]
输出：
[8,1]
        
      

约束条件

• 0 <= a, b <= 10^5
• 1 <= n <= 10
• 最多进行 10^5 次函数调用
• 最多尝试访问 callCount 10^5 次
• 输入函数只能是 sum, fib, 或 factorial

解决方案

        

          
            
            TypeScript
          
          
            
            
          
        
        

          
1234567891011121314151617181920212223242526
          type Fn = (...params: any) => any

function memoize(fn: Fn): Fn {
    const map: Map<string, number> = new Map<string, number>()
    return function(...args: any[]) {
        const str = JSON.stringify(args)
        if (map.has(str)) {
            return map.get(str)
        }
        const result = fn(...args)
        map.set(str, result)
        return result
    }
}

/**
 * 示例用法：
 * let callCount = 0;
 * const memoizedSum = memoize(function (a: number, b: number) {
 *	 callCount += 1;
 *   return a + b;
 * })
 * memoizedSum(2, 3) // 5
 * memoizedSum(2, 3) // 5
 * console.log(callCount) // 1
 */
        
      

注意：上述代码片段中的 memoize 函数实现需要对不同的输入函数类型进行适配，确保能够正确地缓存和检索计算结果。由于 TypeScript 类型系统在此处无法自动推断出具体函数的参数类型，因此实际实现中可能需要针对 sum、fib 和 factorial 分别编写相应的记忆化封装函数，或者提供更精确的类型注解。