刷题记录帖子

2634. Filter Elements from Array
Easy
conpanies icon
Companies
Hint
Given an integer array arr and a filtering function fn, return a filtered array filteredArr.

The fn function takes one or two arguments:

arr[i] - number from the arr
i - index of arr[i]
filteredArr should only contain the elements from the arr for which the expression fn(arr[i], i) evaluates to a truthy value. A truthy value is a value where Boolean(value) returns true.

Please solve it without the built-in Array.filter method.



Example 1:

Input: arr = [0,10,20,30], fn = function greaterThan10(n) { return n > 10; }
Output: [20,30]
Explanation:
const newArray = filter(arr, fn); // [20, 30]
The function filters out values that are not greater than 10
Example 2:

Input: arr = [1,2,3], fn = function firstIndex(n, i) { return i === 0; }
Output: [1]
Explanation:
fn can also accept the index of each element
In this case, the function removes elements not at index 0
Example 3:

Input: arr = [-2,-1,0,1,2], fn = function plusOne(n) { return n + 1 }
Output: [-2,0,1,2]
Explanation:
Falsey values such as 0 should be filtered out


Constraints:

0 <= arr.length <= 1000
-109 <= arr[i] <= 109

代码解释什么是“真值（Truthy）”：在 JavaScript/TypeScript 中，条件判断（如 if (...)）会自动进行隐式类型转换。除了以下 6 个虚值（Falsy）外，其他所有值都被视作真值：false0（包含 -0 和 0n）""（空字符串）nullundefinedNaN示例 3 中 fn(-1 + 1) = 0，由于 0 是虚值，因此被成功过滤出去。遍历与参数传递：使用标准的 for 循环按顺序遍历 arr。按照题意，fn 接收两个参数：第一个是当前元素的值 arr[i]，第二个是当前元素的索引 i。内存效率：由于无法预知最终会有多少个元素符合过滤条件，因此声明一个空数组 filteredArr 并通过 .push() 动态添加匹配项是最直观且高效的处理方式。复杂度分析时间复杂度：$\mathcal{O}(N)$，其中 $N$ 是数组 arr 的长度。需要完整遍历数组一次。空间复杂度：$\mathcal{O}(N)$，最坏情况下（所有元素都满足过滤条件），需要创建一个长度为 $N$ 的新数组存储结果。

1. type Fn = (n: number, i: number) => any
   
2. 
   
3. function filter(arr: number[], fn: Fn): number[] {
   
4.     const filteredArr: number[] = [];
   
5.    
   
6.     // 遍历原数组的所有元素
   
7.     for (let i = 0; i < arr.length; i++) {
   
8.         // 如果 fn 返回真值（Truthy），将元素放入结果数组中
   
9.         if (fn(arr[i], i)) {
   
10.             filteredArr.push(arr[i]);
    
11.         }
    
12.     }
    
13.    
    
14.     return filteredArr;
    
15. };

复制代码

2629. Function Composition
Easy
conpanies icon
Companies
Hint
Given an array of functions [f1, f2, f3, ..., fn], return a new function fn that is the function composition of the array of functions.

The function composition of [f(x), g(x), h(x)] is fn(x) = f(g(h(x))).

The function composition of an empty list of functions is the identity function f(x) = x.

You may assume each function in the array accepts one integer as input and returns one integer as output.



Example 1:

Input: functions = [x => x + 1, x => x * x, x => 2 * x], x = 4
Output: 65
Explanation:
Evaluating from right to left ...
Starting with x = 4.
2 * (4) = 8
(8) * (8) = 64
(64) + 1 = 65
Example 2:

Input: functions = [x => 10 * x, x => 10 * x, x => 10 * x], x = 1
Output: 1000
Explanation:
Evaluating from right to left ...
10 * (1) = 10
10 * (10) = 100
10 * (100) = 1000
Example 3:

Input: functions = [], x = 42
Output: 42
Explanation:
The composition of zero functions is the identity function


Constraints:

-1000 <= x <= 1000
0 <= functions.length <= 1000
all functions accept and return a single integer

这道题要求实现函数组合（Function Composition）。在数学中，函数组合 $(f \circ g \circ h)(x)$ 定义为从右往左依次调用：$f(g(h(x)))$。如果传入的函数数组为空 []，则返回恒等函数（Identity Function），即原样返回 $x$。


我们可以使用 JavaScript 的 Array.prototype.reduceRight 来优雅地实现从右向左的链式计算。

代码解释
为什么选择 reduceRight：

reduceRight 的工作机制与 reduce 完全相同，唯一的区别是它是从右向左遍历数组的。

对于 [f, g, h] 和输入 x：

第 1 步：acc 初始值为 x，执行 h(x)，结果赋给下一次的 acc。

第 2 步：执行 g(h(x))。

第 3 步：执行 f(g(h(x)))。

这正好契合函数组合的右向左执行顺序。

处理空数组：

当 functions 数组为空 [] 时，reduceRight 不会执行回调函数，而是直接返回初始值 x。这完美符合“空数组时返回恒等函数”的要求。

1. type F = (x: number) => number;
   
2. 
   
3. function compose(functions: F[]): F {
   
4.    
   
5.     return function(x) {
   
6. 
   
7.         // reduceRight 会从数组末尾（最右边）开始向前迭代
   
8.         // 初始值累加器 acc 设置为 x
   
9.         return functions.reduceRight((acc, fn) => fn(acc), x);
   
10.     }
    
11. };
    
12. 
    
13. /**
    
14. * const fn = compose([x => x + 1, x => 2 * x])
    
15. * fn(4) // 9
    
16. */

复制代码

传统循环写解答法（性能替代方案）：
如果用普通的 for 循环倒序遍历，代码如下：

1. type F = (x: number) => number;
   
2. 
   
3. function compose(functions: F[]): F {
   
4.    
   
5.     return function(x) {
   
6. let result = x;
   
7.         for (let i = functions.length - 1; i >= 0; i--) {
   
8.             result = functions[i](result);
   
9.         }
   
10.         return result;
    
11.     }
    
12. };
    
13. 
    
14. /**
    
15. * const fn = compose([x => x + 1, x => 2 * x])
    
16. * fn(4) // 9
    
17. */

复制代码

2626. Array Reduce Transformation
Easy
conpanies icon
Companies
Hint
Given an integer array nums, a reducer function fn, and an initial value init, return the final result obtained by executing the fn function on each element of the array, sequentially, passing in the return value from the calculation on the preceding element.

This result is achieved through the following operations: val = fn(init, nums[0]), val = fn(val, nums[1]), val = fn(val, nums[2]), ... until every element in the array has been processed. The ultimate value of val is then returned.

If the length of the array is 0, the function should return init.

Please solve it without using the built-in Array.reduce method.



Example 1:

Input:
nums = [1,2,3,4]
fn = function sum(accum, curr) { return accum + curr; }
init = 0
Output: 10
Explanation:
initially, the value is init=0.
(0) + nums[0] = 1
(1) + nums[1] = 3
(3) + nums[2] = 6
(6) + nums[3] = 10
The final answer is 10.
Example 2:

Input:
nums = [1,2,3,4]
fn = function sum(accum, curr) { return accum + curr * curr; }
init = 100
Output: 130
Explanation:
initially, the value is init=100.
(100) + nums[0] * nums[0] = 101
(101) + nums[1] * nums[1] = 105
(105) + nums[2] * nums[2] = 114
(114) + nums[3] * nums[3] = 130
The final answer is 130.
Example 3:

Input:
nums = []
fn = function sum(accum, curr) { return 0; }
init = 25
Output: 25
Explanation: For empty arrays, the answer is always init.


Constraints:

0 <= nums.length <= 1000
0 <= nums[i] <= 1000
0 <= init <= 1000

1. type Fn = (accum: number, curr: number) => number
   
2. 
   
3. function reduce(nums: number[], fn: Fn, init: number): number {
   
4.     // 1. 初始化累加器为初始值 init
   
5.     let accum = init;
   
6.    
   
7.     // 2. 依次遍历数组中的每个元素
   
8.     for (let i = 0; i < nums.length; i++) {
   
9.         // 将前一次计算的结果 accum 和当前元素 nums[i] 传给 fn，并更新 accum
   
10.         accum = fn(accum, nums[i]);
    
11.     }
    
12.    
    
13.     // 3. 返回最终的累加结果
    
14.     return accum;
    
15. };

复制代码

2622. Cache With Time Limit
Medium
conpanies icon
Companies
Hint
Write a class that allows getting and setting key-value pairs, however a time until expiration is associated with each key.

The class has three public methods:

set(key, value, duration): accepts an integer key, an integer value, and a duration in milliseconds. Once the duration has elapsed, the key should be inaccessible. The method should return true if the same un-expired key already exists and false otherwise. Both the value and duration should be overwritten if the key already exists.

get(key): if an un-expired key exists, it should return the associated value. Otherwise it should return -1.

count(): returns the count of un-expired keys.



Example 1:

Input:
actions = ["TimeLimitedCache", "set", "get", "count", "get"]
values = [[], [1, 42, 100], [1], [], [1]]
timeDelays = [0, 0, 50, 50, 150]
Output: [null, false, 42, 1, -1]
Explanation:
At t=0, the cache is constructed.
At t=0, a key-value pair (1: 42) is added with a time limit of 100ms. The value doesn't exist so false is returned.
At t=50, key=1 is requested and the value of 42 is returned.
At t=50, count() is called and there is one active key in the cache.
At t=100, key=1 expires.
At t=150, get(1) is called but -1 is returned because the cache is empty.
Example 2:

Input:
actions = ["TimeLimitedCache", "set", "set", "get", "get", "get", "count"]
values = [[], [1, 42, 50], [1, 50, 100], [1], [1], [1], []]
timeDelays = [0, 0, 40, 50, 120, 200, 250]
Output: [null, false, true, 50, 50, -1, 0]
Explanation:
At t=0, the cache is constructed.
At t=0, a key-value pair (1: 42) is added with a time limit of 50ms. The value doesn't exist so false is returned.
At t=40, a key-value pair (1: 50) is added with a time limit of 100ms. A non-expired value already existed so true is returned and the old value was overwritten.
At t=50, get(1) is called which returned 50.
At t=120, get(1) is called which returned 50.
At t=140, key=1 expires.
At t=200, get(1) is called but the cache is empty so -1 is returned.
At t=250, count() returns 0 because the cache is empty.


Constraints:

0 <= key, value <= 109
0 <= duration <= 1000
1 <= actions.length <= 100
actions.length === values.length
actions.length === timeDelays.length
0 <= timeDelays[i] <= 1450
actions[i] is one of "TimeLimitedCache", "set", "get" and "count"
First action is always "TimeLimitedCache" and must be executed immediately, with a 0-millisecond delay

这道题要求设计一个支持带过期时间的键值缓存（Time-Limited Cache）的类。

我们需要实现三个核心方法：

set(key, value, duration)：设置键值对并启动过期定时器。如果该键已存在且未过期，取消原定时器、覆写值和过期时间，并返回 true；否则返回 false。

get(key)：如果键存在且未过期，返回对应的值；否则返回 -1。

count()：返回当前尚未过期的键的数量。

代码解释缓存状态管理 (Map)：我们使用 Map 来同时存储缓存的 value 和该 key 专属的定时器句柄 timer。TypeScript 中 ReturnType<typeof setTimeout> 可以完美兼容 Node.js 平台与浏览器环境的定时器类型。set 方法覆写逻辑：在设置一个 key 时，先通过 this.cache.get(key) 检查是否已经存在该键。如果已存在，必须先调用 clearTimeout(existingEntry.timer) 取消掉之前的定时器，否则原定时器到期后仍然会删除当前最新的数据。新设一个 setTimeout，触发时从 Map 中将该 key 删除（保持 Map 内数据均为有效未过期数据）。count 方法的极简实现：因为每个 key 过期后都会被 setTimeout 的回调函数自动执行 delete(key) 清理掉，所以 this.cache.size 就精确地等于当前“未过期的键的数量”，时间复杂度达到 $\mathcal{O}(1)$。复杂度分析时间复杂度：set(key, value, duration): $\mathcal{O}(1)$get(key): $\mathcal{O}(1)$count(): $\mathcal{O}(1)$空间复杂度：$\mathcal{O}(K)$，其中 $K$ 是当前缓存中尚未过期的键值对数量。

1. class TimeLimitedCache {
   
2.     // 内部使用 Map 维护 key 到 { value, timer } 的映射
   
3.     private cache: Map<number, { value: number; timer: ReturnType<typeof setTimeout> }>;
   
4. 
   
5.     constructor() {
   
6.         this.cache = new Map();
   
7.     }
   
8.    
   
9.     set(key: number, value: number, duration: number): boolean {
   
10.         const existingEntry = this.cache.get(key);
    
11.         const hasKey = existingEntry !== undefined;
    
12.         
    
13.         // 如果键已存在且未过期，清除上一次的定时器，避免旧定时器误删新值
    
14.         if (hasKey) {
    
15.             clearTimeout(existingEntry.timer);
    
16.         }
    
17.         
    
18.         // 创建新的定时器，在 duration 毫秒后自动从 cache 中删除该键
    
19.         const timer = setTimeout(() => {
    
20.             this.cache.delete(key);
    
21.         }, duration);
    
22.         
    
23.         // 更新/保存最新的值和定时器句柄
    
24.         this.cache.set(key, { value, timer });
    
25.         
    
26.         return hasKey;
    
27.     }
    
28.    
    
29.     get(key: number): number {
    
30.         if (this.cache.has(key)) {
    
31.             return this.cache.get(key)!.value;
    
32.         }
    
33.         return -1;
    
34.     }
    
35.    
    
36.     count(): number {
    
37.         // 由于过期的键会在 setTimeout 中被删除，Map 的 size 实时反映未过期的键数量
    
38.         return this.cache.size;
    
39.     }
    
40. }
    
41. 
    
42. /**
    
43. * const timeLimitedCache = new TimeLimitedCache()
    
44. * timeLimitedCache.set(1, 42, 1000); // false
    
45. * timeLimitedCache.get(1) // 42
    
46. * timeLimitedCache.count() // 1
    
47. */

复制代码

2777. Date Range Generator
Medium
Given a start date start, an end date end, and a positive integer step, return a generator object that yields dates in the range from start to end inclusive.

The value of step indicates the number of days between consecutive yielded values.

All yielded dates must be in the string format YYYY-MM-DD.



Example 1:

Input: start = "2023-04-01", end = "2023-04-04", step = 1
Output: ["2023-04-01","2023-04-02","2023-04-03","2023-04-04"]
Explanation:
const g = dateRangeGenerator(start, end, step);
g.next().value // '2023-04-01'
g.next().value // '2023-04-02'
g.next().value // '2023-04-03'
g.next().value // '2023-04-04'
Example 2:

Input: start = "2023-04-10", end = "2023-04-20", step = 3
Output: ["2023-04-10","2023-04-13","2023-04-16","2023-04-19"]
Explanation:
const g = dateRangeGenerator(start, end, step);
g.next().value // '2023-04-10'
g.next().value // '2023-04-13'
g.next().value // '2023-04-16'
g.next().value // '2023-04-19'
Example 3:

Input: start = "2023-04-10", end = "2023-04-10", step = 1
Output: ["2023-04-10"]
Explanation:
const g = dateRangeGenerator(start, end, step);
g.next().value // '2023-04-10'


Constraints:

new Date(start) <= new Date(end)
start and end dates are in the string format YYYY-MM-DD
0 <= The difference in days between the start date and the end date <= 1500
1 <= step <= 1000

1. function* dateRangeGenerator(start: string, end: string, step: number) : Generator<string> {
   
2.     // 1. 将输入的日期字符串转换为 Date 对象
   
3.     let currentDate = new Date(start);
   
4.     const endDate = new Date(end);
   
5. 
   
6.     // 2. 循环生成日期，直到当前日期超过结束日期
   
7.     while (currentDate <= endDate) {
   
8.         // 将当前 Date 对象格式化为 YYYY-MM-DD 格式
   
9.         const year = currentDate.getFullYear();
   
10.         // getMonth() 返回 0-11，需要 +1，并补充前导零
    
11.         const month = String(currentDate.getMonth() + 1).padStart(2, '0');
    
12.         // getDate() 返回 1-31，补充前导零
    
13.         const day = String(currentDate.getDate()).padStart(2, '0');
    
14. 
    
15.         // 通过 yield 产生当前格式化的日期字符串
    
16.         yield `${year}-${month}-${day}`;
    
17. 
    
18.         // 3. 将当前日期增加 step 天
    
19.         currentDate.setDate(currentDate.getDate() + step);
    
20.     }
    
21. };
    
22. 
    
23. /**
    
24. * const g = dateRangeGenerator('2023-04-01', '2023-04-04', 1);
    
25. * g.next().value; // '2023-04-01'
    
26. * g.next().value; // '2023-04-02'
    
27. * g.next().value; // '2023-04-03'
    
28. * g.next().value; // '2023-04-04'
    
29. * g.next().done; // true
    
30. */

复制代码

2624. Snail Traversal
Medium
Hint
Write code that enhances all arrays such that you can call the snail(rowsCount, colsCount) method that transforms the 1D array into a 2D array organised in the pattern known as snail traversal order. Invalid input values should output an empty array. If rowsCount * colsCount !== nums.length, the input is considered invalid.

Snail traversal order starts at the top left cell with the first value of the current array. It then moves through the entire first column from top to bottom, followed by moving to the next column on the right and traversing it from bottom to top. This pattern continues, alternating the direction of traversal with each column, until the entire current array is covered. For example, when given the input array [19, 10, 3, 7, 9, 8, 5, 2, 1, 17, 16, 14, 12, 18, 6, 13, 11, 20, 4, 15] with rowsCount = 5 and colsCount = 4, the desired output matrix is shown below. Note that iterating the matrix following the arrows corresponds to the order of numbers in the original array.



Traversal Diagram



Example 1:

Input:
nums = [19, 10, 3, 7, 9, 8, 5, 2, 1, 17, 16, 14, 12, 18, 6, 13, 11, 20, 4, 15]
rowsCount = 5
colsCount = 4
Output:
[
[19,17,16,15],
[10,1,14,4],
[3,2,12,20],
[7,5,18,11],
[9,8,6,13]
]
Example 2:

Input:
nums = [1,2,3,4]
rowsCount = 1
colsCount = 4
Output: [[1, 2, 3, 4]]
Example 3:

Input:
nums = [1,3]
rowsCount = 2
colsCount = 2
Output: []
Explanation: 2 multiplied by 2 is 4, and the original array [1,3] has a length of 2; therefore, the input is invalid.


Constraints:

0 <= nums.length <= 250
1 <= nums[i] <= 1000
1 <= rowsCount <= 250
1 <= colsCount <= 250


解题思路与关键点说明边界处理：如果数组长度不等于 rowsCount * colsCount，输入不合法，直接返回 []。二维数组初始化：使用 Array.from({ length: rowsCount }, () => []) 创建一个拥有 rowsCount 行的空二维数组。蛇形填充逻辑：原数组元素按照列优先顺序填充：第 0 列：占用原数组索引 $0 \sim (\text{rowsCount} - 1)$第 1 列：占用原数组索引 $\text{rowsCount} \sim (2 \times \text{rowsCount} - 1)$，以此类推。列索引计算：col = Math.floor(i / rowsCount)行索引计算：根据列索引的奇偶性决定填充方向：偶数列 (col % 2 === 0)：自顶向下遍历，行索引为 i % rowsCount。奇数列 (col % 2 === 1)：自底向上遍历，行索引为 rowsCount - 1 - (i % rowsCount)

1. interface Array<T> {
   
2.     snail(rowsCount: number, colsCount: number): number[][];
   
3. }
   
4. 
   
5. 
   
6. Array.prototype.snail = function(rowsCount: number, colsCount: number): number[][] {
   
7.     // 1. 校验输入合法性：元素总数必须等于 rowsCount * colsCount
   
8.     if (this.length !== rowsCount * colsCount) {
   
9.         return [];
   
10.     }
    
11. 
    
12.     // 2. 初始化 rowsCount 行的二维数组
    
13.     const result: number[][] = Array.from({ length: rowsCount }, () => []);
    
14. 
    
15.     // 3. 遍历原数组的每个元素，计算对应的行号和列号
    
16.     for (let i = 0; i < this.length; i++) {
    
17.         // 计算当前元素属于第几列
    
18.         const col = Math.floor(i / rowsCount);
    
19.         
    
20.         // 计算行号：
    
21.         // 偶数列（0, 2, 4...）从上到下填充：行号为 i % rowsCount
    
22.         // 奇数列（1, 3, 5...）从下到上填充：行号为 rowsCount - 1 - (i % rowsCount)
    
23.         const row = (col % 2 === 0)
    
24.             ? (i % rowsCount)
    
25.             : (rowsCount - 1 - (i % rowsCount));
    
26. 
    
27.         result[row][col] = this[i];
    
28.     }
    
29. 
    
30.     return result;
    
31. }
    
32. 
    
33. /**
    
34. * const arr = [1,2,3,4];
    
35. * arr.snail(1,4); // [[1,2,3,4]]
    
36. */

复制代码

2623. Memoize
Medium
conpanies icon
Companies
Hint
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. Assume that if a value has already been cached for the arguments (b, a) where a != b, it cannot be used for the arguments (a, b). For example, if the arguments are (3, 2) and (2, 3), two separate calls should be made.
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:
fnName = "sum"
actions = ["call","call","getCallCount","call","getCallCount"]
values = [[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); // "call" - returns 4. sum() was called as (2, 2) was not seen before.
memoizedSum(2, 2); // "call" - returns 4. However sum() was not called because the same inputs were seen before.
// "getCallCount" - total call count: 1
memoizedSum(1, 2); // "call" - returns 3. sum() was called as (1, 2) was not seen before.
// "getCallCount" - total call count: 2
Example 2:

Input:
fnName = "factorial"
actions = ["call","call","call","getCallCount","call","getCallCount"]
values = [[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); // "call" - returns 2.
memoFactorial(3); // "call" - returns 6.
memoFactorial(2); // "call" - returns 2. However factorial was not called because 2 was seen before.
// "getCallCount" - total call count: 2
memoFactorial(3); // "call" - returns 6. However factorial was not called because 3 was seen before.
// "getCallCount" - total call count: 2
Example 3:

Input:
fnName = "fib"
actions = ["call","getCallCount"]
values = [[5],[]]
Output: [8,1]
Explanation:
fib(5) = 8 // "call"
// "getCallCount" - total call count: 1


Constraints:

0 <= a, b <= 105
1 <= n <= 10
1 <= actions.length <= 105
actions.length === values.length
actions[i] is one of "call" and "getCallCount"
fnName is one of "sum", "factorial" and "fib"


解题思路与关键点说明
缓存数据结构：

使用 Map 或普通对象（Object）保存以参数组合作为 key、计算结果作为 value 的映射。由于频繁检索，Map 的查询性能比普通对象稍胜一筹。

序列化 Key 方案：

使用 args.join(',') 将数字数组转换为唯一的字符串 key：

例如 [2, 3] 变为 "2,3"；[2] 变为 "2"。

关于参数顺序：题目明确指出 sum(3, 2) 和 sum(2, 3) 属于不同调用，不能混用缓存。因为 args 的元素顺序不同，join(',') 恰好会生成不同的 key（分别为 "3,2" 和 "2,3"），完美契合要求。

对于单参数函数（fib / factorial）：args[0] 或 String(args[0]) 也能直接作为 key。args.join(',') 统一兼容了单参数和多参数场景。

1. type Fn = (...params: number[]) => number;
   
2. 
   
3. function memoize(fn: Fn): Fn {
   
4.     // 创建一个哈希表用于存储参数组合与结果的映射
   
5.     const cache = new Map<string, number>();
   
6. 
   
7.     return function(...args: number[]): number {
   
8.         // 1. 将传入的参数序列化为唯一的 key 字符串
   
9.         const key = args.join(',');
   
10. 
    
11.         // 2. 检查缓存中是否已有该结果
    
12.         if (cache.has(key)) {
    
13.             return cache.get(key)!;
    
14.         }
    
15. 
    
16.         // 3. 若无缓存，调用原函数计算结果，存入缓存并返回
    
17.         const result = fn(...args);
    
18.         cache.set(key, result);
    
19.         return result;
    
20.     };
    
21. }

复制代码

2632. Curry
Medium
Hint
Given a function fn, return a curried version of that function.

A curried function is a function that accepts fewer or an equal number of parameters as the original function and returns either another curried function or the same value the original function would have returned.

In practical terms, if you called the original function like sum(1,2,3), you would call the curried version like csum(1)(2)(3), csum(1)(2,3), csum(1,2)(3), or csum(1,2,3). All these methods of calling the curried function should return the same value as the original.



Example 1:

Input:
fn = function sum(a, b, c) { return a + b + c; }
inputs = [[1],[2],[3]]
Output: 6
Explanation:
The code being executed is:
const curriedSum = curry(fn);
curriedSum(1)(2)(3) === 6;
curriedSum(1)(2)(3) should return the same value as sum(1, 2, 3).
Example 2:

Input:
fn = function sum(a, b, c) { return a + b + c; }
inputs = [[1,2],[3]]
Output: 6
Explanation:
curriedSum(1, 2)(3) should return the same value as sum(1, 2, 3).
Example 3:

Input:
fn = function sum(a, b, c) { return a + b + c; }
inputs = [[],[],[1,2,3]]
Output: 6
Explanation:
You should be able to pass the parameters in any way, including all at once or none at all.
curriedSum()()(1, 2, 3) should return the same value as sum(1, 2, 3).
Example 4:

Input:
fn = function life() { return 42; }
inputs = [[]]
Output: 42
Explanation:
currying a function that accepts zero parameters should effectively do nothing.
curriedLife() === 42


Constraints:

1 <= inputs.length <= 1000
0 <= inputs[i][j] <= 105
0 <= fn.length <= 1000
inputs.flat().length == fn.length
function parameters explicitly defined
If fn.length > 0 then the last array in inputs is not empty
If fn.length === 0 then inputs.length === 1


柯里化（Currying）是函数式编程中的核心概念，它的本质是将一个接受多个参数的函数，转化为一系列接受部分参数并返回新函数的形式。

解题思路与核心机制
判断的核心逻辑非常清晰：累积传入的参数数量 vs 原函数所需的参数数量 (fn.length)。

原函数的形参个数：在 JavaScript/TypeScript 中，通过 fn.length 可以获取函数定义时的参数个数（例如 sum(a, b, c) 的 fn.length 为 3）。

递归收集参数：

每次调用柯里化函数时，将本次传入的参数与之前已保存的参数拼接合并。

如果合并后的参数总数 大于或等于 fn.length：说明参数已经收集齐了，直接执行原函数 fn(...args) 并返回结果。

如果合并后的参数总数 小于 fn.length：说明参数还没收集够，返回一个新的函数，继续接收并拼接后续参数。

1. function curry(fn: Function): Function {
   
2.    
   
3.     return function curried(...args) {
   
4.         // 如果当前收到的参数数量 >= 原函数需要的参数数量
   
5.         if (args.length >= fn.length) {
   
6.             // 直接执行原函数并返回结果
   
7.             return fn(...args);
   
8.         }
   
9.         
   
10.         // 参数不够，返回一个新函数继续接收剩余参数
    
11.         return function(...nextArgs: any[]) {
    
12.             // 将旧参数 args 和新参数 nextArgs 拼接在一起，递归调用 curried
    
13.             return curried(...args, ...nextArgs);
    
14.         };
    
15.     }
    
16. };
    
17. 
    
18. /**
    
19. * function sum(a, b) { return a + b; }
    
20. * const csum = curry(sum);
    
21. * csum(1)(2) // 3
    
22. */
    

复制代码

2631. Group By
Medium
Hint
Write code that enhances all arrays such that you can call the array.groupBy(fn) method on any array and it will return a grouped version of the array.

A grouped array is an object where each key is the output of fn(arr[i]) and each value is an array containing all items in the original array which generate that key.

The provided callback fn will accept an item in the array and return a string key.

The order of each value list should be the order the items appear in the array. Any order of keys is acceptable.

Please solve it without lodash's _.groupBy function.



Example 1:

Input:
array = [
  {"id":"1"},
  {"id":"1"},
  {"id":"2"}
],
fn = function (item) {
  return item.id;
}
Output:
{
  "1": [{"id": "1"}, {"id": "1"}],   
  "2": [{"id": "2"}]
}
Explanation:
Output is from array.groupBy(fn).
The selector function gets the "id" out of each item in the array.
There are two objects with an "id" of 1. Both of those objects are put in the first array.
There is one object with an "id" of 2. That object is put in the second array.
Example 2:

Input:
array = [
  [1, 2, 3],
  [1, 3, 5],
  [1, 5, 9]
]
fn = function (list) {
  return String(list[0]);
}
Output:
{
  "1": [[1, 2, 3], [1, 3, 5], [1, 5, 9]]
}
Explanation:
The array can be of any type. In this case, the selector function defines the key as being the first element in the array.
All the arrays have 1 as their first element so they are grouped together.
{
  "1": [[1, 2, 3], [1, 3, 5], [1, 5, 9]]
}
Example 3:

Input:
array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
fn = function (n) {
  return String(n > 5);
}
Output:
{
  "true": [6, 7, 8, 9, 10],
  "false": [1, 2, 3, 4, 5]
}
Explanation:
The selector function splits the array by whether each number is greater than 5.


Constraints:

0 <= array.length <= 105
fn returns a string

解题思路与核心机制
原型链扩展（Prototype Extension）：

需要在 Array.prototype.groupBy 上定义该方法，这样任何数组实例都可以直接调用 arr.groupBy(fn)。

上下文 this：

在 Array.prototype 的方法内部，this 指向调用该方法的数组实例。

遍历与结果映射：

遍历 this 数组中的每一个元素 item。

计算键名 const key = fn(item)。

如果结果对象中尚未存在该 key，则先初始化为空数组 result[key] = []。

将当前 item 追加到 result[key] 数组中。

1. interface Array<T> {
   
2.     groupBy(fn: (item: T) => string): Record<string, T[]>
   
3. }
   
4. 
   
5. 
   
6. Array.prototype.groupBy = function(fn) {
   
7.     const res = {};
   
8. 
   
9.     for (let i = 0; i < this.length; i++) {
   
10.         const key = fn(this[i]);
    
11.         if (res[key]) {
    
12.             res[key].push(this[i]);
    
13.         } else {
    
14.             res[key] = [this[i]];
    
15.         }
    
16.     }
    
17. 
    
18.     return res;
    
19. }
    
20. 
    
21. /**
    
22. * [1,2,3].groupBy(String) // {"1":[1],"2":[2],"3":[3]}
    
23. */

复制代码

2628. JSON Deep Equal
Medium
Hint
Given two values o1 and o2, return a boolean value indicating whether two values, o1 and o2, are deeply equal.

For two values to be deeply equal, the following conditions must be met:

If both values are primitive types, they are deeply equal if they pass the === equality check.

If both values are arrays, they are deeply equal if they have the same elements in the same order, and each element is also deeply equal according to these conditions.

If both values are objects, they are deeply equal if they have the same keys, and the associated values for each key are also deeply equal according to these conditions.

You may assume both values are the output of JSON.parse. In other words, they are valid JSON.

Please solve it without using lodash's _.isEqual() function



Example 1:

Input: o1 = {"x":1,"y":2}, o2 = {"x":1,"y":2}
Output: true
Explanation: The keys and values match exactly.
Example 2:

Input: o1 = {"y":2,"x":1}, o2 = {"x":1,"y":2}
Output: true
Explanation: Although the keys are in a different order, they still match exactly.
Example 3:

Input: o1 = {"x":null,"L":[1,2,3]}, o2 = {"x":null,"L":["1","2","3"]}
Output: false
Explanation: The array of numbers is different from the array of strings.
Example 4:

Input: o1 = true, o2 = false
Output: false
Explanation: true !== false


Constraints:

1 <= JSON.stringify(o1).length <= 105
1 <= JSON.stringify(o2).length <= 105
maxNestingDepth <= 1000

解题思路
因为题目保证输入均由 JSON.parse 生成，我们只需处理标准的 JSON 类型（null, boolean, number, string, Array, Object）：

基本类型判断：如果两者严格相等 o1 === o2，直接返回 true（可覆盖基本数据类型及指向同一引用的情况）。

类型不匹配或有 null：

如果其中一个是 null 或两者类型不为 object，则不再可能相等，直接返回 false。

数组与对象区分：

必须区分 Array 和普通 Object（Array.isArray()）。一个数组与一个对象（如 [] 与 {}）不相等。

数组匹配：长度必须一致，且索引位置上的对应元素需要递归调用 areDeeplyEqual 匹配。

对象匹配：获取两者的所有 key（Object.keys），数量必须一致；且 o2 必须包含 o1 的每一个 key，其对应的 value 也要递归匹配。

1. type JSONValue = null | boolean | number | string | JSONValue[] | { [key: string]: JSONValue };
   
2. 
   
3. function areDeeplyEqual(o1: JSONValue, o2: JSONValue): boolean {
   
4.     // 1. 基本数据类型强匹配，或指向同一引用
   
5.     if (o1 === o2) return true;
   
6. 
   
7.     // 2. 如果其中有一个是 null 或不是 object，说明类型/基本值不一致
   
8.     if (o1 === null || o2 === null || typeof o1 !== 'object' || typeof o2 !== 'object') {
   
9.         return false;
   
10.     }
    
11. 
    
12.     // 3. 检查是否一个为数组，另一个不是
    
13.     const isArr1 = Array.isArray(o1);
    
14.     const isArr2 = Array.isArray(o2);
    
15.     if (isArr1 !== isArr2) return false;
    
16. 
    
17.     // 4. 两者都是数组
    
18.     if (isArr1 && isArr2) {
    
19.         if (o1.length !== o2.length) return false;
    
20.         for (let i = 0; i < o1.length; i++) {
    
21.             if (!areDeeplyEqual(o1[i], o2[i])) return false;
    
22.         }
    
23.         return true;
    
24.     }
    
25. 
    
26.     // 5. 两者都是对象
    
27.     const keys1 = Object.keys(o1);
    
28.     const keys2 = Object.keys(o2);
    
29. 
    
30.     if (keys1.length !== keys2.length) return false;
    
31. 
    
32.     for (const key of keys1) {
    
33.         if (!Object.prototype.hasOwnProperty.call(o2, key)) return false;
    
34.         if (!areDeeplyEqual((o1 as Record<string, JSONValue>)[key], (o2 as Record<string, JSONValue>)[key])) {
    
35.             return false;
    
36.         }
    
37.     }
    
38. 
    
39.     return true;
    
40. };

复制代码