前端面经（Js手撕题部分）

10.1 并发限制

class Scheduler {
    constructor(max){
        this.max = max
        this.count = 0
        this.queue = []
    }
    async add(fn){
        if(this.count >= this.max){
            await new Promise(resolve => this.queue.push(resolve))
        }
        this.count++
        const res = await fn()
        this.count--
        this.queue.length && this.queue.shift()()
        return res
    }
}

class Scheduler {
    constructor(max){
        this.max = max
        this.count = 0
        this.queue = []
    }
    add(fn){
        this.queue.push(fn)
    }
    start(){
        for(let i = 0; i < this.max; i++){
            this.doNext()
        }
    }
    doNext(){
        if(this.queue.length && this.max >= this.count){
            this.count++
            this.queue.shift()().then(()=>{
                this.count--
                this.doNext()
            })

        }
    }
}




const scheduler = new Scheduler(2)

const timeout = time => new Promise(resolve => setTimeout(resolve,time))

const addTask = (time,order) => {
    scheduler.add(() => timeout(time).then(()=>console.log(order)))
}

addTask(1000,1)
addTask(500,2)
addTask(300,3)
addTask(400,4)

function limitQueue(urls, limit) {
    // 完成任务数
    let i = 0;
    // 填充满执行队列
    for (let excuteCount = 0; excuteCount < limit; excuteCount++) {
        run();
    }
    // 执行一个任务
    function run() {
        // 构造待执行任务 当该任务完成后 如果还有待完成的任务 继续执行任务
        new Promise((resolve, reject) => {
            const url = urls[i];
            i++;
            resolve(fn(url))
        }).then(() => {
            if (i < urls.length) run()
        })
    }
}
const fn = url => {
    // 实际场景这里用axios等请求库 发请求即可 也不用设置延时
    return new Promise(resolve => {
        setTimeout(() => {
            console.log('完成一个任务', url, new Date());
            resolve({ url, date: new Date() });
        }, 1000);
    })
};
const urls = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15];

(async _ => {
    await limitQueue(urls, 4);
})()

10.2 Promise输出

• 40道Promise输出题，你都会了吗？🔥 - 掘金 (juejin.cn)

10.3 setTimeout()

​ 渲染进程所有运行在主线程上的任务都需要先添加到消息队列中,然后事件循环系统顺序执行消息队列。​ eg: 解析 DOM; 改变 web 大小, 重新布局; js 垃圾回收; 异步执行 js 代码​ 但是定时器的任务不能直接放置在消息队列中,他需要按照时间间隔来执行。因此,chrome 除了消息队列外,新增了个延时队列,在每次执行完任务后,执行延迟队列中的任务,计算出到期任务,依次执行。最小执行时间4ms。

代码实现:

1） 在每次新增一个定时器时,将定时器添加到 DelayTask 中；2） 执行消息循环时,在当前任务执行完成时,执行延迟队列中的任务,ProcessTimerTask 函数会根据发起时间和延迟时间计算出到期的任务，然后依次执行这些到期的任务；3） 查找延迟队列中的已到期任务执行；4） 取消定时器: 从 delayed_incoming_queue 根据定时器 id 查找到定时器并删除；

DelayedIncomingQueue delayed_incoming_queue;

// 当通过 JavaScript 调用 setTimeout 设置回调函数的时候，渲染进程将会创建一个回调任务，包含了回调函数 showName、当前发起时间、延迟执行时间
struct DelayTask{
  int64 id；
  CallBackFunction cbf;
  int start_time;
  int delay_time;
};
DelayTask timerTask;
timerTask.cbf = showName;
timerTask.start_time = getCurrentTime(); //获取当前时间
timerTask.delay_time = 200;//设置延迟执行时间

// 创建好回调任务之后，再将该任务添加到延迟执行队列中
delayed_incoming_queue.push(timerTask)；



void ProcessTimerTask(){
  //从delayed_incoming_queue中取出已经到期的定时器任务
  //依次执行这些任务
}

//消息循环系统是 触发延迟队列的
TaskQueue task_queue；
void ProcessTask();
bool keep_running = true;
void MainTherad(){
  for(;;){
    //执行消息队列中的任务
    Task task = task_queue.takeTask();
    ProcessTask(task);

    //执行延迟队列中的任务
    ProcessTimerTask()

    if(!keep_running) //如果设置了退出标志，那么直接退出线程循环
        break;
  }
}

Settimeout有4ms的延迟可以通过postMessage解决（处理页面中嵌套iframe跨域的问题，它的通信原理类似于TCP三次握手，不但能解决各种跨域问题，而且实时性高。）

参考：

https://juejin.cn/post/6961673921150238751

10.4 版本号排序

arr.sort((a, b) => {
  let i = 0;
  const arr1 = a.split(".");
  const arr2 = b.split(".");
 
  while (true) {
    const s1 = arr1[i];
    const s2 = arr2[i];
    i++;
    if (s1 === undefined || s2 === undefined) {
      return arr2.length - arr1.length;
    }
 
    if (s1 === s2) continue;
 
    return s2 - s1;
  }
});

10.5 Sleep()

const sleep = time => {
 return new Promise(resolve => setTimeout(resolve,time)
 ) } 
const sleep = time => {
 return new Promise(resolve => setTimeout(()=>{resolve()},time)
 ) } 
 sleep(1000).then(()=>{ console.log(1) })

10.6 手写JS

https://juejin.cn/post/6875152247714480136

10.7 缓存装饰器

function cacheDecorator(func) {
  let cache = new Map();

  return function (...args) {
    let key = JSON.stringify(args);
    if (cache.has(key)) {
      return cache.get(key);
    }
	// 如果缓存中没有这个键，我们调用原来的函数 func，并将结果保存在 result 中。
    let result = func.apply(this, args);
    cache.set(key, result);
    return result;
  };
}

10.8 限制次数内重试

function retryPromise(func, retries = 5) {
  return new Promise((resolve, reject) => {
    const attempt = (n) => {
      func().then(resolve).catch((error) => {
        if (n === 0) {
          reject(error);
        } else {
          attempt(n - 1);
        }
      });
    };
    attempt(retries);
  });
}

10.9 bigint相加

let a = "9007199254740991";
let b = "1234567899999999999";

function add(a ,b){
   //取两个数字的最大长度
   let maxLength = Math.max(a.length, b.length);
   //用0去补齐长度
   a = a.padStart(maxLength , 0);//"0009007199254740991"
   b = b.padStart(maxLength , 0);//"1234567899999999999"
   //定义加法过程中需要用到的变量
   let t = 0;
   let f = 0;   //"进位"
   let sum = "";
   for(let i=maxLength-1 ; i>=0 ; i--){
      t = parseInt(a[i]) + parseInt(b[i]) + f;
      f = Math.floor(t/10);
      sum = t%10 + sum;
   }
   if(f == 1){
      sum = "1" + sum;
   }
   return sum;
}

10.10 防抖和节流

使用场景：防抖和节流

防抖：让事件在触发后N秒后执行，如果在N秒内重新触发，则重新计算时间。

场景：

• 按钮双击，我们平时电脑上快速双击就有可能触发两次点击事件
• 输入框的input或者change时间
• 轮动条

function debounce(fn, delay){
    let timer
    return function(){
        if(timer) clearTimeout(timer)
        let args = arguments
        timer = setTimeout(()=>{
            fn.apply(this,args)
        }, delay)
    }
}

// input实现防抖
<div>
<input type="text" id="ipt">
</div> <script>
let ipt = document.getElementById('ipt');
let dbFun = debounce()
ipt.addEventListener('keyup', function (e) {
dbFun(e.target.value);
})
function debounce() {
let timer;
return function (value) {
clearTimeout(timer);
timer = setTimeout(() =>
{
console.log(value)
}, 500);
}
}
</script>

节流：在规范时间内，只能触发一次函数，如果多次触发不会执行。

function throttle(func, time) {
    let lastTime = null;
    return function (...args) {
        let now = +new Date()
        if (now - lastTime > wait) {
            lastTime = now
            func.apply(this, args)
        }
    }
}
var throttle = function(fn, t) {
    let timer = null
    let tempArgs = null
  const func = function(...args) {
      if(!timer){
          fn(...args)
          timer = setTimeout(_=>{
              timer = null
              if(tempArgs){
                  func(...tempArgs)
              }
              tempArgs = null
          }, t)
      }else{
          tempArgs = args
      }
  }
  return func
};

10.11 Promise.all

function promiseAll(promises) {
    return new Promise(function(resolve, reject) {
        // 记录已解决的 promise 的数量
        let resolvedCount = 0;
        // 记录每个 promise 的结果
        const promiseResults = new Array(promises.length);

        for (let i = 0; i < promises.length; i++) {
            // 立即执行每个 promise
            promises[i].then(
                // promise 成功解决
                value => {
                    resolvedCount++;
                    promiseResults[i] = value;

                    // 如果所有的 promise 都解决了，那么我们可以解决总的 promise
                    if (resolvedCount === promises.length) {
                        resolve(promiseResults);
                    }
                },
                // 如果任何一个 promise 失败了，我们都需要拒绝总的 promise
                error => {
                    reject(error);
                }
            );
        }
    });
}
const promises = [
    Promise.resolve('Promise 1'),
    Promise.resolve('Promise 2'),
    Promise.resolve('Promise 3'),
    Promise.resolve('Promise 4')
];

promiseAll(promises)
    .then((fulfilled) => {
        console.log('Fulfilled promises:', fulfilled);
    })
    .catch((reason) => {
        console.error('Error:', reason);
    });

//race
//方法接收一个包含多个 Promise 对象的可迭代对象，并返回一个新的 Promise 对象，该 Promise 对象在多个 Promise 中任意一个 Promise 对象状态变为 fulfilled 或 rejected 时立即返回该 Promise 对象的值或原因。
function promiseRace(promises) {
    return new Promise((resolve, reject) => {
        if (!Array.isArray(promises)) {
            reject(new TypeError('Promises must be an array'));
            return;
        }

        if (promises.length === 0) {
            reject(new Error('Promises array must not be empty'));
            return;
        }

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

//some
function PromiseSome(promises, n) {
    return new Promise((resolve, reject) => {
        if (promises.length < n) reject('Not enough promises to fulfill the request');

        let results = [];
        let settled = 0;
        let stillPending = promises.length;

        promises.forEach((promise, i) => {
            Promise.resolve(promise)
                .then(value => {
                    settled += 1;
                    results[i] = value;
                    stillPending -= 1;

                    if (settled >= n) {
                        resolve(results);
                    }
                })
                .catch(() => {
                    stillPending -= 1;

                    if (stillPending + settled < n) {
                        reject('Too many promises rejected');
                    }
                });
        });
    });
};

//any
MyPromise.any = function(promises){
  return new Promise((resolve,reject)=>{
    promises = Array.isArray(promises) ? promises : []
    let len = promises.length
    // 用于收集所有 reject 
    let errs = []
    // 如果传入的是一个空数组，那么就直接返回 AggregateError
    if(len === 0) return reject(new AggregateError('All promises were rejected'))
    promises.forEach((promise)=>{
      promise.then(value=>{
        resolve(value)
      },err=>{
        len--
        errs.push(err)
        if(len === 0){
          reject(new AggregateError(errs))
        }
      })
    })
  })
}

Promise.prototype.finally = function (callback) {
let P = this.constructor;
return this.then(
value => P.resolve(callback()).then(() => value),
reason => P.resolve(callback()).then(()
=> { throw reason })
);
};

// none
Promise.none = function(promises) {
    return Promise.all(promises.map(promise => {
        return new Promise((resolve, reject) => {
            // Promise.all里边的所有promise实例反过来就好了
            return Promise.resolve(promise).then(reject, resolve)
        })
    }))
}
// none2
Promise.none = function(promises) {
    return new Promise(function(resolve, reject) {
        let count = promises.length;
        let reasons = new Array(count);
        if (count === 0) {
            resolve(reasons);
            return;
        }

        promises.forEach(function(promise, index) {
            Promise.resolve(promise).then(function() {
                reject(new Error("At least one promise resolved"));
            }, function(reason) {
                reasons[index] = reason;
                if (--count === 0) {
                    resolve(reasons);
                }
            });
        });
    });
};
const promisesForNoneTest1= [
    Promise.reject('1'),
    Promise.reject('2'),
    Promise.resolve('3'),
    Promise.reject('4'),
]
Promise.none(promisesForNoneTest1).then(res => {
    console.log('true promises:', res);
}, res => {
    console.log('false promises:', res);
})

 Promise.first = function(promises) {
    return new Promise((resolve, reject) => {
      let rejectNum = 0
      promises.forEach(promise => {
        // 如果当前 promise 决议为reslove，那就直接执行"根promise"的resolve
        // 否则去记录到拒绝的promise中，然后判断全部的promise拒绝了，执行"根promise"的reject
        Promise.resolve(promise).then(resolve, () => {
          if (++rejectNum === promises.length) {
            // 这里可以控制reject返回的信息
            reject()
          }
        })
      })
    })
  }

Promise.map = function(arr, mapper) {
    // 首先，使用 map 将数组中的每个元素都转换为 promise。
    let promises = arr.map((item, index, arr) => Promise.resolve(mapper(item, index, arr)));

    // 然后，使用 Promise.all 来等待所有 promise 都 resolve。
    return Promise.all(promises);
};
let mapper = function(num) {
    return new Promise((resolve, reject) => {
        setTimeout(() => {
            console.log(num);  // 输出处理的数字
            resolve(num);
        }, 1000);
    });
};
let nums = [1, 2, 3, 4, 5];
Promise.map(nums, mapper)
    .then(results => {
        console.log('All promises are resolved');
        console.log('Results:', results);  // 输出：Results: [ 1, 2, 3, 4, 5 ]
    })
    .catch(err => {
        console.log('A promise rejected with', err);
    });

10.12 apply&bind

//apply&call
Function.prototype.myApply = function (context, args) {
    console.log(this)
    context = context || window;
    const fnSymbol = Symbol();
    context[fnSymbol] = this;
    const result = context[fnSymbol](...args);
    delete context[fnSymbol];
    return result;
};
//bind
Function.prototype.myBind = function (){
    const args = [...arguments]
    const self = args.shift()
    console.log(this)
    const t = this
    return function (){
        t.apply(self,args.concat(...arguments))
    }
}

10.13 数组转树

function formatToTree(ary, pid, pidName = 'parentId') {
  return ary
      .filter((item) => item[pidName] === pid)
      .map((item) => {
          // 通过父节点ID查询所有子节点
          item.children = formatToTree(ary, item.id);
        return item;
      });
}
const data = [{ id: 2, name: "研发部", parentId: 1 },...]

10.14 排序

冒泡排序	O(n2)	O(n2)	O(1)	是
选择排序	O(n2)	O(n2)	O(1)	不是
直接插入	O(n2)	O(n2)	O(1)	是
归并	O(nlogn)	O(nlogn)	O(n)	是
快排	O(nlogn)	O(n2)	O(logn)	不是
堆排序	O(nlogn)	O(nlogn)	O(1)	不是
希尔排序	O(nlogn)	O(ns)	O(1)	不是
计数排序	O(n+k)	O(n+k)	O(n+k)	是
基数排序	O(N*M)	O(N*M)	O(M)	是

//归并排序
function mergeSort(arr) {
    if (arr.length === 1) return arr;
    const midIdx = Math.floor(arr.length / 2);
    return merge(mergeSort(arr.slice(0, midIdx)), mergeSort(arr.slice(midIdx)))
}

function merge(leftArr, rightArr) {
    let temp = [];
    while (leftArr.length > 0 && rightArr.length > 0) {
        if (leftArr[0] < rightArr[0]) {
            temp.push(leftArr.shift());
        } else {
            temp.push(rightArr.shift());
        }
    }
    return temp.concat(leftArr).concat(rightArr);
}

//快速排序

function quickSort(arr) {
    // 基线条件：小于或等于1个元素的数组是有序的
    if (arr.length <= 1) return arr;

    // 选择一个基准值，这里我们选择数组的中间值作为基准值
    let pivotIndex = Math.floor(arr.length / 2);
    let pivot = arr.splice(pivotIndex, 1)[0];

    // 定义两个子数组，一个用于存放比基准值小的元素，另一个用于存放比基准值大的元素
    let left = [];
    let right = [];

    // 遍历数组，将比基准值小的元素放入左边的子数组，比基准值大的元素放入右边的子数组
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] > pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }

    // 递归地对左右两个子数组进行快速排序，然后连接这两个子数组和基准值，得到排序后的数组
    return quickSort(left).concat([pivot], quickSort(right));
}

// 时间复杂度：平均情况下为O(n log n)，最坏情况下为O(n^2)，但在实际应用中表现良好。

console.log(quickSort([1,25,72,3,78,2,5,8,9,-2]))
快速排序的最坏情况发生在每次选择的基准值都是输入数组的最小值或最大值时。这会导致每次递归调用只能减少一个元素，从而使算法退化为O(n^2)的复杂度。

具体来说，以下是一些导致最坏情况的场景：

1. **已排序的数组**：如果输入数组已经是升序或降序，且我们每次选择第一个或最后一个元素作为基准值，那么快速排序将会退化为O(n^2)。

2. **含有许多重复值的数组**：如果数组包含许多重复的值，并且这些重复值经常被选为基准值，那么分区可能会非常不平衡。

为了避免这些最坏情况，通常有以下几种策略：

1. **随机选择基准值**：每次从数组中随机选择一个元素作为基准值，这样即使在面对已排序的数组时，平均情况下也能达到O(n log n)的性能。

2. **使用"三数取中"策略**：选择数组的第一个、中间和最后一个元素中的中值作为基准值。这可以减少对已排序输入或近似排序输入的不良性能。

3. **双基准快速排序**：这是快速排序的变种，它每次选择两个基准值并将数组分为三部分。这种方法在处理有大量重复值的数组时表现得更好。

总之，虽然快速排序在最坏情况下的性能不佳，但通过适当的策略，可以在大多数情况下获得很好的平均性能。

function quickSort(arr) {
    quickSort_c(arr, 0, arr.length - 1);
}

function quickSort_c(arr, p, r) {
    if (p >= r) return;
    let q = partition(arr, p, r);
    quickSort_c(arr, p, q - 1);
    quickSort_c(arr, q + 1, r);
}

function partition(arr, p, r) {
    let i = j = p;
    while (j < r) {
        if (arr[j] < arr[r]) {
            swap(arr, j, i);
            i++;
        }
        j++;
    }
    swap(arr, i, r)
    return i
}

function swap(arr, i, r) {
    let temp = arr[i];
    arr[i] = arr[r];
    arr[r] = temp;
}

//降序
function quickSortDesc(arr) {
    if (arr.length <= 1) {
        return arr;
    }

    const pivot = arr[Math.floor(arr.length / 2)];
    const less = [];
    const greater = [];

    for (let i = 0; i < arr.length; i++) {
        if (arr[i] > pivot) {
            less.push(arr[i]);
        } else if (arr[i] < pivot) {
            greater.push(arr[i]);
        }
    }

    return [...quickSortDesc(less), pivot, ...quickSortDesc(greater)];
}

// 示例用法
const array = [9, 4, 2, 7, 1, 5, 8, 3, 6];
const sortedArray = quickSortDesc(array);
console.log(sortedArray);

10.15 同一对象

function areDeeplyEqual(o1, o2) {
    if (Object.prototype.toString.call(o1) !== Object.prototype.toString.call(o2)) {
        return false;
    }
    if (o1 !== null && typeof o1 === 'object') {
        const keys1 = Object.keys(o1);
        const keys2 = Object.keys(o2);
        if (keys1.length !== keys2.length) return false;
        return keys1.every((k) => areDeeplyEqual(o1[k], o2[k]));
    }

    return o1 === o2;
}

10.16数组扁平化

// 1.递归
function flatDeep(arr){
	let result = [];
	for(let i = 0; i < arr.length; i++) {
		if(Array.isArray(arr[i])){
			result = result.concat(flatDeep(arr[i]))
		} else {
			result.push(arr[i])
		}
	}
	return result;
}
// 2.ES6
function flatDeep(arr) {
	return arr.flat(Infinity)
}
// 3.扩展运算符与some
function flatDeep(arr) {
	while(arr.some(item => Array.isArray(item))){
		arr = [].concat(...arr)
	}
	return arr;
}
// 4.reduce
function flatDeep(arr) {
	return arr.reduce((pre, next) => {
		return pre.concat(Array.isArray(next) ?  flatDeep(next) : next)
	},[])
}
// 5.toString
function flatDeep(arr){
	let result = [];
	return result = arr.toString().split(',').map(Number)
}
// 6.正则表达式
const res3 = JSON.parse('[' + JSON.stringify(arr).replace(/\[|\]/g, '') + ']');
// 传参
var flat = function (arr, n) {  
    if(n === 0) return arr;
    return arr.reduce((acc, item) => {
        if (Array.isArray(item)) {
            acc.push(...flat(item, n - 1))
        } else {
            acc.push(item)
        }
        return acc
    }, [])
    
};
var flat = function (arr, n) {
    while(arr.some(item=>Array.isArray(item))&&n>0){
        arr=[].concat(...arr)
        n--;
    }
    return arr;
};



var array = [1, [2, [3, [4, 5]]]];
console.log(flatDeep(array));

10.17 instance

function myInstanceof(L = null, R) {
    // 对于左侧参数如果是非对象直接返回false
    if (Object(L) !== L) return false
    // 对于右侧参数可以认为只能为函数且不能没有Prototype属性
    if (typeof R !== 'function' || !R.prototype) throw new TypeError('Right-hand side of 'instanceof' is not an object')
    // 声明一个变量获取对象的__proto__
    let link = L.__proto__
    // 做循环（当link最终指向null，如果指向null的情况下都找不到那就返回false）
    while (link !== null) {
        // 如果找到说明R.prototype在L的原型链上，即返回true
        if(link === R.prototype) return true
        // 逐级向下
        link = link.__proto__
    }
    return false
}

function myTypeof(params){
  const type = Object.prototype.toString.call(params).slice(8, -1).toLowerCase()
  const map = {
    'number': true,
    'string': true,
    'boolean': true,
    'undefined': true,
    'bigint': true,
    'symbol': true,
    'function': true
  }
  return map[type] ? type : 'object'

10.18 登录流程

1.前端校验

2.发送请求

3.路由跳转

useRouter.repalce(path)

4.拦截器

const httpInstance = axios.create(baseURL,timeout)
httpInstance.interceptors.request.use(config=>{
	if(token){config.header.Authorization = `Bearer ${token}`} //一次配置
	return config
},e)

httpInstance.interceptors.response.use(res=>{},e=>{
    e.reponse.status == 401
})

5.用户管理

Pinia或vuex集中管理

6.持久化

本地化保存Token

7.更改页面显示

v-if

8.配置退出

参考：

https://juejin.cn/post/7072771035312947207

10.19 比较版本号

function compareVersion(version1, version2) {
  const arr1 = version1.split('.')
  const arr2 = version2.split('.')
  const length1 = arr1.length
  const length2 = arr2.length
  const minlength = Math.min(length1, length2)
  let i = 0
  for (i ; i < minlength; i++) {
    let a = parseInt(arr1[i])
    let b = parseInt(arr2[i])
    if (a > b) {
      return 1
    } else if (a < b) {
      ret