2630. 记忆函数 II
请你编写一个函数，它接收一个函数参数 fn，并返回该函数的 记忆化 后的结果。
记忆函数 是一个对于相同的输入永远不会被调用两次的函数。相反，它将返回一个缓存值。
fn 可以是任何函数，对于它接受什么类型的值没有限制。如果输入为 ===，则认为输入相同。
示例 1：
输入：
getInputs = () => [[2,2],[2,2],[1,2]]
fn = function (a, b) { return a + b; }
输出：[{"val":4,"calls":1},{"val":4,"calls":1},{"val":3,"calls":2}]
解释：
const inputs = getInputs();
const memoized = memoize(fn);
for (const arr of inputs) {
memoized(...arr);
}
对于参数为 (2, 2) 的输入: 2 + 2 = 4，需要调用 fn() 。
对于参数为 (2, 2) 的输入: 2 + 2 = 4，这些输入此前调用过，因此不需要调用 fn() 。
对于参数为 (1, 2) 的输入: 1 + 2 = 3，需要再次调用 fn()，总调用数为 2 。
示例 2：
输入：
getInputs = () => [[{},{}],[{},{}],[{},{}]]
fn = function (a, b) { return a + b; }
输出：[{"val":{},"calls":1},{"val":{},"calls":2},{"val":{},"calls":3}]
解释：
合并两个空对象总是会得到一个空对象。因为缓存命中，所以只有 1 次对 fn() 的调用，尽管这些对象之间没有一个是相同的（===）。
示例 3：
输入：
getInputs = () => { const o = {}; return [[o,o],[o,o],[o,o]]; }
fn = function (a, b) { return ({...a, ...b}); }
输出：[{"val":{},"calls":1},{"val":{},"calls":1},{"val":{},"calls":1}]
解释：
合并两个空对象总是会得到一个空对象。第 2 和第 3 个函数调用导致缓存命中。这是因为传入的每个对象都是相同的。
提示：
1 <= inputs.length <= 1050 <= inputs.flat().length <= 105inputs[i][j] != NaN原站题解
javascript 解法, 执行用时: 320 ms, 内存消耗: 97.9 MB, 提交时间: 2023-04-17 16:12:47
/**
* @param {Function} fn
*/
function memoize(fn) {
var index = 0;
// 参数arg -> 参数arg对应的唯一索引
var argIndexMap = new Map();
var cache = new Map();
return (...args) => {
// 参数列表[...args]对应的索引数组，根据索引数组判断是否命中缓存
var argIndexes = [];
for (var arg of args) {
if (!argIndexMap.has(arg)) {
var argIndex = index++;
argIndexMap.set(arg, argIndex);
argIndexes.push(argIndex);
} else {
argIndexes.push(argIndexMap.get(arg));
}
}
// 将索引数组转换成字符串
var key = argIndexes.join("-");
if (cache.has(key)) {
return cache.get(key);
} else {
var value = fn(...args);
cache.set(key, value);
return value;
}
}
}
/**
* 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
*/
typescript 解法, 执行用时: 320 ms, 内存消耗: 102.3 MB, 提交时间: 2023-04-17 16:12:21
type Fn = (...params: any) => any
function memoize(fn: Fn): Fn {
const idPool = new Map<unknown, number>()
const cache: Map<string, ReturnType<Fn>> = new Map()
return function (...args: Parameters<Fn>): ReturnType<Fn> {
const key = args.map(getId).join(',')
if (cache.has(key)) {
return cache.get(key)!
}
const res = fn(...args)
cache.set(key, res)
return res
}
function getId(o: unknown): number {
if (idPool.has(o)) {
return idPool.get(o)!
}
const id = idPool.size
idPool.set(o, id)
return id
}
}
/**
* 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
*/