场景算法题

二叉树的 Z 型遍历

function zigzagLevelOrder(root) {
if (!root) return [];

const result = [];
const deque = [root];
let leftToRight = true;

while (deque.length > 0) {
    const levelSize = deque.length;
    const level = [];

    for (let i = 0; i < levelSize; i++) {
        const node = deque.shift();

        if (leftToRight) {
            level.push(node.val);
        } else {
            level.unshift(node.val);
        }

        if (node.left) {
            deque.push(node.left);
        }
        if (node.right) {
            deque.push(node.right);
        }
    }

    result.push(level);
    leftToRight = !leftToRight; // 切换方向
}

return result;

}

// 示例用法
function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}

const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(7);

console.log(zigzagLevelOrder(root));
// 输出: [[1], [3, 2], [4, 5, 6, 7]]

防抖（Debounce）

防抖函数的原理是：当持续触发事件时，防抖会在规定的时间内不执行事件，只有当最后一次事件触发后，等待一定时间才会执行回调函数。如果在这个时间内事件又被触发，则重新开始等待。

function debounce(func, wait) {
    let timeout;

    return function (...args) {
        const context = this;

        clearTimeout(timeout);
        timeout = setTimeout(() => {
            func.apply(context, args);
        }, wait);
    };
}

// 示例用法
const onResize = debounce(() => {
    console.log('Window resized');
}, 300);

window.addEventListener('resize', onResize);

节流（Throttle）

节流函数的原理是：当持续触发事件时，保证在规定的时间间隔内只执行一次回调函数。

javascript复制代码function throttle(func, limit) {
    let lastFunc;
    let lastRan;

    return function (...args) {
        const context = this;

        if (!lastRan) {
            func.apply(context, args);
            lastRan = Date.now();
        } else {
            clearTimeout(lastFunc);
            lastFunc = setTimeout(() => {
                if (Date.now() - lastRan >= limit) {
                    func.apply(context, args);
                    lastRan = Date.now();
                }
            }, limit - (Date.now() - lastRan));
        }
    };
}

// 示例用法
const onScroll = throttle(() => {
    console.log('Scrolled');
}, 1000);

window.addEventListener('scroll', onScroll);

合并两个有序数组

function mergeSortedArrays(arr1, arr2) {
let mergedArray = [];
let i = 0, j = 0;

// 当两个数组都没有遍历完时
while (i < arr1.length && j < arr2.length) {
    if (arr1[i] < arr2[j]) {
        mergedArray.push(arr1[i]);
        i++;
    } else {
        mergedArray.push(arr2[j]);
        j++;
    }
}

// 将剩余的元素加入到结果数组中
while (i < arr1.length) {
    mergedArray.push(arr1[i]);
    i++;
}

while (j < arr2.length) {
    mergedArray.push(arr2[j]);
    j++;
}

return mergedArray;

}

// 示例用法
const array1 = [1, 3, 5, 7];
const array2 = [2, 4, 6, 8];

const mergedArray = mergeSortedArrays(array1, array2);
console.log(mergedArray); // 输出 [1, 2, 3, 4, 5, 6, 7, 8]

写一个类似 `new` 的函数

function myNew(constructor, …args) {
// 1. 创建一个新对象，并将它的 proto 链接到 constructor.prototype
const obj = Object.create(constructor.prototype);

// 2. 执行构造函数，并将 this 绑定到新对象上
const result = constructor.apply(obj, args);

// 3. 如果构造函数返回的是对象，则返回该对象；否则，返回新对象
return result !== null && (typeof result === "object" || typeof result === "function") ? result : obj;

}

// 示例用法
function Person(name, age) {
this.name = name;
this.age = age;
}

Person.prototype.sayHello = function() {
console.log(Hello, my name is ${this.name} and I'm ${this.age} years old.);
};

const person = myNew(Person, ‘Alice’, 30);
person.sayHello(); // 输出: Hello, my name is Alice and I’m 30 years old.

使用递归实现深拷贝

function deepClone(obj) {
// 检查是否是原始值，如果是，则直接返回
if (obj === null || typeof obj !== ‘object’) {
return obj;
}

// 检查是否是数组，创建对应的新对象
if (Array.isArray(obj)) {
    const copy = [];
    for (let i = 0; i < obj.length; i++) {
        copy[i] = deepClone(obj[i]);
    }
    return copy;
}

// 如果是对象，创建一个新对象并递归复制属性
const copy = {};
for (const key in obj) {
    if (obj.hasOwnProperty(key)) {
        copy[key] = deepClone(obj[key]);
    }
}
return copy;

}

// 示例用法
const original = {
name: “Alice”,
age: 25,
skills: [“JavaScript”, “React”],
address: {
city: “New York”,
zip: “10001”
}
};

const copied = deepClone(original);
copied.address.city = “Los Angeles”;

console.log(original.address.city); // 输出: “New York”
console.log(copied.address.city); // 输出: “Los Angeles”

二叉树的最大深度

function maxDepth(root) {
if (root === null) {
return 0;
} else {
const leftDepth = maxDepth(root.left);
const rightDepth = maxDepth(root.right);
return Math.max(leftDepth, rightDepth) + 1;
}
}

// 示例用法
function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}

const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

console.log(maxDepth(root)); // 输出: 3

二叉树的最大广度

function maxWidth(root) {
if (root === null) return 0;

const queue = [root];
let maxWidth = 0;

while (queue.length > 0) {
    const levelSize = queue.length; // 当前层的节点数
    maxWidth = Math.max(maxWidth, levelSize);

    for (let i = 0; i < levelSize; i++) {
        const node = queue.shift();

        if (node.left !== null) queue.push(node.left);
        if (node.right !== null) queue.push(node.right);
    }
}

return maxWidth;

}

// 示例用法
function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}

const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.right = new TreeNode(6);

console.log(maxWidth(root)); // 输出: 3

自定义 `map` 方法的实现

Array.prototype.myMap = function(callback, thisArg) {
// 检查调用者是否为数组
if (this == null) {
throw new TypeError(‘Array.prototype.myMap called on null or undefined’);
}

// 强制将调用对象转换为对象类型（通常是数组）
const O = Object(this);
const len = O.length >>> 0;

// 如果传入了thisArg，则将callback的this指向thisArg，否则指向undefined
const result = new Array(len);

for (let i = 0; i < len; i++) {
    if (i in O) { // 检查当前索引是否存在于数组中
        result[i] = callback.call(thisArg, O[i], i, O);
    }
}

return result;

};

// 示例用法
const numbers = [1, 2, 3, 4];
const doubled = numbers.myMap(function(number) {
return number * 2;
});

console.log(doubled); // 输出: [2, 4, 6, 8]

Promise.all

Promise.myAll = function(promises) {
return new Promise((resolve, reject) => {
if (!Array.isArray(promises)) {
return reject(new TypeError(‘Argument must be an array’));
}

    let resolvedCounter = 0;
    const results = [];
    const promisesLength = promises.length;

    if (promisesLength === 0) {
        return resolve([]);
    }

    promises.forEach((promise, index) => {
        Promise.resolve(promise)
            .then(value => {
                resolvedCounter++;
                results[index] = value;

                if (resolvedCounter === promisesLength) {
                    resolve(results);
                }
            })
            .catch(err => reject(err));
    });
});

};

Promise.race

Promise.myRace = function(promises) {
return new Promise((resolve, reject) => {
if (!Array.isArray(promises)) {
return reject(new TypeError(‘Argument must be an array’));
}

    promises.forEach(promise => {
        Promise.resolve(promise)
            .then(resolve)
            .catch(reject);
    });
});

};

接受两个参数控制一次最多六个请求

function limitConcurrentRequests(urls, maxConcurrent) {
return new Promise((resolve, reject) => {
const results = [];
let index = 0; // 当前处理的请求索引
let activeRequests = 0; // 当前正在进行的请求数量

    function next() {
        if (index === urls.length && activeRequests === 0) {
            // 所有请求完成
            resolve(results);
            return;
        }

        while (activeRequests < maxConcurrent && index < urls.length) {
            const currentIndex = index++;
            const url = urls[currentIndex];

            activeRequests++;

            fetch(url)
                .then(response => response.json())
                .then(data => {
                    results[currentIndex] = data;
                })
                .catch(error => {
                    results[currentIndex] = error;
                })
                .finally(() => {
                    activeRequests--;
                    next(); // 发起下一个请求
                });
        }
    }

    next(); // 初始调用
});

}

limitConcurrentRequests(urls, 6).then(results => {
console.log(results);
}).catch(error => {
console.error(‘Error:’, error);
});

1.防抖节流

场景算法题

http://example.com/2024/08/19/场景算法题/

作者

John Doe

发布于

2024年8月19日

许可协议

面经下一篇

场景算法题

二叉树的 Z 型遍历

防抖（Debounce）

节流（Throttle）

合并两个有序数组

写一个类似 new 的函数

使用递归实现深拷贝

二叉树的最大深度

二叉树的最大广度

自定义 map 方法的实现

Promise.all

Promise.race

接受两个参数控制一次最多六个请求

1.防抖节流

写一个类似 `new` 的函数

自定义 `map` 方法的实现