刷题记录帖子

Myron2017

2700. Differences Between Two Objects
Medium
conpanies icon
Companies
Hint
Write a function that accepts two deeply nested objects or arrays obj1 and obj2 and returns a new object representing their differences.

The function should compare the properties of the two objects and identify any changes. The returned object should only contains keys where the value is different from obj1 to obj2.

For each changed key, the value should be represented as an array [obj1 value, obj2 value]. Keys that exist in one object but not in the other should not be included in the returned object. The end result should be a deeply nested object where each leaf value is a difference array.

When comparing two arrays, the indices of the arrays are considered to be their keys.

You may assume that both objects are the output of JSON.parse.

Example 1:

Input:
obj1 = {}
obj2 = {
  "a": 1,
  "b": 2
}
Output: {}
Explanation: There were no modifications made to obj1. New keys "a" and "b" appear in obj2, but keys that are added or removed should be ignored.
Example 2:

Input:
obj1 = {
  "a": 1,
  "v": 3,
  "x": [],
  "z": {
"a": null
  }
}
obj2 = {
  "a": 2,
  "v": 4,
  "x": [],
  "z": {
"a": 2
  }
}
Output:
{
  "a": [1, 2],
  "v": [3, 4],
  "z": {
"a": [null, 2]
  }
}
Explanation: The keys "a", "v", and "z" all had changes applied. "a" was changed from 1 to 2. "v" was changed from 3 to 4. "z" had a change applied to a child object. "z.a" was changed from null to 2.
Example 3:

Input:
obj1 = {
  "a": 5,
  "v": 6,
  "z": [1, 2, 4, [2, 5, 7]]
}
obj2 = {
  "a": 5,
  "v": 7,
  "z": [1, 2, 3, [1]]
}
Output:
{
  "v": [6, 7],
  "z": {
"2": [4, 3],
"3": {
   "0": [2, 1]
}
  }
}
Explanation: In obj1 and obj2, the keys "v" and "z" have different assigned values. "a" is ignored because the value is unchanged. In the key "z", there is a nested array. Arrays are treated like objects where the indices are keys. There were two alterations to the the array: z[2] and z[3][0]. z[0] and z[1] were unchanged and thus not included. z[3][1] and z[3][2] were removed and thus not included.
Example 4:

Input:
obj1 = {
  "a": {"b": 1},
}
obj2 = {
  "a": [5],
}
Output:
{
  "a": [{"b": 1}, [5]]
}
Explanation: The key "a" exists in both objects. Since the two associated values have different types, they are placed in the difference array.
Example 5:

Input:
obj1 = {
  "a": [1, 2, {}],
  "b": false
}
obj2 = {
  "b": false,
  "a": [1, 2, {}]
}
Output:
{}
Explanation: Apart from a different ordering of keys, the two objects are identical so an empty object is returned.

Constraints:

obj1 and obj2 are valid JSON objects or arrays
2 <= JSON.stringify(obj1).length <= 104
2 <= JSON.stringify(obj2).length <= 104

这道题要求我们找出两个深度嵌套的对象或数组之间的差异。
规则很简单：只比较在两个对象中共同存在的键（或索引）。如果值不同，就记录为 [旧值, 新值]；如果完全相同，或者某个键只在其中一个对象里存在（新增或删除），则忽略它。

因为数据是深度嵌套的（对象里面有对象，数组里面有数组），所以最自然的解法是使用递归。

核心解题思路
我们可以写一个辅助函数 findDiff(v1, v2) 来专门比较两个值。比较时会有以下几种情况，我们需要按顺序依次判断：

完全相等 (===)：
如果 v1 === v2，说明没有任何修改。我们返回 undefined，用来告诉上层：“这里没变化，不用记录”。

基本数据类型或 null：
如果这两个值只要有一个是 null，或者有一个不是 object（也就是数字、字符串、布尔值等基本类型）。既然它们经过了第 1 步发现不相等，那直接返回它们的差异：[v1, v2]。
(注：在 JavaScript 里 typeof null 会返回 'object'，所以需要把 null 单独拿出来判断。)

数据结构不同（对象 vs 数组）：
如果一个是普通对象 {}，另一个是数组 []（通过 Array.isArray() 判断），那么它们的数据结构都变了，不需要再往下深挖了，直接返回差异：[v1, v2]。

深度递归比较：
排除了以上情况后，说明两者要么都是数组，要么都是普通对象。
这时，我们创建一个空的 diffObj，然后遍历 v1 里面的所有 key：

如果 v2 里面也有这个 key，我们就递归调用 findDiff(v1[key], v2[key])。

如果递归返回的结果不是 undefined，说明里面的子元素有差异，我们就把这个差异保存到 diffObj 里。

清理空壳：
在递归完当前层级后，如果发现 diffObj 里面什么都没存进去（即里面的元素都一模一样），我们就返回 undefined，防止外层套上无意义的空对象。

type JSONValue = null | boolean | number | string | JSONValue[] | { [key: string]: JSONValue };
type Obj = Record<string, JSONValue> | Array<JSONValue>;
function objDiff(obj1: Obj, obj2: Obj): Obj {
function findDiff(v1: any, v2: any): any {
// 1. Both are strictly equal
if (v1 === v2) {
return undefined;
}
// 2. Either value is null or a primitive type
if (v1 === null || v2 === null || typeof v1 !== 'object' || typeof v2 !== 'object') {
return [v1, v2];
}
// 3. Different structure types (Array vs Plain Object)
if (Array.isArray(v1) !== Array.isArray(v2)) {
return [v1, v2];
}
// 4. Both are objects or both are arrays
const diffObj: any = {};
for (const key in v1) {
if (key in v2) {
const subDiff = findDiff(v1[key], v2[key]);
// If there's a difference, append it to our local diffObj
if (subDiff !== undefined) {
diffObj[key] = subDiff;
}
}
}
// 5. If no changes were found in the nested structure, return undefined
if (Object.keys(diffObj).length === 0) {
return undefined;
}
return diffObj;
}
const result = findDiff(obj1, obj2);
// The top level is guaranteed to return an object.
// If undefined is returned, it means obj1 and obj2 are identical.
return result === undefined ? {} : result;
}

复制代码

Myron2017

2676. Throttle
Medium
Hint
Given a function fn and a time in milliseconds t, return a throttled version of that function.

A throttled function is first called without delay and then, for a time interval of t milliseconds, can't be executed but should store the latest function arguments provided to call fn with them after the end of the delay.

For instance, t = 50ms, and the function was called at 30ms, 40ms, and 60ms.

At 30ms, without delay, the throttled function fn should be called with the arguments, and calling the throttled function fn should be blocked for the following t milliseconds.

At 40ms, the function should just save arguments.

At 60ms, arguments should overwrite currently stored arguments from the second call because the second and third calls are made before 80ms. Once the delay has passed, the throttled function fn should be called with the latest arguments provided during the delay period, and it should also create another delay period of 80ms + t.

Throttle DiagramThe above diagram shows how throttle will transform events. Each rectangle represents 100ms and the throttle time is 400ms. Each color represents a different set of inputs.

Example 1:

Input:
t = 100,
calls = [
  {"t":20,"inputs":[1]}
]
Output: [{"t":20,"inputs":[1]}]
Explanation: The 1st call is always called without delay
Example 2:

Input:
t = 50,
calls = [
  {"t":50,"inputs":[1]},
  {"t":75,"inputs":[2]}
]
Output: [{"t":50,"inputs":[1]},{"t":100,"inputs":[2]}]
Explanation:
The 1st is called a function with arguments (1) without delay.
The 2nd is called at 75ms, within the delay period because 50ms + 50ms = 100ms, so the next call can be reached at 100ms. Therefore, we save arguments from the 2nd call to use them at the callback of the 1st call.
Example 3:

Input:
t = 70,
calls = [
  {"t":50,"inputs":[1]},
  {"t":75,"inputs":[2]},
  {"t":90,"inputs":[8]},
  {"t": 140, "inputs":[5,7]},
  {"t": 300, "inputs": [9,4]}
]
Output: [{"t":50,"inputs":[1]},{"t":120,"inputs":[8]},{"t":190,"inputs":[5,7]},{"t":300,"inputs":[9,4]}]
Explanation:
The 1st is called a function with arguments (1) without delay.
The 2nd is called at 75ms within the delay period because 50ms + 70ms = 120ms, so it should only save arguments.
The 3rd is also called within the delay period, and because we need just the latest function arguments, we overwrite previous ones. After the delay period, we do a callback at 120ms with saved arguments. That callback makes another delay period of 120ms + 70ms = 190ms so that the next function can be called at 190ms.
The 4th is called at 140ms in the delay period, so it should be called as a callback at 190ms. That will create another delay period of 190ms + 70ms = 260ms.
The 5th is called at 300ms, but it is after 260ms, so it should be called immediately and should create another delay period of 300ms + 70ms = 370ms.

Constraints:

0 <= t <= 1000
1 <= calls.length <= 10
0 <= calls[i].t <= 1000
0 <= calls[i].inputs[j], calls[i].inputs.length <= 10

什么是节流 (Throttle)？节流 (Throttle) 是一种限制函数执行频率的技术。如果说防抖 (Debounce) 是“等电梯，只要有人进就重新倒计时”，那么节流就是“放技能的冷却时间 (CD)”：当你按下技能键时，技能会立刻释放。但在接下来的冷却时间（比如 $t$ 毫秒）内，无论你怎么疯狂按键盘，技能都不会触发。这道题目的特殊要求：通常的基础版节流在冷却期间会直接无视后续的点击。但这道题要求更高级：第一次调用：立刻执行。冷却期间的调用：虽然不能立刻执行，但系统会记住你最后一次按键时的参数。冷却结束时：如果系统发现你在冷却期间按过键，它会立刻用最新记住的参数再执行一次函数，并重新开启下一轮的冷却倒计时。如果没有按过，就彻底解除冷却状态。

最容易让人困惑的地方是：为什么要在 timeoutCallback 里面再写一个 setTimeout 递归？假设 $t = 100$ms：0ms: 触发函数。立刻执行，开启 100ms 冷却。30ms: 再次触发函数。处于冷却中，不执行，仅保存参数。50ms: 再次触发函数。处于冷却中，不执行，覆盖保存最新的参数。100ms: 第一轮冷却结束，触发 timeoutCallback。系统发现保存了 50ms 时的参数，于是立刻执行函数。重点来了：既然在 100ms 时又执行了一次函数，那么从 100ms 到 200ms 的时间段也必须被封锁（进入新一轮冷却）。这就是为什么在 if (nextArgs) 里面，我们必须再次调用 setTimeout(timeoutCallback, t) 来续上冷却时间。

type F = (...args: any[]) => void
function throttle(fn: F, t: number): F {
let isThrottled = false;
let nextArgs: any[] | null = null;
const timeoutCallback = () => {
if (nextArgs) {
// Execute the function with the latest stored arguments
fn(...nextArgs);
nextArgs = null;
// Set another timer to respect the cooldown period
setTimeout(timeoutCallback, t);
} else {
// No arguments stored, open the function for immediate calls again
isThrottled = false;
}
};
return function (...args: any[]) {
if (isThrottled) {
// If in cooldown, just hold onto the latest arguments
nextArgs = args;
} else {
// If open, fire immediately and begin the cooldown period
fn(...args);
isThrottled = true;
setTimeout(timeoutCallback, t);
}
};
}
/**
* const throttled = throttle(console.log, 100);
* throttled("log"); // logged immediately.
* throttled("log"); // logged at t=100ms.
*/

复制代码

Myron2017

2675. Array of Objects to Matrix
Hard
Hint
Write a function that converts an array of objects arr into a matrix m.

arr is an array of objects or arrays. Each item in the array can be deeply nested with child arrays and child objects. It can also contain numbers, strings, booleans, and null values.

The first row m should be the column names. If there is no nesting, the column names are the unique keys within the objects. If there is nesting, the column names are the respective paths in the object separated by ".".

Each of the remaining rows corresponds to an object in arr. Each value in the matrix corresponds to a value in an object. If a given object doesn't contain a value for a given column, the cell should contain an empty string "".

The columns in the matrix should be in lexographically ascending order.

Example 1:

Input:
arr = [
  {"b": 1, "a": 2},
  {"b": 3, "a": 4}
]
Output:
[
  ["a", "b"],
  [2, 1],
  [4, 3]
]

Explanation:
There are two unique column names in the two objects: "a" and "b".
"a" corresponds with [2, 4].
"b" coresponds with [1, 3].
Example 2:

Input:
arr = [
  {"a": 1, "b": 2},
  {"c": 3, "d": 4},
  {}
]
Output:
[
  ["a", "b", "c", "d"],
  [1, 2, "", ""],
  ["", "", 3, 4],
  ["", "", "", ""]
]

Explanation:
There are 4 unique column names: "a", "b", "c", "d".
The first object has values associated with "a" and "b".
The second object has values associated with "c" and "d".
The third object has no keys, so it is just a row of empty strings.
Example 3:

Input:
arr = [
  {"a": {"b": 1, "c": 2}},
  {"a": {"b": 3, "d": 4}}
]
Output:
[
  ["a.b", "a.c", "a.d"],
  [1, 2, ""],
  [3, "", 4]
]

Explanation:
In this example, the objects are nested. The keys represent the full path to each value separated by periods.
There are three paths: "a.b", "a.c", "a.d".
Example 4:

Input:
arr = [
  [{"a": null}],
  [{"b": true}],
  [{"c": "x"}]
]
Output:
[
  ["0.a", "0.b", "0.c"],
  [null, "", ""],
  ["", true, ""],
  ["", "", "x"]
]

Explanation:
Arrays are also considered objects with their keys being their indices.
Each array has one element so the keys are "0.a", "0.b", and "0.c".
Example 5:

Input:
arr = [
  {},
  {},
  {},
]
Output:
[
  [],
  [],
  [],
  []
]

Explanation:
There are no keys so every row is an empty array.

Constraints:

arr is a valid JSON array
1 <= arr.length <= 1000
unique keys <= 1000

这道题的核心任务是将一个深度嵌套的 JSON 数组“拍平”（Flatten），并转换成一个类似 Excel 表格的二维数组（矩阵）。

核心解题思路
要完成这个转换，我们可以分为四个步骤：

递归扁平化 (Flatten)：
原数据里可能有对象嵌套对象，或者数组嵌套对象。我们需要写一个递归函数，把深度嵌套的结构拍平。

如果遇到的是对象或数组，就提取它的键（或索引），然后和父级的路径用 . 拼接（例如从 { a: { b: 1 } } 变成 "a.b": 1）。

如果遇到的是基本数据类型（数字、字符串、布尔值、null），说明到底了，直接把它存入一个只有一层的一维对象中。

收集并去重表头：
在扁平化的过程中，我们用一个 Set 把所有出现过的路径（列名）收集起来，确保没有重复。

字典序排序：
题目要求列名必须按字母顺序（字典序）排列。我们将 Set 转换成数组，直接使用 JavaScript 原生的 .sort() 方法即可得到矩阵的第一行（表头）。

填充数据，生成矩阵：
把排序好的表头作为矩阵的第 0 行。然后遍历我们拍平后的每一个对象：对照着表头，如果对象里有这个键，就填入对应的值；如果没有，就填入空字符串 ""。

type JSONValue = null | boolean | number | string | JSONValue[] | { [key: string]: JSONValue };
function jsonToMatrix(arr: JSONValue[]): (null | boolean | number | string)[][] {
// 存放拍平后的每一个对象
const flattenedArr: Record<string, null | boolean | number | string>[] = [];
const keySet = new Set<string>();
// 递归辅助函数
function flatten(val: JSONValue, path: string, result: Record<string, null | boolean | number | string>) {
if (val !== null && typeof val === 'object') {
const keys = Object.keys(val);
for (const key of keys) {
// 如果当前已经有路径了，就用 '.' 拼接；如果是第一层，直接用 key
const newPath = path ? `${path}.${key}` : key;
flatten((val as any)[key], newPath, result);
}
} else {
// 【修复报错的位置】使用 as 断言，向 TS 保证这里绝对是基本类型或 null
result[path] = val as null | boolean | number | string;
}
}
// 1. 遍历并拍平根数组中的每一个元素
for (const item of arr) {
const flat: Record<string, null | boolean | number | string> = {};
flatten(item, "", flat);
flattenedArr.push(flat);
// 2. 将当前对象的所有路径加入 Set 中
for (const key of Object.keys(flat)) {
keySet.add(key);
}
}
// 3. 对所有列名进行字典序排序
const sortedKeys = Array.from(keySet).sort();
// 4. 构建最终的矩阵，第一行是排好序的表头
const matrix: (null | boolean | number | string)[][] = [sortedKeys];
// 遍历拍平后的对象数组，按表头的顺序填充每一行
for (const flat of flattenedArr) {
const row: (null | boolean | number | string)[] = [];
for (const key of sortedKeys) {
// 如果该对象包含这个键，填入值；否则填入空字符串
if (flat.hasOwnProperty(key)) {
row.push(flat[key]);
} else {
row.push("");
}
}
matrix.push(row);
}
return matrix;
}

复制代码

Myron2017

2650. Design Cancellable Function
Hard
Hint
Sometimes you have a long running task, and you may wish to cancel it before it completes. To help with this goal, write a function cancellable that accepts a generator object and returns an array of two values: a cancel function and a promise.

You may assume the generator function will only yield promises. It is your function's responsibility to pass the values resolved by the promise back to the generator. If the promise rejects, your function should throw that error back to the generator.

If the cancel callback is called before the generator is done, your function should throw an error back to the generator. That error should be the string "Cancelled" (Not an Error object). If the error was caught, the returned promise should resolve with the next value that was yielded or returned. Otherwise, the promise should reject with the thrown error. No more code should be executed.

When the generator is done, the promise your function returned should resolve the value the generator returned. If, however, the generator throws an error, the returned promise should reject with the error.

An example of how your code would be used:

function* tasks() {
  const val = yield new Promise(resolve => resolve(2 + 2));
  yield new Promise(resolve => setTimeout(resolve, 100));
  return val + 1; // calculation shouldn't be done.
}
const [cancel, promise] = cancellable(tasks());
setTimeout(cancel, 50);
promise.catch(console.log); // logs "Cancelled" at t=50ms
If instead cancel() was not called or was called after t=100ms, the promise would have resolved 5.

Example 1:

Input:
generatorFunction = function*() {
  return 42;
}
cancelledAt = 100
Output: {"resolved": 42}
Explanation:
const generator = generatorFunction();
const [cancel, promise] = cancellable(generator);
setTimeout(cancel, 100);
promise.then(console.log); // resolves 42 at t=0ms

The generator immediately yields 42 and finishes. Because of that, the returned promise immediately resolves 42. Note that cancelling a finished generator does nothing.
Example 2:

Input:
generatorFunction = function*() {
  const msg = yield new Promise(res => res("Hello"));
  throw `Error: ${msg}`;
}
cancelledAt = null
Output: {"rejected": "Error: Hello"}
Explanation:
A promise is yielded. The function handles this by waiting for it to resolve and then passes the resolved value back to the generator. Then an error is thrown which has the effect of causing the promise to reject with the same thrown error.
Example 3:

Input:
generatorFunction = function*() {
  yield new Promise(res => setTimeout(res, 200));
  return "Success";
}
cancelledAt = 100
Output: {"rejected": "Cancelled"}
Explanation:
While the function is waiting for the yielded promise to resolve, cancel() is called. This causes an error message to be sent back to the generator. Since this error is uncaught, the returned promise rejected with this error.
Example 4:

Input:
generatorFunction = function*() {
  let result = 0;
  yield new Promise(res => setTimeout(res, 100));
  result += yield new Promise(res => res(1));
  yield new Promise(res => setTimeout(res, 100));
  result += yield new Promise(res => res(1));
  return result;
}
cancelledAt = null
Output: {"resolved": 2}
Explanation:
4 promises are yielded. Two of those promises have their values added to the result. After 200ms, the generator finishes with a value of 2, and that value is resolved by the returned promise.
Example 5:

Input:
generatorFunction = function*() {
  let result = 0;
  try {
yield new Promise(res => setTimeout(res, 100));
result += yield new Promise(res => res(1));
yield new Promise(res => setTimeout(res, 100));
result += yield new Promise(res => res(1));
  } catch(e) {
return result;
  }
  return result;
}
cancelledAt = 150
Output: {"resolved": 1}
Explanation:
The first two yielded promises resolve and cause the result to increment. However, at t=150ms, the generator is cancelled. The error sent to the generator is caught and the result is returned and finally resolved by the returned promise.
Example 6:

Input:
generatorFunction = function*() {
  try {
yield new Promise((resolve, reject) => reject("Promise Rejected"));
  } catch(e) {
let a = yield new Promise(resolve => resolve(2));
let b = yield new Promise(resolve => resolve(2));
return a + b;
  };
}
cancelledAt = null
Output: {"resolved": 4}
Explanation:
The first yielded promise immediately rejects. This error is caught. Because the generator hasn't been cancelled, execution continues as usual. It ends up resolving 2 + 2 = 4.

Constraints:

cancelledAt == null or 0 <= cancelledAt <= 1000
generatorFunction returns a generator object

这道题的本质是要求你手动实现一个带有“取消（Cancel）”功能的 async/await 引擎。

在 JavaScript 的底层，async/await 其实就是基于 Generator（生成器）和 Promise 封装出来的语法糖。这道题让我们剥开这层语法糖，用纯 Generator 来接收 Promise，并在它执行完毕前提供一个强行中断的方法。

核心运作机制：我们该如何驱动 Generator？
Generator 函数（带有 function*）在执行到 yield 时会暂停，并交出控制权。我们需要在外部做以下几件事来“驱动”它：

拿走 Promise：拿到 yield 吐出来的 Promise。

等待结果：在外部用 .then() 或 .catch() 等待这个 Promise 出结果。

送回结果：

如果 Promise 成功，我们就调用 generator.next(成功的值)，把值塞回给 Generator，让它继续往下走。

如果 Promise 失败，我们就调用 generator.throw(失败的错误)，在 Generator 内部引发一个报错。

代码详细拆解
下面我们一段段来剖析代码是如何实现这些目标的：

1. 骨架与取消函数 (cancelFn)
TypeScript
let cancelFn: () => void = () => {};

const promise = new Promise<T>((resolve, reject) => {
let isDone = false; // 状态锁：防止取消后再执行回调

cancelFn = () => {
      if (isDone) return; // 如果已经执行完或者已经取消过，直接无视
      isDone = true;
      try {
         // 强行向 Generator 内部抛出一个 "Cancelled" 错误
         const res = generator.throw("Cancelled");
         // 如果 Generator 内部有 try...catch 捕获了这个 "Cancelled"，
         // 并且在 catch 里 return 了一个新值，我们要把这个新值 resolve 掉。
         resolve(res.value as T | PromiseLike<T>);
      } catch (err) {
         // 如果 Generator 内部没有接住这个报错，错误就会溢出到这里，
         // 此时我们要让最外层的 Promise reject 掉。
         reject(err);
      }
};
// ... 驱动引擎的代码
});
难点解析：当调用 generator.throw("Cancelled") 时，就相当于在 Generator 内部当前的 yield 位置突然写了一句 throw "Cancelled"。这也是题目 Example 5 中能用 try/catch 拦住取消操作的原因。

2. 处理 Generator 的返回值 (handleResult)
每次调用 .next() 或 .throw() 后，Generator 都会返回一个对象 { value: ..., done: boolean }。

TypeScript
function handleResult(res: IteratorResult<Promise<any>, T>) {
if (res.done) {
      // 如果 Generator 已经走到了最后的 return，直接 resolve 最终结果
      isDone = true;
      resolve(res.value);
} else {
      // 如果 done 为 false，说明 yield 出来了一个 Promise，我们需要等它
      Promise.resolve(res.value).then(
         val => {
            if (isDone) return; // 如果在等待期间用户点击了取消，立刻停手
            step(val);       // 成功了，把结果送回 Generator
         },
         err => {
            if (isDone) return;
            stepError(err);    // 失败了，把错误抛回 Generator
         }
      );
}
}
为什么用 Promise.resolve(res.value)？因为为了安全起见，哪怕 yield 出来的不是一个真正的 Promise（比如直接 yield 5），用 Promise.resolve() 包一层也能把它当成 Promise 一致处理。

3. 驱动引擎 (step 和 stepError)
这两个辅助函数的作用非常纯粹：负责向 Generator 里面“推”数据。

TypeScript
function step(val?: any) {
if (isDone) return;
try {
      // 把成功的 Promise 值推进去，让 Generator 继续走，并拿到下一个结果
      const res = generator.next(val);
      handleResult(res);
} catch (err) {
      // 如果在推入数据的过程中 Generator 内部代码报错了，终止一切
      isDone = true;
      reject(err);
}
}

function stepError(err: any) {
if (isDone) return;
try {
      // 把失败的 Promise 错误抛进去
      const res = generator.throw(err);
      handleResult(res);
} catch (e) {
      isDone = true;
      reject(e);
}
}
最后，在 Promise 构造函数的末尾调用 step()，踢出第一脚，整个引擎就会自动循环跑起来了，直到 res.done 变为 true 或者触发 cancelFn 为止。

function cancellable<T>(generator: Generator<Promise<any>, T, unknown>): [() => void, Promise<T>] {
let cancelFn: () => void = () => {};
const promise = new Promise<T>((resolve, reject) => {
let isDone = false;
cancelFn = () => {
// If already done or cancelled, do nothing
if (isDone) return;
isDone = true;
try {
// Throw "Cancelled" back into the generator
const res = generator.throw("Cancelled");
// If it was caught, resolve with the next value yielded or returned.
// Note: If res.value is a Promise, passing it to `resolve` will make
// the main Promise wait for it and adopt its final state.
resolve(res.value as T | PromiseLike<T>);
} catch (err) {
// If the generator didn't catch the error (or threw a new one), reject the promise
reject(err);
}
};
function step(val?: any) {
if (isDone) return;
try {
const res = generator.next(val);
handleResult(res);
} catch (err) {
isDone = true;
reject(err);
}
}
function stepError(err: any) {
if (isDone) return;
try {
const res = generator.throw(err);
handleResult(res);
} catch (e) {
isDone = true;
reject(e);
}
}
function handleResult(res: IteratorResult<Promise<any>, T>) {
if (res.done) {
isDone = true;
resolve(res.value);
} else {
// Wait for the yielded promise to settle
Promise.resolve(res.value).then(
val => {
// If cancelFn was called during the wait, ignore the result
if (isDone) return;
step(val);
},
err => {
if (isDone) return;
stepError(err);
}
);
}
}
// Kick off the generator execution
step();
});
return [cancelFn, promise];
}
/**
* function* tasks() {
* const val = yield new Promise(resolve => resolve(2 + 2));
* yield new Promise(resolve => setTimeout(resolve, 100));
* return val + 1;
* }
* const [cancel, promise] = cancellable(tasks());
* setTimeout(cancel, 50);
* promise.catch(console.log); // logs "Cancelled" at t=50ms
*/

复制代码

Myron2017

2649. Nested Array Generator
Medium
Hint
Given a multi-dimensional array of integers, return a generator object which yields integers in the same order as inorder traversal.

A multi-dimensional array is a recursive data structure that contains both integers and other multi-dimensional arrays.

inorder traversal iterates over each array from left to right, yielding any integers it encounters or applying inorder traversal to any arrays it encounters.

Example 1:

Input: arr = [[[6]],[1,3],[]]
Output: [6,1,3]
Explanation:
const generator = inorderTraversal(arr);
generator.next().value; // 6
generator.next().value; // 1
generator.next().value; // 3
generator.next().done; // true
Example 2:

Input: arr = []
Output: []
Explanation: There are no integers so the generator doesn't yield anything.

Constraints:

0 <= arr.flat().length <= 105
0 <= arr.flat()[i] <= 105
maxNestingDepth <= 105

这道题要求我们将一个多维嵌套数组“拍平”，但特殊之处在于必须使用生成器 (Generator)。这意味着我们不能直接使用 arr.flat(Infinity) 一口气把所有数字都提取出来堆在内存里，而是需要“按需产出”——外部调用一次 .next()，引擎才去数组里找下一个数字并返回。这段代码中最核心的魔法在于 yield* 关键字。核心代码拆解TypeScriptfor (const item of arr) {
if (Array.isArray(item)) {
      // 遇到数组：委托给子生成器
      yield* inorderTraversal(item);
} else {
      // 遇到数字：直接产出
      yield item;
}
}
基本遍历：我们用 for...of 循环从左到右遍历当前的数组 arr。处理数字 (yield)：如果当前元素是个纯数字，直接用 yield item 将它扔到外部。此时函数会暂停执行，保留当前状态，直到外部下一次调用 .next()。处理嵌套数组 (yield*)：如果当前元素是个数组，我们就需要递归调用 inorderTraversal(item)。如果你只写 yield inorderTraversal(item)，外部收到的将是一个未执行的生成器对象，这显然不对。加上星号写成 yield*，它的意思是委托产出。它会自动遍历这个子生成器里的所有元素，把里面吐出来的数字，原封不动地直接“转交”给最外层。这就好比你作为一个中间商（父生成器），把供应商（子生成器）的货一件件直接转发给客户。为什么这是最佳实践？惰性求值 (Lazy Evaluation)：这种写法不会在初始化时就执行完毕。如果你有一个包含 10 万个数字的嵌套数组，但外部只调用了 3 次 .next()，这段代码只会精确地运行到找到前 3 个数字的地方就彻底停下，绝不多做无效运算。极低的空间占用：它不需要新建一个巨大的数组来存放拍平后的结果。它在内存中占用的额外空间仅仅是递归调用栈的深度（时间复杂度为 $O(N)$，空间复杂度为 $O(D)$，其中 $D$ 是最大嵌套层数）。

type MultidimensionalArray = (MultidimensionalArray | number)[]
function* inorderTraversal(arr: MultidimensionalArray): Generator<number, void, unknown> {
for (const item of arr) {
if (Array.isArray(item)) {
// If the item is an array, recursively delegate yielding to it
yield* inorderTraversal(item);
} else {
// If the item is a number, yield it directly
yield item;
}
}
};
/**
* const gen = inorderTraversal([1, [2, 3]]);
* gen.next().value; // 1
* gen.next().value; // 2
* gen.next().value; // 3
*/

复制代码

Myron2017

2705. Compact Object
Medium
Given an object or array obj, return a compact object.

A compact object is the same as the original object, except with keys containing falsy values removed. This operation applies to the object and any nested objects. Arrays are considered objects where the indices are keys. A value is considered falsy when Boolean(value) returns false.

You may assume the obj is the output of JSON.parse. In other words, it is valid JSON.

Example 1:

Input: obj = [null, 0, false, 1]
Output: [1]
Explanation: All falsy values have been removed from the array.
Example 2:

Input: obj = {"a": null, "b": [false, 1]}
Output: {"b": [1]}
Explanation: obj["a"] and obj["b"][0] had falsy values and were removed.
Example 3:

Input: obj = [null, 0, 5, [0], [false, 16]]
Output: [5, [], [16]]
Explanation: obj[0], obj[1], obj[3][0], and obj[4][0] were falsy and removed.

Constraints:

obj is a valid JSON object
2 <= JSON.stringify(obj).length <= 106

题目理解

题目要求实现一个 compactObject 函数：递归地遍历一个对象（或数组），把所有值为 falsy（即 Boolean(value) === false，比如 null、0、false、""）的键删除掉。

关键点：

数组也是对象：数组的下标就相当于键，所以数组里的假值元素也要被移除（移除后数组会重新紧凑排列，因为用的是 filter）。
递归：不仅要处理最外层，内部嵌套的对象/数组也要做同样的清理。
因为输入保证是合法 JSON（JSON.parse 的结果），所以不用担心 undefined、NaN、循环引用等特殊情况。

思路：

如果当前值是数组：先用 filter(Boolean) 去掉本层的假值元素，再对剩下元素中「本身还是对象/数组」的元素递归调用 compactObject。
如果当前值是普通对象：遍历所有键，只保留值为真值的键；如果这个真值本身是对象或数组，就递归清理它，再存入结果对象。
如果是基本类型（数字、字符串、布尔值等），直接原样返回（不会再往下递归）。

type JSONValue = null | boolean | number | string | JSONValue[] | { [key: string]: JSONValue };
type Obj = Record<string, JSONValue> | Array<JSONValue>;
function compactObject(obj: Obj): Obj {
const isObjectLike = (v: JSONValue): v is Obj =>
typeof v === 'object' && v !== null;
if (Array.isArray(obj)) {
// 1. 先过滤掉本层的假值元素
// 2. 对剩下的元素中仍是对象/数组的部分递归清理
return obj
.filter(Boolean)
.map(item => (isObjectLike(item) ? compactObject(item) : item));
}
const result: Record<string, JSONValue> = {};
for (const key in obj) {
const value = obj[key];
if (Boolean(value)) {
result[key] = isObjectLike(value) ? compactObject(value) : value;
}
}
return result;
}

复制代码

Myron2017

2721. Execute Asynchronous Functions in Parallel
Medium
Given an array of asynchronous functions functions, return a new promise promise. Each function in the array accepts no arguments and returns a promise. All the promises should be executed in parallel.

promise resolves:

When all the promises returned from functions were resolved successfully in parallel. The resolved value of promise should be an array of all the resolved values of promises in the same order as they were in the functions. The promise should resolve when all the asynchronous functions in the array have completed execution in parallel.
promise rejects:

When any of the promises returned from functions were rejected. promise should also reject with the reason of the first rejection.
Please solve it without using the built-in Promise.all function.

Example 1:

Input: functions = [
() => new Promise(resolve => setTimeout(() => resolve(5), 200))
]
Output: {"t": 200, "resolved": [5]}
Explanation:
promiseAll(functions).then(console.log); // [5]

The single function was resolved at 200ms with a value of 5.
Example 2:

Input: functions = [
() => new Promise(resolve => setTimeout(() => resolve(1), 200)),
() => new Promise((resolve, reject) => setTimeout(() => reject("Error"), 100))
]
Output: {"t": 100, "rejected": "Error"}
Explanation: Since one of the promises rejected, the returned promise also rejected with the same error at the same time.
Example 3:

Input: functions = [
() => new Promise(resolve => setTimeout(() => resolve(4), 50)),
() => new Promise(resolve => setTimeout(() => resolve(10), 150)),
() => new Promise(resolve => setTimeout(() => resolve(16), 100))
]
Output: {"t": 150, "resolved": [4, 10, 16]}
Explanation: All the promises resolved with a value. The returned promise resolved when the last promise resolved.

Constraints:

functions is an array of functions that returns promises
1 <= functions.length <= 10

题目理解

要求手写一个 promiseAll，功能等价于内置的 Promise.all，但不能直接使用 Promise.all。

输入是一个函数数组，每个函数不接收参数，调用后返回一个 Promise。要求：

并行执行：所有函数要同时被调用，不能等前一个完成再调用下一个。
全部成功时：返回的 promise 变为 resolved，值是一个数组，且顺序必须和 functions 里的顺序一致（而不是按完成先后排序）。比如例 3 中，完成顺序是 50ms、100ms、150ms，但结果仍是 [4, 10, 16]。
任意一个失败时：返回的 promise 立即 reject，原因是第一个失败的那个 promise 的 reason。比如例 2，100ms 时就已经 reject 了，不会等 200ms 那个。
思路
返回一个 new Promise((resolve, reject) => { ... })，把控制权拿在自己手里。
用 forEach 遍历所有函数并立即调用，这样它们就是并行启动的。
用 results[index] = value 按下标存结果，而不是 push，这样才能保证顺序和原数组一致。
用一个计数器 resolvedCount 记录已经成功的数量。之所以不用 results.length 判断，是因为按下标赋值时，数组可能先出现「空位」，长度会提前变大，不能反映真实完成数量。
当计数器等于 functions.length 时，resolve(results)。
任何一个 promise 失败，就直接把 reject 作为它的失败回调。一个 promise 只会被 settle 一次，所以后续的 reject 或 resolve 调用都会被忽略，天然满足「以第一个失败的原因 reject」。

type Fn<T> = () => Promise<T>
function promiseAll<T>(functions: Fn<T>[]): Promise<T[]> {
return new Promise((resolve, reject) => {
const total = functions.length;
// 空数组时没有任何 promise 会触发 resolve，需要直接返回
if (total === 0) {
resolve([]);
return;
}
const results: T[] = new Array(total);
let resolvedCount = 0;
functions.forEach((fn, index) => {
// 所有函数在这里被同步地依次调用，因此是并行执行的
fn().then(
(value) => {
results[index] = value; // 按下标存放，保证顺序
resolvedCount++;
if (resolvedCount === total) {
resolve(results);
}
},
reject // 任意一个失败，直接 reject
);
});
});
}

复制代码

Myron2017

2722. Join Two Arrays by ID
Medium
Given two arrays arr1 and arr2, return a new array joinedArray. All the objects in each of the two inputs arrays will contain an id field that has an integer value.

joinedArray is an array formed by merging arr1 and arr2 based on their id key. The length of joinedArray should be the length of unique values of id. The returned array should be sorted in ascending order based on the id key.

If a given id exists in one array but not the other, the single object with that id should be included in the result array without modification.

If two objects share an id, their properties should be merged into a single object:

If a key only exists in one object, that single key-value pair should be included in the object.
If a key is included in both objects, the value in the object from arr2 should override the value from arr1.

Example 1:

Input:
arr1 = [
{"id": 1, "x": 1},
{"id": 2, "x": 9}
],
arr2 = [
{"id": 3, "x": 5}
]
Output:
[
{"id": 1, "x": 1},
{"id": 2, "x": 9},
{"id": 3, "x": 5}
]
Explanation: There are no duplicate ids so arr1 is simply concatenated with arr2.
Example 2:

Input:
arr1 = [
{"id": 1, "x": 2, "y": 3},
{"id": 2, "x": 3, "y": 6}
],
arr2 = [
{"id": 2, "x": 10, "y": 20},
{"id": 3, "x": 0, "y": 0}
]
Output:
[
{"id": 1, "x": 2, "y": 3},
{"id": 2, "x": 10, "y": 20},
{"id": 3, "x": 0, "y": 0}
]
Explanation: The two objects with id=1 and id=3 are included in the result array without modifiction. The two objects with id=2 are merged together. The keys from arr2 override the values in arr1.
Example 3:

Input:
arr1 = [
{"id": 1, "b": {"b": 94},"v": [4, 3], "y": 48}
]
arr2 = [
{"id": 1, "b": {"c": 84}, "v": [1, 3]}
]
Output: [
{"id": 1, "b": {"c": 84}, "v": [1, 3], "y": 48}
]
Explanation: The two objects with id=1 are merged together. For the keys "b" and "v" the values from arr2 are used. Since the key "y" only exists in arr1, that value is taken form arr1.

Constraints:

arr1 and arr2 are valid JSON arrays
Each object in arr1 and arr2 has a unique integer id key
2 <= JSON.stringify(arr1).length <= 106
2 <= JSON.stringify(arr2).length <= 106

题目理解

给定两个数组 arr1 和 arr2，每个元素都是带有整数 id 字段的对象。要把它们按 id 合并成一个新数组 joinedArray：

长度等于两个数组中不同 id 的个数。
排序：结果按 id 升序排列。
只出现在一个数组里的 id：对应的对象原样保留。
两个数组都有的 id：把两个对象合并成一个：
只存在于其中一个对象里的键，直接保留。
两个对象都有的键，用 arr2 的值覆盖 arr1 的值。

要特别注意例 3：合并是浅合并。arr1 的 b 是 {"b": 94}，arr2 的 b 是 {"c": 84}，结果中 b 直接变成 {"c": 84}，而不是把两者递归合并成 {"b": 94, "c": 84}。v 数组同理，整体被 arr2 的替换。
思路
用一个 Map<number, ArrayType> 以 id 为键存放对象，这样按 id 查找是 O(1)。
先遍历 arr1，把所有对象放进 Map。
再遍历 arr2：
如果 Map 里已有相同 id，用展开运算符 { ...existing, ...item } 合并。展开运算符是浅拷贝，后面的属性覆盖前面的，正好满足「arr2 覆盖 arr1」，并且不会修改原对象。
如果没有，直接放入 Map。
最后取出 Map 的所有值，按 id 升序排序后返回。

这里不能用双指针归并，因为题目并没有保证两个输入数组本身是按 id 有序的，所以最后统一排序更稳妥。

type JSONValue = null | boolean | number | string | JSONValue[] | { [key: string]: JSONValue };
type ArrayType = { "id": number } & Record<string, JSONValue>;
function join(arr1: ArrayType[], arr2: ArrayType[]): ArrayType[] {
const map = new Map<number, ArrayType>();
// 1. 先放入 arr1 的所有对象
for (const item of arr1) {
map.set(item.id, item);
}
// 2. 再处理 arr2：id 已存在则浅合并（arr2 覆盖 arr1），否则直接加入
for (const item of arr2) {
const existing = map.get(item.id);
map.set(item.id, existing ? { ...existing, ...item } : item);
}
// 3. 按 id 升序排序后返回
return Array.from(map.values()).sort((a, b) => a.id - b.id);
}

复制代码

Myron2017

2757. Generate Circular Array Values
Medium
Given a circular array arr and an integer startIndex, return a generator object gen that yields values from arr.

The first time gen.next() is called on the generator, it should should yield arr[startIndex].

Each subsequent time gen.next() is called, an integer jump will be passed into the function (Ex: gen.next(-3)).

If jump is positive, the index should increase by that value, however if the current index is the last index, it should instead jump to the first index.
If jump is negative, the index should decrease by the magnitude of that value, however if the current index is the first index, it should instead jump to the last index.

Example 1:

Input: arr = [1,2,3,4,5], steps = [1,2,6], startIndex = 0
Output: [1,2,4,5]
Explanation:
const gen = cycleGenerator(arr, startIndex);
gen.next().value;  // 1, index = startIndex = 0
gen.next(1).value; // 2, index = 1, 0 -> 1
gen.next(2).value; // 4, index = 3, 1 -> 2 -> 3
gen.next(6).value; // 5, index = 4, 3 -> 4 -> 0 -> 1 -> 2 -> 3 -> 4
Example 2:

Input: arr = [10,11,12,13,14,15], steps = [1,4,0,-1,-3], startIndex = 1
Output: [11,12,10,10,15,12]
Explanation:
const gen = cycleGenerator(arr, startIndex);
gen.next().value; // 11, index = 1
gen.next(1).value;  // 12, index = 2
gen.next(4).value;  // 10, index = 0
gen.next(0).value;  // 10, index = 0
gen.next(-1).value; // 15, index = 5
gen.next(-3).value; // 12, index = 2
Example 3:

Input: arr = [2,4,6,7,8,10], steps = [-4,5,-3,10], startIndex = 3
Output: [7,10,8,4,10]
Explanation:
const gen = cycleGenerator(arr, startIndex);
gen.next().value // 7,  index = 3
gen.next(-4).value // 10, index = 5
gen.next(5).value  // 8,  index = 4
gen.next(-3).value // 4,  index = 1
gen.next(10).value // 10, index = 5

Constraints:

1 <= arr.length <= 104
1 <= steps.length <= 100
-104 <= steps[i], arr[i] <= 104
0 <= startIndex < arr.length

题目理解

给定一个环形数组 arr 和起始下标 startIndex，要返回一个生成器对象 gen：

第一次调用 gen.next() 时，产出（yield）arr[startIndex]。
之后每次调用 gen.next(jump) 时，会传入一个整数 jump，当前下标要移动 jump 步，然后产出新位置的值：
jump 为正：下标向后移动；走到最后一个元素后，下一步回到第一个元素。
jump 为负：下标向前移动；走到第一个元素后，再往前一步会到最后一个元素。
jump 为 0：原地不动，再次产出当前值。

说白了就是在环上移动，本质是对数组长度取模。例如例 1 中，arr 长度为 5，从下标 3 跳 6 步：3 + 6 = 9，9 % 5 = 4，落在下标 4，值为 5。

先复习两个关键知识点

1. 生成器的 next(value) 传参机制

typescript
const jump = yield arr[index];

这行代码做了两件事：

yield arr[index]：把 arr[index] 作为 next() 的返回值产出，然后暂停在这里。
下一次调用 gen.next(x) 时，暂停处的 yield 表达式会求值为 x，于是 jump 就拿到了 x，然后继续往下执行。

注意：第一次调用 gen.next() 传入的参数会被忽略，因为此时生成器还没有执行到任何 yield。这正好符合题意：第一次调用不带参数，只产出起始位置的值。

2. JavaScript 中负数取模

JS 的 % 运算结果符号和被除数一致，例如 -1 % 6 === -1，而不是 5。所以要处理负数下标，需要写成：

typescript
((x % n) + n) % n

先取模得到 (-n, n) 范围内的值，加 n 让它变成正数，再取模一次收敛到 [0, n)。

function* cycleGenerator(arr: number[], startIndex: number): Generator<number, void, number> {
const n = arr.length;
let index = startIndex;
while (true) {
// 产出当前位置的值，并暂停；下一次 next(jump) 传入的值会赋给 jump
const jump = yield arr[index];
// 在环形数组上移动，同时兼容负数和超过数组长度的跳跃
index = (((index + jump) % n) + n) % n;
}
}
/**
* const gen = cycleGenerator([1,2,3,4,5], 0);
* gen.next().value // 1
* gen.next(1).value // 2
* gen.next(2).value // 4
* gen.next(6).value // 5
*/

复制代码

Myron2017

2756. Query Batching
Hard
Batching multiple small queries into a single large query can be a useful optimization. Write a class QueryBatcher that implements this functionality.

The constructor should accept two parameters:

An asynchronous function queryMultiple which accepts an array of string keys input. It will resolve with an array of values that is the same length as the input array. Each index corresponds to the value associated with input[i]. You can assume the promise will never reject.
A throttle time in milliseconds t.
The class has a single method.

async getValue(key). Accepts a single string key and resolves with a single string value. The keys passed to this function should eventually get passed to the queryMultiple function. queryMultiple should never be called consecutively within t milliseconds. The first time getValue is called, queryMultiple should immediately be called with that single key. If after t milliseconds, getValue had been called again, all the passed keys should be passed to queryMultiple and ultimately returned. You can assume every key passed to this method is unique.
The following diagram illustrates how the throttling algorithm works. Each rectangle represents 100ms. The throttle time is 400ms.

Throttle info

Example 1:

Input:
queryMultiple = async function(keys) {
  return keys.map(key => key + '!');
}
t = 100
calls = [
{"key": "a", "time": 10},
{"key": "b", "time": 20},
{"key": "c", "time": 30}
]
Output: [
{"resolved": "a!", "time": 10},
{"resolved": "b!", "time": 110},
{"resolved": "c!", "time": 110}
]
Explanation:
const batcher = new QueryBatcher(queryMultiple, 100);
setTimeout(() => batcher.getValue('a'), 10); // "a!" at t=10ms
setTimeout(() => batcher.getValue('b'), 20); // "b!" at t=110ms
setTimeout(() => batcher.getValue('c'), 30); // "c!" at t=110ms

queryMultiple simply adds an "!" to the key
At t=10ms, getValue('a') is called, queryMultiple(['a']) is immediately called and the result is immediately returned.
At t=20ms, getValue('b') is called but the query is queued
At t=30ms, getValue('c') is called but the query is queued.
At t=110ms, queryMultiple(['a', 'b']) is called and the results are immediately returned.
Example 2:

Input:
queryMultiple = async function(keys) {
  await new Promise(res => setTimeout(res, 100));
  return keys.map(key => key + '!');
}
t = 100
calls = [
{"key": "a", "time": 10},
{"key": "b", "time": 20},
{"key": "c", "time": 30}
]
Output: [
  {"resolved": "a!", "time": 110},
  {"resolved": "b!", "time": 210},
  {"resolved": "c!", "time": 210}
]
Explanation:
This example is the same as example 1 except there is a 100ms delay in queryMultiple. The results are the same except the promises resolve 100ms later.
Example 3:

Input:
queryMultiple = async function(keys) {
  await new Promise(res => setTimeout(res, keys.length * 100));
  return keys.map(key => key + '!');
}
t = 100
calls = [
  {"key": "a", "time": 10},
  {"key": "b", "time": 20},
  {"key": "c", "time": 30},
  {"key": "d", "time": 40},
  {"key": "e", "time": 250}
  {"key": "f", "time": 300}
]
Output: [
  {"resolved":"a!","time":110},
  {"resolved":"e!","time":350},
  {"resolved":"b!","time":410},
  {"resolved":"c!","time":410},
  {"resolved":"d!","time":410},
  {"resolved":"f!","time":450}
]
Explanation:
queryMultiple(['a']) is called at t=10ms, it is resolved at t=110ms
queryMultiple(['b', 'c', 'd']) is called at t=110ms, it is resolved at 410ms
queryMultiple(['e']) is called at t=250ms, it is resolved at 350ms
queryMultiple(['f']) is called at t=350ms, it is resolved at 450ms

Constraints:

0 <= t <= 1000
0 <= calls.length <= 10
1 <= key.length <= 100
All keys are unique

题目理解

要实现一个 QueryBatcher 类，把多次零散的单个查询合并成一次批量查询，同时对批量查询的调用频率做节流：

构造函数接收批量查询函数 queryMultiple 和节流时间 t。
getValue(key) 接收单个 key，返回一个 Promise，最终 resolve 成这个 key 对应的值。
第一次调用 getValue 时，立即用这一个 key 调用 queryMultiple。
之后两次 queryMultiple 调用之间，至少间隔 t 毫秒。在节流期间进来的 key 先排队，等节流结束后，一次性把队列里所有 key 传给 queryMultiple。

几个容易忽略的关键点，都能从例 3 看出来：

节流时间从「调用 queryMultiple 的时刻」开始算，而不是从它 resolve 的时刻算。例 3 中 ['a'] 在 t=10 调用，t=110 才 resolve，但 ['b','c','d'] 在 t=110 就被调用了，与 a 是否完成无关（这里恰好相等，看后面的 e 更明显）。
多个 queryMultiple 可以同时在途。 ['b','c','d'] 在 t=110 调用，要到 t=410 才返回；而 ['e'] 在 t=250 就被调用了，并没有等前一个返回。
节流结束时如果队列为空，就回到「空闲」状态，之后再来的 key 可以立即触发查询（例如 t=250 的 e）。
思路

维护三样东西：

queue：等待查询的项，每项包含 key 和这个 key 对应 Promise 的 resolve 函数。
throttled：布尔值，表示当前是否处于节流期。
flush()：发起一次批量查询的方法。

流程：

getValue(key)：创建一个 Promise，把 {key, resolve} 放入队列；如果当前不在节流期，立刻 flush()。

flush()：

取出队列里的所有项，清空队列。
把 throttled 设为 true，进入节流期。
调用 queryMultiple(所有 key)，结果返回后，按下标依次 resolve 每一项（返回数组的第 i 个值对应第 i 个 key）。
同时启动一个 t 毫秒的定时器：定时器触发时结束节流期，如果队列里有新排队的项，就再次 flush()；如果队列为空，就什么也不做，安静地回到空闲状态。

定时器只在有 flush 发生时才会被创建，队列空了就不会继续设置，所以不会出现永远不退出的定时器。

type QueryMultiple = (keys: string[]) => Promise<string[]>
class QueryBatcher {
private queryMultiple: QueryMultiple;
private t: number;
private queue: { key: string; resolve: (value: string) => void }[] = [];
private throttled = false;
constructor(queryMultiple: QueryMultiple, t: number) {
this.queryMultiple = queryMultiple;
this.t = t;
}
private flush(): void {
// 取出当前队列里的全部请求，并清空队列
const batch = this.queue;
this.queue = [];
// 进入节流期：从"调用 queryMultiple"这一刻开始计时
this.throttled = true;
// 发起批量查询，返回后按下标把结果分发给各自的 Promise
this.queryMultiple(batch.map(item => item.key)).then(values => {
batch.forEach((item, i) => item.resolve(values[i]));
});
// t 毫秒后结束节流期；若期间有新请求排队，则立即发起下一批
setTimeout(() => {
this.throttled = false;
if (this.queue.length > 0) {
this.flush();
}
}, this.t);
}
async getValue(key: string): Promise<string> {
return new Promise<string>(resolve => {
this.queue.push({ key, resolve });
// 不在节流期就立即查询；否则留在队列里等定时器触发
if (!this.throttled) {
this.flush();
}
});
}
};
/**
* async function queryMultiple(keys) {
* return keys.map(key => key + '!');
* }
*
* const batcher = new QueryBatcher(queryMultiple, 100);
* batcher.getValue('a').then(console.log); // resolves "a!" at t=0ms
* batcher.getValue('b').then(console.log); // resolves "b!" at t=100ms
* batcher.getValue('c').then(console.log); // resolves "c!" at t=100ms
*/

复制代码