前端面试题《手写代码》

比眉伴天荒 2022-11-14 10:11 149阅读 0赞

### 二分查找 ###

非递归

function search(arr,key) {
             let min = 0
             let max = arr.length-1
             while (min<=max) {
               let  mid = parseInt((min+max)/2)
               if(arr[mid]==key){
                 return mid
               }else if(arr[mid]>key){
                 max = mid-1
               }else if(arr[mid]<key){
                 min = mid+1
               }else{
                 return -1
               }           
             }
           }

递归

function search(min,max,key,arr) {
             let mid = parseInt((min+max)/2)
             if(arr[mid]=key){
               returnn mid
             }else if(arr[mid]>key){
               max = mid-1
               search(min,max,key,arr)
             }else if(arr[mid]<key){
               min = mid+1
               search(min,max,key,arr)
             }else{
               return -1
             }
           }

**时间复杂度**

总共有n个元素，每次查找的区间大小就是n，n/2，n/4，…，n/2^k（接下来操作元素的剩余个数），其中k就是循环的次数。  
最差的情况就是 n/2^k=1, 即区间大小为1, 所以 k=log2n, 时间复杂度为 O(logn)

### call ###

Function.prototype.myCall = function(context) {
     context = context||window
     context.fn = this
     let args = [...arguments].splice(1)
     let result = context.fn(...args)
     delete context.fn
     return result 
    }

### apply ###

Function.prototype.myApply = function (context) {
      context = context||window
      context.fn = this
      let args = arguments[1]
      let result
      if(args){
        result = context.fn(..args)
      }else{
        result = context.fn()
      }
      delete context.fn
      return result
    }

### bind ###

Function.prototype.myBind = function (context) {
      if(typeof this!=='function'){
        return TypeError('error')
      }
      let _this = this
      let args = [...arguments].splice(1)
      return function F() {
        if(this instanceof F){
          return _this.apply(this,args.concat([...arguments]))
        }
        return _this.apply(context,args.concat([...arguments]))
      }
    }

### 扁平化数组（递归） ###

Array.prototype.flat2 =function(){
      let reslut=[]
      for(let i=0;i<this.length;i++){
          if(Array.isArray(this[i])){
              reslut=reslut.concat(this[i].flat2())
          }else{
              reslut.push(this[i])
          }
      } 
      return reslut
    }
    let arr=[1,[2,[3,[4],[5],[6]]]]
    arr.flat2()

### 扁平化数组（迭代） ###

function *flat(arr) {
           for (const item of arr) {
               if (Array.isArray(item)) {
                   yield *flat(item);
               } else {
                   yield item;
               }
           }
       }
       const result = [...flat([1,2,[3,[4]]])]
       console.log(result) //  [1, 2, 3, 4]

定义一个生成器函数：迭代当前数组，如果值也是数组则生成扁平化的值，否则直接生成值。然后在我们的扁平化函数里调用这个生成器函数得到我们的一维数组。

这里有两点需要注意：

1.  嵌套 yield 需要再加一个星号，这被称为生成器委托。
2.  不能使用 forEach 代替 for...of 但可以用 for 循环，因为 for 循环和for...of 可以中断迭代去执行 yield，forEach 不行

### 冒泡排序 ###

### 快速排序 ###

function quickSort(arr) {
      let len = arr.length
      let mid = Math.floor(len/2)
      let midValue = arr.splice(mid,1)[0]
      let leftArr=[]
      let rigthArr=[]
      for (let i = 0; i < len; i++) {
        if(arr[i]>midValue){
          rigthArr.push(arr[i])
        }else{
          leftArr.push(arr[i])
        }   
      }
      return quickSort(leftArr).concat([midValue,quickSort(rigthArr)])
    }

### 排序算法的时间复杂度 ###

![20170327164357916][]

### 数组去重 ###

let arr=[1,'1',1,2,3,4,4,5]
    [...new Set(arr)]
    //也可用Array.from(new Set(arr) 
    
    
    let newArr=[]
    for(let i=0,i>arr.lengeh,i++){
      if(newArr.indexOf(arr[i])==-1){
        newArr.push(arr[i]
    }

### 柯里化函数 ###

function currying(fn) {
      let args_arr = []
      max_length = fn.length
      let closure = function (...args) {
        // 先把参数加进去
        args_arr = args_arr.concat(args)
        // 如果参数没满，返回闭包等待下一次调用
        if (args_arr.length < max_length) return closure
        // 传递完成，执行
        return fn(...args_arr)
      }
      return closure
    }
    function add(x, y, z) {
      return x + y + z
    }
    curriedAdd = currying(add)
    console.log(curriedAdd(1, 2)(3))

### 防抖 ###

### 节流 ###

### promise.all ###

Promise.all= function (promiseList) {
        return new Promise((resolve,reject)=>{  // 返回一个promise实例
          if(!Array.isArray(promiseList)){  // 判断参数是否是数组
            return reject(new TypeError('error'))
          }
           // 数组为空，直接resolve
           if (promiseList.length == 0) {
             resolve(promiseList);
          }
          let cont=0 // 用于计数，当等于cont=len时就resolve
          let len=promiseList.length
          let values=new Array(len) //创建一个和传入数组长度相同的数组，用于存放结果
          for (let i = 0; i < len; i++) {
           Promise.resolve(promiseList[i]) //如果元素不是 Promise 对象，则使用 Promise.resolve 转成 Promise 对象
           .then((res)=>{
              cont++  //每次成功后+1
              values[i]=res //将成功后的值放入数组
              if(cont===len){ // 数据接收完成
                resolve(values) 
              }
           })
           .catch(err=>{ //只要有一个失败，抛出异常，状态变为 rejected
             reject(err)
           })
            
          }
        })
      }

### **Promise.race** ###

Promise.race=function(promiseList){
     return new Promise((resolve,reject)=>{
       if(!Array.isArray(promiseList)){
         return reject (new TypeError('error'))
       }
       promiseList.forEach(item => {
         Promise.resolve(item)
         .then(res=>{
            resolve(res)
         })
         .catch(err=>{
            reject(err)
         })
       });
     }) 
    }

### 简单promise ###

### promise实现，红色三秒打印一次、绿色两秒打印一次、黄色一秒打印一次 ###

### 简单数据劫持 ###

### 简单发布订阅 ###

class subject{
        observerList = []
        addObservers(obs){
            this.observerList.push( obs )
        }
        removeObservers(obs){
            let index = this.observerList.indexOf( obs )
                if( index > -1 ){
                    arr.splice( index , 1)
                }
        }
        notify(){
            this.observerList.forEach(item => item.update())
        }
     }
     class observer{
         update(){
         }
         subscribeTo(obj){
             obj.addObservers(this)
         }
     }

发布者核心功能: 增加/删除订阅者 ,通知订阅者更新

观察者核心功能: 在发布者通知更新后,及时更新,绑定订阅者

### 简单深拷贝，递归 ###

// 定义一个深拷贝函数  接收目标target参数
    function deepClone(target) {
        // 定义一个变量
        let result;
        // 如果当前需要深拷贝的是一个对象的话
        if (typeof target === 'object') {
        // 如果是一个数组的话
            if (Array.isArray(target)) {
                result = []; // 将result赋值为一个数组，并且执行遍历
                for (let i in target) {
                    // 递归克隆数组中的每一项
                    result.push(deepClone(target[i]))
                }
             // 判断如果当前的值是null的话；直接赋值为null
            } else if(target===null) {
                result = null;
             // 判断如果当前的值是一个RegExp对象的话，直接赋值    
            } else if(target.constructor===RegExp){
                result = target;
            }else {
             // 否则是普通对象，直接for in循环，递归赋值对象的所有值
                result = {};
                for (let i in target) {
                    result[i] = deepClone(target[i]);
                }
            }
         // 如果不是对象的话，就是基本数据类型，那么直接赋值
        } else {
            result = target;
        }
         // 返回最终结果
        return result;
    }

### 考虑循环引用、symbol类型的深拷贝 ###

需要解决拷贝对象内的循环引用问题（使用数组记录拷贝过的对象，记录一个拷贝对象的数据结构，\{source:原拷贝对象，target:拷贝后的对象\}）

//存放已拷贝的对象用于循环引用检测
    let objArr = [];
     
    function deepCopy(obj) {
      //判断循环引用检测
      for (let ele of objArr) {
        if (obj === ele.source) {
          return ele.target;
        }
      }
      //拷贝容器
      let newObj = {};
     
      //将拷贝的对象放入数组中用于循环引用检测
      objArr.push({
        source: obj, //被拷贝对象上的原引用对象，用于循环检测比对
        target: newObj
      })
     
      //使用Reflect可以检测到Symbol类型的属性
      Reflect.ownKeys(obj).forEach(key => {
        if (obj.hasOwnProperty(key)) {
          if (typeof obj[key] === 'object') {
            //使用Array.from对拷贝的数组进行处理
            newObj[key] = Object.prototype.toString.call(obj[key]) === '[object Array]' ? Array.from(deepCopy(obj[key], key)) : deepCopy(obj[key], key);
          } else {
            //属性值为原始类型的值
            newObj[key] = obj[key];
          }
        }
      })
      return newObj;
    }

### 考虑递归爆栈的深拷贝，迭代 ###

### 给ul下的所有li绑定点击事件，弹出下标和内容 ###

### 杨辉三角 ###

### 实现接口失败重新请求，并限制并发请求Retry ###

retry = function(fn, times, delay) {
      var err = null;
      return new Promise(function(resolve, reject) {
     
        var attempt = function() {
          fn().then(resolve).catch(function(err) {
            console.log(`Attempt #${times} failed`);
            if (0 == times) {
              reject(err);
            } else {
              times--;
              setTimeout(function(){
                attempt()
              }, delay);
            }
          });
        }; 
        attempt(); 
      });
    };

### **instanceof** ###

function instanceOf(left, right) {
        let leftValue = left.__proto__;
        let rightValue = right.prototype;
        while(leftValue ){ 
            if(leftValue === rightValue ){
            return true
            }else{
              leftValue = leftValue.__proto__
            }         
       }
       return false   
    }

### 闭包解决settimeout打印同一个值的问题 ###

for (var i = 0; i < 5; i++) {
      (function (i) {
          setTimeout(function() {
         console.log(i);
      }, 1000);
      })(i)
    }

### 交集、并集、补集、差集 ###

//交集
    var c = a.filter(function(v){ return b.indexOf(v) > -1 })
    //差集
    var d = a.filter(function(v){ return b.indexOf(v) == -1 })
    //补集
    var e = a.filter(function(v){ return !(b.indexOf(v) > -1) })
     .concat(b.filter(function(v){ return !(a.indexOf(v) > -1)}))
    //并集
    var f = a.concat(b.filter(function(v){ return !(a.indexOf(v) > -1)}));

[20170327164357916]: /images/20221022/0613c909b4164bd5bfcc6e8dc985fd38.png