请分别用深度优先思想和广度优先思想实现一个拷贝函数？
好的，以下是使用JavaScript实现深度优先和广度优先的拷贝函数示例：
深度优先拷贝函数：
function deepCopy(obj) {
if (typeof obj !== 'object' || obj === null) {
return obj;
}
let copyObj;
if (Array.isArray(obj)) {
copyObj = [];
for (let i = 0; i < obj.length; i++) {
copyObj.push(deepCopy(obj[i]));
}
} else {
copyObj = {};
for (let key in obj) {
if (obj.hasOwnProperty(key)) {
copyObj[key] = deepCopy(obj[key]);
}
}
}
return copyObj;
}
// 使用示例
let original = {
name: 'John',
age: 30,
address: {
street: '123 Main St',
city: 'New York'
},
hobbies: ['reading', 'painting']
};
let copied = deepCopy(original);
上述代码中，deepCopy()函数使用了递归的深度优先方式进行拷贝。函数会检查对象的类型，如果是基本类型或null，则直接返回该值。对于数组和对象，递归地遍历每个元素或属性，并进行拷贝。
广度优先拷贝函数：
function breadthCopy(obj) {
if (typeof obj !== 'object' || obj === null) {
return obj;
}
let copyObj;
let queue = [];
let copyQueue = [];
if (Array.isArray(obj)) {
copyObj = [];
queue.push(obj);
copyQueue.push(copyObj);
} else {
copyObj = {};
queue.push(obj);
copyQueue.push(copyObj);
}
while (queue.length > 0) {
let current = queue.shift();
let copyCurrent = copyQueue.shift();
for (let key in current) {
if (current.hasOwnProperty(key)) {
let value = current[key];
if (typeof value === 'object' && value !== null) {
let copyValue = Array.isArray(value) ? [] : {};
copyCurrent[key] = copyValue;
queue.push(value);
copyQueue.push(copyValue);
} else {
copyCurrent[key] = value;
}
}
}
}
return copyObj;
}
// 使用示例
let original = {
name: 'John',
age: 30,
address: {
street: '123 Main St',
city: 'New York'
},
hobbies: ['reading', 'painting']
};
let copied = breadthCopy(original);
上述代码中，breadthCopy()函数使用了广度优先的方式进行拷贝。函数使用两个队列，一个用于追踪原始对象的层级结构，另一个用于构建拷贝对象的相应层级结构。通过迭代遍历原始对象的属性，并根据属性值的类型进行相应的拷贝操作，实现广度优先的拷贝。
需要注意的是，上述代码只是简单的示例，实际应用中可能需要根据具体的数据结构和需求进行相应的调整和扩展。
算法手写题
已知如下数组：
var arr = [ [1, 2, 2], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14] ] ] ], 10];
编写一个程序将数组扁平化去并除其中重复部分数据，最终得到一个升序且不重复的数组
简单方法：
Array.form(new Set(arr.flat(Infinity))).sort((a, b) => a - b)
你可以使用递归和Set数据结构来将数组扁平化并去除重复部分数据，然后再将结果数组进行排序。
下面是一个实现该功能的JavaScript代码：
function flattenAndSortArray(arr) {
const flatArray = flatten(arr); // 调用扁平化函数将数组扁平化
const uniqueArray = [...new Set(flatArray)]; // 使用Set数据结构去除重复部分数据
const sortedArray = uniqueArray.sort((a, b) => a - b); // 对数组进行升序排序
return sortedArray;
}
function flatten(arr) {
return arr.reduce((result, current) => {
if (Array.isArray(current)) {
return result.concat(flatten(current)); // 递归处理嵌套数组
}
return result.concat(current);
}, []);
}
var arr = [[1, 2, 2], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14]]]], 10];
var flattenedAndSortedArray = flattenAndSortArray(arr);
console.log(flattenedAndSortedArray);
运行以上代码，将输出结果：
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
在代码中，flattenAndSortArray函数首先调用flatten函数将数组扁平化。flatten函数使用reduce方法遍历数组，如果当前元素是数组，则递归调用flatten函数处理嵌套数组，否则将当前元素添加到结果数组中。
然后，使用Set数据结构去除结果数组中的重复部分数据，通过展开运算符[...new Set(flatArray)]将Set转换为数组。
最后，使用sort方法对数组进行升序排序，得到最终结果。
如何实现一个 new
function _new(fn, ...arg) {
const obj = Object.create(fn.prototype);
const ret = fn.apply(obj, arg);
return ret instanceof Object ? ret : obj;
}
两个数组合并成一个数组
请把两个数组 ['A1', 'A2', 'B1', 'B2', 'C1', 'C2', 'D1', 'D2'] 和 ['A', 'B', 'C', 'D']，合并为 ['A1', 'A2', 'A', 'B1', 'B2', 'B', 'C1', 'C2', 'C', 'D1', 'D2', 'D']。
var array1 = ['A1', 'A2', 'B1', 'B2', 'C1', 'C2', 'D1', 'D2']
var array2 = ['A', 'B', 'C', 'D']
array1.concat(array2).sort((a,b) => {
return a.codePointAt(0) - b.codePointAt(0) ? a.codePointAt(0) - b.codePointAt(0) :(b.length - a.length)
})
改造下面的代码，使之输出0 - 9，写出你能想到的所有解法。
for (var i = 0; i< 10; i++){
setTimeout(() => {
console.log(i);
}, 1000)
}
在原始代码中，由于setTimeout的回调函数是在一个闭包中执行的，并且在setTimeout内部的回调函数执行时，循环已经完成，所以输出的结果是10个10。要实现输出0-9的效果，可以使用以下几种方法：
解法1：使用let关键字
for (let i = 0; i < 10; i++) {
setTimeout(() => {
console.log(i);
}, 1000)
}
解法2：使用闭包
for (var i = 0; i < 10; i++) {
(function (j) {
setTimeout(() => {
console.log(j);
}, 1000)
})(i);
}
解法3：使用setTimeout的第三个参数
for (var i = 0; i < 10; i++) {
setTimeout((j) => {
console.log(j);
}, 1000, i);
}
解法4：使用async/await和setTimeout
const delay = (ms) => new Promise((resolve) => setTimeout(resolve, ms));
async function printNumbers() {
for (var i = 0; i < 10; i++) {
await delay(1000);
console.log(i);
}
}
printNumbers();
这些解法中，解法1使用了ES6的let关键字，它会创建一个块级作用域，每次迭代循环时会创建一个新的变量i。解法2使用了立即执行函数表达式（IIFE）来创建一个新的闭包作用域保留每个迭代的变量值。解法3通过将i作为setTimeout的第三个参数传递来保留每个迭代的变量值。解法4使用了async/await和Promise来实现每次延迟1秒后再进行下一次迭代。
使用迭代的方式实现 flatten 函数。
let arr = [1, 2, [3, 4, 5, [6, 7], 8], 9, 10, [11, [12, 13]]]
迭代实现
function flatten(arr) {
let arrs =[...arr]
let newArr = [];
while (arrs.length){
let item = arrs.shift()
if(Array.isArray(item)){
arrs.unshift(...item)
}else {
newArr.push(item)
}
}
return newArr
}
递归实现
function flatten(arr) {
let arrs = [];
arr.map(item => {
if(Array.isArray(item)){
arrs.push(... flatten(item))
} else {
arrs.push(item)
}
})
return arrs
}
字符串转换
arr.join(',').split(',').map(item => Number(item)))
实现一个 sleep 函数
比如 sleep(1000) 意味着等待1000毫秒，可从 Promise、Generator、Async/Await 等角度实现
以下是使用 Promise、Generator、Async/Await 等方式实现一个 sleep 函数的示例：
- 使用 Promise：
function sleep(ms) {
return new Promise(resolve => setTimeout(resolve, ms));
}
// 使用示例
sleep(1000).then(() => {
console.log('Waited for 1000 milliseconds');
});
- 使用 Generator：
function* sleepGenerator(ms) {
yield new Promise(resolve => setTimeout(resolve, ms));
}
// 使用示例
const sleepFn = sleepGenerator(1000);
sleepFn.next().value.then(() => {
console.log('Waited for 1000 milliseconds');
});
- 使用 Async/Await：
async function sleep(ms) {
await new Promise(resolve => setTimeout(resolve, ms));
}
// 使用示例
async function example() {
await sleep(1000);
console.log('Waited for 1000 milliseconds');
}
example();
这些实现方式都基于 JavaScript 的异步特性，通过创建一个定时器来等待指定的时间（以毫秒为单位），然后通过 Promise、Generator 或 Async/Await 来包裹定时器。这样可以在指定时间后执行回调或者继续执行后续的代码。
实现 (5).add(3).minus(2) 功能
例： 5 + 3 - 2，结果为 6
要实现 (5).add(3).minus(2) 这样的链式操作，需要对数字类型进行扩展，添加 add 和 minus 方法。在 JavaScript 中，数字类型是基本类型，不具备直接添加方法的能力。但可以通过原型链的方式对其进行扩展。
下面是一个示例实现：
Number.prototype.add = function (num) {
return this + num;
};
Number.prototype.minus = function (num) {
return this - num;
};
// 示例用法
const result = (5).add(3).minus(2);
console.log(result); // 输出 6
在上面的示例中，通过给 Number.prototype 添加 add 和 minus 方法，可以将这两个方法应用于数字类型。
add 方法接受一个数字作为参数，将其与当前数字相加并返回结果。minus 方法接受一个数字作为参数，将其从当前数字中减去并返回结果。
通过 (5).add(3).minus(2) 的链式操作，首先将 5 加上 3 得到 8，然后再从 8 中减去 2，最终得到结果 6。
请注意，在 JavaScript 中，数字类型被自动包装为 Number 对象，以便调用其方法。因此，可以在数字后面直接调用 add 和 minus 方法。
需要注意的是，对基本类型进行原型扩展可能会引起命名冲突或与其他库的冲突。因此，在实际开发中，应谨慎使用原型扩展，并确保了解潜在的影响。
要求设计 LazyMan 类，实现以下功能。
LazyMan('Tony');
// Hi I am Tony
LazyMan('Tony').sleep(10).eat('lunch');
// Hi I am Tony
// 等待了10秒...
// I am eating lunch
LazyMan('Tony').eat('lunch').sleep(10).eat('dinner');
// Hi I am Tony
// I am eating lunch
// 等待了10秒...
// I am eating diner
LazyMan('Tony').eat('lunch').eat('dinner').sleepFirst(5).sleep(10).eat('junk food');
// Hi I am Tony
// 等待了5秒...
// I am eating lunch
// I am eating dinner
// 等待了10秒...
// I am eating junk food
class LazyManClass {
constructor(name) {
console.log('Hi! I am ' + name);
this.tasks = [];
// 最关键点在这里，开始第一次调用
setTimeout(() => {
this.next();
}, 0);
}
eat(food) {
let self = this;
self.tasks.push(() => {
console.log(`I am eating ${food}`);
self.next()
});
return self;
}
sleepFirst(time) {
let self = this;
self.tasks.unshift(() => {
setTimeout(() => {
console.log(`等待了${time}秒...`)
self.next();
}, time * 1000);
});
return self;
}
sleep(time) {
let self = this;
self.tasks.push(() => {
setTimeout(() => {
console.log(`等待了${time}秒...`)
self.next();
}, time * 1000);
});
return self;
}
next() {
const task = this.tasks.shift();
task && task();
}
}
function LazyMan(name) {
return new LazyManClass(name);
}
LazyMan('Tony').eat('lunch').eat('dinner').sleepFirst(5).sleep(10).eat('junk food');
给定两个数组，写一个方法来计算它们的交集。
例如：给定 nums1 = [1, 2, 2, 1]，nums2 = [2, 2]，返回 [2, 2]。
var nums1 = [1, 2, 2, 1];
var nums2 = [2, 2];
// 时间复杂度：O(m * n)
var intersection = function(nums1, nums2) {
let arr = [];
for(let i = 0;i< nums1.length;i++){
var findIndex = nums2.indexOf(nums1[i]);
if(findIndex>=0){
arr.push(nums1[i]);
nums2.splice(findIndex,1);
}
}
return arr;
};
// hash
var intersection = function(nums1, nums2) {
let arr = [];
let map = nums1.reduce((prev, cur, index, arr) => {
if(!prev.has(cur)){
prev.set(cur,1);
}else{
prev.set(cur,(prev.get(cur) + 1));
}
return prev;
},new Map());
for(let i = 0;i< nums2.length;i++){
if(map.get(nums2[i]) > 0){
arr.push(nums2[i]);
map.set(nums2[i],(map.get(nums2[i]) - 1));
}
}
return arr;
}
模拟实现一个 Promise.finally
下面是一个简单的模拟实现 Promise.finally 方法的示例代码：
// 模拟实现 Promise.finally
if (!Promise.prototype.finally) {
Promise.prototype.finally = function (callback) {
var Fn = this.constructor; // 获取当前实例构造函数的引用
return this.then(
value => Fn.resolve(callback()).then(() => value),
reason => Fn.resolve(callback()).then(() => { throw reason })
);
};
}
// 示例使用
const promise = new Promise((resolve, reject) => {
// 模拟异步操作
setTimeout(() => {
resolve('Success');
// reject('Error');
}, 1000);
});
promise
.then(result => {
console.log('Resolved:', result);
})
.catch(error => {
console.log('Rejected:', error);
})
.finally(() => {
console.log('Finally');
});
在上述代码中，我们首先检查 Promise.prototype.finally 方法是否已经存在，如果不存在，则进行模拟实现。
Promise.prototype.finally 方法接受一个回调函数作为参数，该回调函数将在 Promise 结束时（无论是成功还是失败）被调用。在模拟实现中，我们通过调用 this.then 方法来处理 finally 中的逻辑。
在 this.then 方法中，我们使用 Promise.resolve(callback()) 包装回调函数的调用，以确保回调函数始终返回一个 Promise 对象。在 then 的 onFulfilled 回调中，我们通过 then(() => value) 将结果值传递给下一个 then，保持 Promise 链的正常执行。在 then 的 onRejected 回调中，我们使用 then(() => { throw reason }) 抛出错误，以确保错误能够正确地传递给链中的下一个 catch。
在示例使用中，我们创建了一个异步的 Promise 对象，并在 then 和 catch 中打印相应的结果。然后，我们添加了 finally 方法，并在其中打印 "Finally"。无论 Promise 是成功还是失败，finally 方法中的回调函数都会被执行。
请注意，上述代码只是一个简单的模拟实现，并不考虑所有的边界情况和 Promise/A+ 规范的细节。在实际应用中，建议使用原生的 Promise.finally 方法或者使用符合规范的 Promise 库来确保更好的兼容性和可靠性。
数组编程题
随机生成一个长度为 10 的整数类型的数组，例如 [2, 10, 3, 4, 5, 11, 10, 11, 20]，将其排列成一个新数组，要求新数组形式如下，例如 [[2, 3, 4, 5], [10, 11], [20]]。
// 生成随机数
var genRandomNum = (min,max) => Math.floor(Math.random() * (max - min + 1)) + min;
// 生成数组
function genArray(size,min,max){
//去重
var array = new Set();
// 生成指定长度数组
while(array.size < size){
array.add(genRandomNum(min,max))
}
// 排序
array = Array.from(array).sort((a,b) => (a-b));
// 构建hash
var map = new Map();
// 放入hash
array.forEach(v => {
let index = Math.floor(v / 10);
if(map.has(index)){
map.set(index, map.get(index).concat(v));
}else{
map.set(index, [v]);
}
})
// 输出结果
return Array.from(map.values())
}
实现一个字符串匹配算法，从长度为 n 的字符串 S 中，查找是否存在字符串 T，T 的长度是 m，若存在返回所在位置。
方法一：
const find = (S, T) => S.search(T)
方法二：
const find = (S, T) => {
const matched = S.match(T)
return matched ? matched.index : -1
}
方法三：
function searchStr(S, T){
if(S.length < T.length) return -1;
for(let i = 0; i< S.length;i++){
if(S.slice(i, i + T.length) === T){
return i
}
}
return -1;
}
使用 JavaScript Proxy 实现简单的数据绑定
使用 JavaScript 的 Proxy 对象可以实现简单的数据绑定。下面是一个示例，演示了如何使用 Proxy 对象监听对象属性的变化并触发回调函数：
<body>
hello,world
<input type="text" id="model">
<p id="word"></p>
</body>
<script>
const model = document.getElementById("model")
const word = document.getElementById("word")
var obj= {};
const newObj = new Proxy(obj, {
get: function(target, key, receiver) {
console.log(`getting ${key}!`);
return Reflect.get(target, key, receiver);
},
set: function(target, key, value, receiver) {
console.log('setting',target, key, value, receiver);
if (key === "text") {
model.value = value;
word.innerHTML = value;
}
return Reflect.set(target, key, value, receiver);
}
});
model.addEventListener("keyup",function(e){
newObj.text = e.target.value
})
</script>
算法题「旋转数组」
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
示例 1：
输入: [1, 2, 3, 4, 5, 6, 7] 和 k = 3
输出: [5, 6, 7, 1, 2, 3, 4]
解释:
向右旋转 1 步: [7, 1, 2, 3, 4, 5, 6]
向右旋转 2 步: [6, 7, 1, 2, 3, 4, 5]
向右旋转 3 步: [5, 6, 7, 1, 2, 3, 4]
示例 2：
输入: [-1, -100, 3, 99] 和 k = 2
输出: [3, 99, -1, -100]
解释:
向右旋转 1 步: [99, -1, -100, 3]
向右旋转 2 步: [3, 99, -1, -100]
当需要将数组中的元素向右移动 k 个位置，并且要求使用空间复杂度为 O(1) 的原地算法时，可以考虑以下三种不同的解决方案：
方法一：使用反转
- 首先，将整个数组反转。
- 然后，将前 k 个元素反转。
- 最后，将剩余的 n-k 个元素反转。
这种方法可以实现原地旋转，不需要额外的空间。以下是使用该方法的 JavaScript 代码示例：
function rotateArray(nums, k) {
const n = nums.length;
k = k % n;
reverse(nums, 0, n - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, n - 1);
return nums;
}
function reverse(nums, start, end) {
while (start < end) {
const temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++;
end--;
}
}
// 示例测试
const nums1 = [1, 2, 3, 4, 5, 6, 7];
const k1 = 3;
console.log(rotateArray(nums1, k1)); // 输出: [5, 6, 7, 1, 2, 3, 4]
const nums2 = [-1, -100, 3, 99];
const k2 = 2;
console.log(rotateArray(nums2, k2)); // 输出: [3, 99, -1, -100]
方法二：使用循环交换
- 首先，计算数组的长度 n 和有效的移动次数 k = k % n。
- 使用一个循环，从 0 开始遍历到 n-1：
- 在每一步迭代中，将当前位置的元素与 (i+k) % n 的位置上的元素进行交换。
这种方法也可以实现原地旋转，只需要常数级别的额外空间。以下是使用该方法的 JavaScript 代码示例：
function rotateArray(nums, k) {
const n = nums.length;
k = k % n;
let count = 0;
for (let start = 0; count < n; start++) {
let current = start;
let prev = nums[start];
do {
const next = (current + k) % n;
const temp = nums[next];
nums[next] = prev;
prev = temp;
current = next;
count++;
} while (start !== current);
}
return nums;
}
// 示例测试
const nums1 = [1, 2, 3, 4, 5, 6, 7];
const k1 = 3;
console.log(rotateArray(nums1, k1)); // 输出: [5, 6, 7, 1, 2, 3, 4]
const nums2 = [-1, -100, 3, 99];
const k2 = 2;
console.log(rotateArray(nums2, k2)); // 输出: [3, 99, -1, -100]
方法三：使用额外数组
- 首先，创建一个额外的数组，将原数组的元素按照移动后的位置存储到额外数组中。
- 最后，将额外数组的元素复制回原数组。
这种方法使用了额外的空间，但仍然可以达到 O(1) 的空间复杂度，因为额外数组的大小与原数组相同。以下是使用该方法的 JavaScript 代码示例：
function rotateArray(nums, k) {
const n = nums.length;
k = k % n;
const rotatedArray = [];
for (let i = 0; i < n; i++) {
rotatedArray[(i + k) % n] = nums[i];
}
for (let i = 0; i < n; i++) {
nums[i] = rotatedArray[i];
}
return nums;
}
// 示例测试
const nums1 = [1, 2, 3, 4, 5, 6, 7];
const k1 = 3;
console.log(rotateArray(nums1, k1)); // 输出: [5, 6, 7,1, 2, 3, 4]
const nums2 = [-1, -100, 3, 99];
const k2 = 2;
console.log(rotateArray(nums2, k2)); // 输出: [3, 99, -1, -100]
这些是三种使用空间复杂度为 O(1) 的原地算法来将数组中的元素向右移动 k 个位置的方法。每种方法都有其自己的优势和适用场景，可以根据具体的需求选择合适的方法来解决问题。
补充：纯js方法
var rotate = function (nums, k) {
nums.unshift(...nums.splice(nums.length - k, k))
return nums
};
打印出 1 - 10000 之间的所有对称数
例如：121、1331 等
核心点：不要去循环10000次，而是从1开始构造对称数，到10000就停止
let result=[]
for(let i=1;i<10;i++){
result.push(i)
result.push(i*11)
for(let j=0;j<10;j++){
result.push(i*101+j*10)
result.push(i*1001+j*110)
}
}
周一算法题之「移动零」
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:
必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。
let nums = [0,1,0,3,12];
function sortArr(nums) {
let i = 0;
for (let j = 0; j < nums.length; j++) {
if (nums[j] !== 0) {
nums[i] = nums[j];
i++;
}
}
while (i < nums.length) {
nums[i] = 0;
i++;
}
return nums;
}
请实现一个 add 函数，满足以下功能。
add(1); // 1
add(1)(2); // 3
add(1)(2)(3); // 6
add(1)(2, 3); // 6
add(1, 2)(3); // 6
add(1, 2, 3); // 6
题目有点问题，一种是考柯里化，一种是使用toString来hack。
柯里化：
function Add(a, b, c) {
return a + b + c ;
}
function curring(fn) {
let length = fn.length;
let args = [];
return function inner() {
let innerArgs = Array.prototype.slice.call(arguments);
args = args.concat(innerArgs)
if (args.length >= length) {
return fn.apply(null, args)
} else {
return inner;
}
}
}
var add = curring(Add);
add(1)(2)(3); // 6
add(1)(2, 3); // 6
add(1, 2)(3); // 6
add(1, 2, 3); // 6
toString方式：
function add(...num) {
let res = 0 //第一次调用函数时生成一个闭包来存储结果
num.forEach(item => res += item) //遍历输入参数加到res上
let ret = function (...num) {
num.forEach(item => res += item)
return ret
}
ret.toString = function () {
return res
}
ret.valueOf = function () {
return res
}
return ret
}
add(1).toString(); // 1
add(1)(2).toString(); // 2
add(1)(2)(3).toString(); // 6
add(1)(2)(3, 7)(4, 5, 6).toString();// 28
周一算法题之「两数之和」
给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
示例：
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
function twoSum(nums, target) {
var map = new Map();
for (let i = 0; i < nums.length; i++) {
let diff = target - nums[i];
if (map.has(diff)) {
return [i, map.get(diff)]
} else {
map.set(nums[i], i);
}
}
return [];
}
var res = towSum([2, 7, 11, 15], 9)
console.log(res);
实现 convert 方法，把原始 list 转换成树形结构，要求尽可能降低时间复杂度
以下数据结构中，id 代表部门编号，name 是部门名称，parentId 是父部门编号，为 0 代表一级部门，现在要求实现一个 convert 方法，把原始 list 转换成树形结构，parentId 为多少就挂载在该 id 的属性 children 数组下，结构如下：
// 原始 list 如下
let list =[
{id:1,name:'部门A',parentId:0},
{id:2,name:'部门B',parentId:0},
{id:3,name:'部门C',parentId:1},
{id:4,name:'部门D',parentId:1},
{id:5,name:'部门E',parentId:2},
{id:6,name:'部门F',parentId:3},
{id:7,name:'部门G',parentId:2},
{id:8,name:'部门H',parentId:4}
];
const result = convert(list, ...);
// 转换后的结果如下
let result = [
{
id: 1,
name: '部门A',
parentId: 0,
children: [
{
id: 3,
name: '部门C',
parentId: 1,
children: [
{
id: 6,
name: '部门F',
parentId: 3
}, {
id: 16,
name: '部门L',
parentId: 3
}
]
},
{
id: 4,
name: '部门D',
parentId: 1,
children: [
{
id: 8,
name: '部门H',
parentId: 4
}
]
}
]
},
···
];
要将原始的列表转换为树形结构，可以利用哈希表来提高效率。首先，遍历原始列表，将每个部门以其id作为键存储在哈希表中。然后，再次遍历列表，根据每个部门的parentId将其添加到相应的父部门的children数组中。
以下是一个实现该转换方法的示例代码：
function convert(list) {
const map = {};
const result = [];
// 第一次遍历，构建哈希表
for (const item of list) {
const { id, name, parentId } = item;
map[id] = { id, name, parentId, children: [] };
}
// 第二次遍历，构建树形结构
for (const item of list) {
const { id, parentId } = item;
const department = map[id];
if (parentId === 0) {
// 根部门
result.push(department);
} else {
// 子部门
const parent = map[parentId];
parent.children.push(department);
}
}
return result;
}
// 示例测试
const list = [
{ id: 1, name: '部门A', parentId: 0 },
{ id: 2, name: '部门B', parentId: 0 },
{ id: 3, name: '部门C', parentId: 1 },
{ id: 4, name: '部门D', parentId: 1 },
{ id: 5, name: '部门E', parentId: 2 },
{ id: 6, name: '部门F', parentId: 3 },
{ id: 7, name: '部门G', parentId: 2 },
{ id: 8, name: '部门H', parentId: 4 }
];
const result = convert(list);
console.log(result);
在这段代码中，我们首先创建了一个空对象 map 作为哈希表，用于存储部门信息。第一次遍历原始列表时，将每个部门对象存储在哈希表中，以部门的id作为键。然后，第二次遍历列表，根据每个部门的parentId，将其添加到相应的父部门的children数组中。如果parentId为0，则将部门视为根部门，直接添加到结果数组中。
通过这种方式，我们只需要进行两次遍历，时间复杂度为O(n)，其中n是原始列表的长度。通过使用哈希表，我们可以在常数时间内根据部门的id查找到相应的部门对象，从而快速构建树形结构。
设计并实现 Promise.race()
Promise.race() 方法用于将多个 Promise 对象包装成一个新的 Promise，并返回最先 resolved 或 rejected 的 Promise 的结果或原因。
以下是一个简单的实现 Promise.race() 的例子：
function promiseRace(promises) {
return new Promise((resolve, reject) => {
for (const promise of promises) {
promise.then(resolve).catch(reject);
}
});
}
// 示例使用
const promise1 = new Promise((resolve) => {
setTimeout(() => resolve('Promise 1 resolved'), 1000);
});
const promise2 = new Promise((resolve, reject) => {
setTimeout(() => reject(new Error('Promise 2 rejected')), 500);
});
const promise3 = new Promise((resolve) => {
setTimeout(() => resolve('Promise 3 resolved'), 2000);
});
const racePromise = promiseRace([promise1, promise2, promise3]);
racePromise.then((result) => {
console.log('Race result:', result);
}).catch((error) => {
console.error('Race error:', error);
});
在这个例子中，我们定义了一个 promiseRace() 函数，它接收一个 Promise 数组 promises 作为参数。在函数内部，我们创建了一个新的 Promise，并使用 resolve 和 reject 参数来控制该 Promise 的状态和结果。
然后，我们遍历 promises 数组，对每个 Promise 调用 then() 方法和 catch() 方法。如果有任何一个 Promise 被 resolved，我们通过 resolve 参数将结果传递给新的 Promise，从而使其最终 resolved。如果有任何一个 Promise 被 rejected，我们通过 reject 参数将原因传递给新的 Promise，使其最终 rejected。
最后，我们通过调用 then() 方法和 catch() 方法来处理 racePromise 这个新的 Promise 的结果或原因。
注意，这只是一个简单的实现，并没有处理一些特殊情况，例如传入空数组或传入非 Promise 对象等。在实际使用中，需要根据具体需求和场景对 Promise.race() 方法进行更全面和健壮的实现。
实现模糊搜索结果的关键词高亮显示
要实现模糊搜索结果的关键词高亮显示，可以使用 HTML 和 CSS 来改变搜索结果中匹配关键词的样式。以下是一个简单的实现示例：
function highlightKeywords(searchText, resultText) {
const regex = new RegExp(searchText, 'gi');
return resultText.replace(regex, (match) => `<span class="highlight">${match}</span>`);
}
// 示例使用
const searchText = 'example';
const resultText = 'This is an example text for highlighting example.';
const highlightedText = highlightKeywords(searchText, resultText);
console.log(highlightedText);
在这个例子中，我们定义了一个函数 highlightKeywords()，它接收两个参数：searchText 是搜索关键词，resultText 是搜索结果文本。
在函数内部，我们使用 new RegExp() 构造函数创建一个正则表达式，其中使用了 'gi' 修饰符来进行全局匹配和不区分大小写的搜索。
然后，我们使用 replace() 方法来替换匹配到的关键词。在替换的回调函数中，我们将匹配到的关键词用 <span class="highlight"> 标签包裹起来，从而改变其样式。
最后，函数返回经过关键词高亮处理的结果文本。
在使用时，你可以将搜索关键词和搜索结果传递给 highlightKeywords() 函数，得到高亮显示的文本结果。
为了实现高亮样式，你可以使用 CSS 来定义 .highlight 类的样式，例如：
.highlight {
background-color: yellow;
font-weight: bold;
}
上述 CSS 样式会将匹配到的关键词文本的背景色设置为黄色，并加粗显示。
请注意，这只是一个简单的实现示例，你可以根据自己的需求和样式要求对关键词高亮的方式进行定制和扩展。
已知数据格式，实现一个函数 fn 找出链条中所有的父级 id
const value = '112'
const fn = (value) => {
...
}
fn(value) // 输出 [1， 11， 112]
// dfs
const data = [
{
id: '1',
name: 'test1',
children: [
{
id: '11',
name: 'test11',
children: [
{
id: '111',
name: 'test111'
},
{
id: '112',
name: 'test112'
}
]
},
{
id: '12',
name: 'test12',
children: [
{
id: '121',
name: 'test121',
children: [
{
id: '1221',
name: 'test121',
children: [
{
id: '12345'
}
]
}
]
}
]
}
]
},
{
id: '1234',
children: [
{
id: '567'
}
]
}
]
function treverse(list, target) {
let res = [];
function dfs(arr, ids = []) {
for (const item of arr) {
if (item.id === target) {
res = [...ids, item.id];
} else {
if (Array.isArray(item.children)) {
dfs(item.children, ids.concat(item.id))
}
}
}
}
dfs(list, [])
return res;
}
console.log(treverse(data, '12345'));//[ '1', '12', '121', '1221', '12345' ]
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log(m+n))。
示例 1：
nums1 = [1, 3]
nums2 = [2]
中位数是 2.0
示例 2：
nums1 = [1, 2]
nums2 = [3, 4]
中位数是(2 + 3) / 2 = 2.5
leetcode 4. 寻找两个正序数组的中位数
https://leetcode.cn/problems/median-of-two-sorted-arrays/submissions/516627948/
function findMedianSortedArrays(nums1, nums2) {
// 由于nums1的长度和nums2的长度已知，所以中位数的位置也就知道了，
// 比如奇数在合并后的第(m + n + 1) / 2个，偶数在合并后的第(m + n) / 2和第(m + n) / 2 + 1个
// 只需要双指针，依次从左到右数够这几个数就行了
let m = nums1.length;
let n = nums2.length;
let left = 0, right = 0;
let preValue = -1; currentValue = -1;
for (let i = 0; i <= Math.floor((m + n) / 2); i++) {
preValue = currentValue;
if ((nums1[left] < nums2[right] || right >= n) && left < m) {
currentValue = nums1[left];
left++;
} else {
currentValue = nums2[right];
right++;
}
}
return (m + n) % 2 === 0 ? (preValue + currentValue) / 2 : preValue;
}
console.log(findMedianSortedArrays([1, 2], [3, 4]));
编程算法题
用 JavaScript 写一个函数，输入 int 型，返回整数逆序后的字符串。如：输入整型 1234，返回字符串“4321”。要求必须使用递归函数调用，不能用全局变量，输入函数必须只有一个参数传入，必须返回字符串。
function reverse(num) {
return num >= 10 ? `${num % 10}${reverse(Math.floor(num / 10))}` : `${num}`;
}
console.log(reverse(384729));//927483
console.log(reverse(38000));//00083
0 1 1 2 3 5 8，假设第 0 个是 0，第 1 个是 1，求第 n 个数的实现方式？
实现一个扑克牌式的插入排序（我们总是喜欢将某张扑克牌插入到已排序的扑克中），输入：[5,6,1,8,7,2,4,3]，输出：[1,2,3,4,5,6,7]，并提供单元测试思路（如何测试你的代码是稳定正确的）？
实现一个简易的模板引擎
let template = '嗨，{{name}}您好，今天是星期 {day}';
let data = {
name: '张三',
day: '三'
}
render(template, data); // 嗨，张三您好，今天是星期三