笔记14常见js手写题(2)

常见js手写题2

PromiseAll、PromiseRace、走楼梯问题、repeat函数、最长回文子串、两数/三数和

PromiseAll

    //特点:等所有Promise执行成功，再resolve；一旦有一个失败回调第一个失败
    function PromiseAll(arr){ 
      return new Promise(){
      let index = 0,
          resArr = [];
      if(arr.length === 0){resolve resArr} //处理传入为空的情况
      function deal(index,item){
        resArr.push(item);
        index ++;
        if(index === arr.length){
          return resolve(resArr)
        }
      }
      for(let i =0;i < arr.length;i++){
      Promise.resolve(arr[i]).then(
        res=>{deal(i,res)},
        err=>{throw new Error(err+'err')} 
        )
      }    
    }
  }

PromiseRace

  //特点:返回最快的Promise,不管执行成功或失败
  function PromiseRace(arr){
    return new Promise((resolve,reject)=>{
      arr.forEach(item=>{
        item.then(resolve,reject)
      })
    })
  }

走棋盘问题

  //需求:输入楼梯阶数n，每次走一步或者两步，返回可能结果数
  

  //解法1：递归
  function Deal(n){
    if(n ===1 || n ===2){
      return n
    }
    return Deal(n-1)+Deal(n-2) 
  }
  //解法2：dp， 用以解决基数n较大使用递归导致的内存占用太多
  function Deal(n){
    if(n === 1 || n === 2){
      return n
    }
    let dp =[];
        dp[0]=1;
        dp[1]=2;   
    for(let i=2;i < n;i++){
      dp[i] = dp[i-1]+dp[i-2]
    }
    return dp[n-1]
  }

rePeat函数

  //需求：输入func、执行次数times、时延wait；返回一个函数每隔时延回调输入
  function rePeat(func,times,wait){
   return (...arg)=>{
     let self = this
     let timer = setInterval(()=>{
       if(times>0){
         fn.apply(self,arg)
         times --;
       } else {
         clearTimeOut(timer) 
       }
     },wait)
   }
  }

最长回文子串

  //需求：输入一个字符串，找出其中最长的回文子串
  

  //解法1：暴力法(略)两轮遍历获取所有子串可能性，判断是否回文，时间复杂度o(n^3)
  //解法2：动态规划
  function Deal(str){
    let max =0,
        result = '',
        dp=[];
    for(let n =0;n < str.length;n++){
      dp[n] = [];//构建二维数组dp
    }
    for(let k=0;k < str.length;k++){ //一轮遍历所有可能的子串始末下标差值k
      for(let i=0;i < str.length-k;i++){ //二轮遍历所有可能子串的起始下标i
        j=i+k; //得到子串末尾下标j
        if(k === 0){ //若差值为0，代表子串长度为1，一定回文
          dp【i】【j】 = true  
        } else if (k <=2){ 若差值为1或2，代表子串长度为2或3，当首位相同回文

          if(str[i] === str[j]){ 
            dp【i】【j】 = true
          }else{
            dp【i】【j】 = false               
          }
        } else { //差值大于2，子串长度大于3，回文条件：首尾相同且内部回文
          if(str[i] === str[j] && dp【i+1】【j-1】){
            dp【i】【j】 = true 
          } else {
            dp【i】【j】 = false
          }
        }
        if(dp【i】【j】 && k>max){
          max = k;
          result = str.slice(i,j+1);
        } 
      }
    }
    return result
  }

两数之和

  //需求：输入数组、目标和；返回和等于目标的两数下标
  

  function sumOfTwo(arr,target){
    let res=[]; //维护一个hash-map
    for(let i=0;i < arr.length;i++){
      if(res[arr[i]] === undefined){
        res[target - arr[i]] = i
      } else {
          return [res[arr[i]],i]
      }
    }
  }

三数之和

  //需求：输入数组；返回三数之和为0的数
  

  function sumOfThree(arr){
    arr=arr.sort((a,b)=>a-b) //对输入数组排序
    let res = [];
    for(let i=0;i < arr.length-2;i++){
      if(i>=1 && arr[i] === arr[i-1]){ //对第一位i去重
        continue; 
      }
      let j = i+1,
          k = arr.length-1;
      while(j < k){
        let sum = arr[i]+arr[j]+arr[k];//获取三数之和
        if(sum ===0){
          res.push(arr[i],arr[j],arr[k])
          j++;
          while(arr[j] === arr[j-1]){ //对第二位数j去重
            j++;
          }
        }
        else if(sum < 0){
          j++;
        }
        else if(sum > 0){
          k--;    
        }
      }    
    }
    return res;
  }