记录@2023-09-07
Published by powerfulyang on Sep 7, 2023
一些相关问题的总结
微前端对比
二叉树的最小路径和
在这种情境下，你可能是在寻找一个从根节点到叶子节点的路径，该路径上的所有节点值的和为最小。
我们可以使用递归的方法来解决这个问题。以下是一个示例：
1class TreeNode {
2 constructor(value) {
3 this.value = value;
4 this.left = null;
5 this.right = null;
6 }
7}
8
9function minPathSum(root) {
10 if (!root) return 0;
11
12 if (!root.left && !root.right) {
13 // 当前节点是叶子节点
14 return root.value;
15 }
16
17 if (!root.left) {
18 // 只有右子树
19 return root.value + minPathSum(root.right);
20 }
21
22 if (!root.right) {
23 // 只有左子树
24 return root.value + minPathSum(root.left);
25 }
26
27 // 左右子树都存在
28 return root.value + Math.min(minPathSum(root.left), minPathSum(root.right));
29}
30
31// 使用示例
32const root = new TreeNode(10);
33root.left = new TreeNode(5);
34root.right = new TreeNode(15);
35root.left.left = new TreeNode(2);
36root.left.right = new TreeNode(6);
37root.right.left = new TreeNode(13);
38root.right.right = new TreeNode(20);
39
40console.log(minPathSum(root)); // 输出应为 10 + 5 + 2 = 17在这个示例中，我们从根节点开始，递归地计算左右子树的最小路径和，并将当前节点的值加到较小的那个路径和上，直到到达叶子节点。最终的结果是从根节点到叶子节点的最小路径和。
数组形式的二叉树
如果二叉树是以数组形式给出的，通常根据以下关系来表示父子关系：
-
对于数组中的每个元素，位置为
i的元素：- 它的左孩子在位置
2i + 1 - 它的右孩子在位置
2i + 2
- 它的左孩子在位置
基于上述关系，我们可以递归地求解二叉树中的最小路径和。以下是一个示例，展示了如何计算给定数组形式的二叉树的最小路径和：
1function minPathSum(tree, idx = 0) {
2 // 如果索引超过了数组的大小，返回一个很大的数字
3 if (idx >= tree.length || tree[idx] === null) return Number.MAX_VALUE;
4
5 // 当前节点是叶子节点
6 if (2 * idx + 1 >= tree.length || (tree[2 * idx + 1] === null && tree[2 * idx + 2] === null)) {
7 return tree[idx];
8 }
9
10 // 计算左右子树的最小路径和
11 let leftSum = minPathSum(tree, 2 * idx + 1);
12 let rightSum = minPathSum(tree, 2 * idx + 2);
13
14 return tree[idx] + Math.min(leftSum, rightSum);
15}
16
17// 使用示例
18const treeArray = [10, 5, 15, 2, 6, 13, 20];
19console.log(minPathSum(treeArray)); // 输出应为 10 + 5 + 2 = 17这个示例使用了递归方法来求解。从根节点开始，递归地计算左右子树的最小路径和，并将当前节点的值加到较小的那个路径和上，直到到达叶子节点。
手写一个 Promise
Promise 是 JavaScript 中的一个构造函数，用于异步编程。它有三种状态：pending（待定）、fulfilled（已实现）和 rejected（已拒绝）。以下是一个简化版的 Promise 的实现：
1class MyPromise {
2 constructor(executor) {
3 this.state = 'pending'; // 'fulfilled', 'rejected'
4 this.value = undefined;
5 this.reason = undefined;
6 this.onResolvedCallbacks = [];
7 this.onRejectedCallbacks = [];
8
9 let resolve = (value) => {
10 if (this.state === 'pending') {
11 this.state = 'fulfilled';
12 this.value = value;
13 this.onResolvedCallbacks.forEach(fn => fn());
14 }
15 };
16
17 let reject = (reason) => {
18 if (this.state === 'pending') {
19 this.state = 'rejected';
20 this.reason = reason;
21 this.onRejectedCallbacks.forEach(fn => fn());
22 }
23 };
24
25 try {
26 executor(resolve, reject);
27 } catch (err) {
28 reject(err);
29 }
30 }
31
32 then(onFulfilled, onRejected) {
33 if (this.state === 'fulfilled') {
34 onFulfilled(this.value);
35 }
36 if (this.state === 'rejected') {
37 onRejected(this.reason);
38 }
39 if (this.state === 'pending') {
40 this.onResolvedCallbacks.push(() => {
41 onFulfilled(this.value);
42 });
43 this.onRejectedCallbacks.push(() => {
44 onRejected(this.reason);
45 });
46 }
47 }
48}
49
50// 使用示例
51new MyPromise((resolve, reject) => {
52 setTimeout(() => {
53 resolve('Resolved after 1 second');
54 }, 1000);
55}).then(value => {
56 console.log(value);
57}, reason => {
58 console.error(reason);
59});这只是一个基础的实现，真实的 Promise 更复杂，还包括链式调用、catch、finally、all、race 等方法。但这个简化版可以帮助你理解其基础工作原理。
手写一个 flat
flat 是一个数组的方法，用于将多层嵌套的数组扁平化。以下是一个简化版的 flat 函数实现，考虑了递归和深度：
1function flat(array, depth = 1) {
2 if (depth < 1 || !Array.isArray(array)) return array;
3
4 let result = [];
5
6 for (let item of array) {
7 if (Array.isArray(item) && depth > 0) {
8 result = result.concat(flat(item, depth - 1));
9 } else {
10 result.push(item);
11 }
12 }
13
14 return result;
15}
16
17// 使用示例
18console.log(flat([1, [2, 3, [4, 5]], 6], 1)); // [1, 2, 3, [4, 5], 6]
19console.log(flat([1, [2, 3, [4, 5]], 6], 2)); // [1, 2, 3, 4, 5, 6]这个 flat 函数可以接受一个 depth 参数，表示扁平化的深度。如果没有提供这个参数，它默认为1，即只会扁平化一层。