一些编程/算法题练习

温馨提示

以下纯属自我练习，可能不是最优解，甚至可能存在一些问题

写一个 mySetInterVal(fn, a, b),每次间隔 a,a+b,a+2b 的时间，然后写一个 myClear，停止上面的 mySetInterVal

function mySetInterVal(fn, a, b) {
  let index = 0;
  let timmer;
  const loop = () => {
    timmer = setTimeout( ()=> {
      fn();
      index++;
      loop();
    }, a + index*b );
  };
  loop();
  return () => {
    clearTimeout(timmer);
  }
}
let testMyInt = mySetInterVal( () => { console.log('acc')}, 1000, 2000);

斐波那契额数列

// 斐波那契额数列的公式表示
F(0) = 0;
F(1) = 1;
F(n) = F(n - 1) + F(n - 2);

// 递归实现
function fib(n) {
  if(n < 0) throw new Error('输入的数字不能小于0');
  if (n < 2) {
    return n;
  }
  return fib(n - 1) + fib(n - 2);
}

字符串出现的不重复最长长度

function lengthOfLongestSubstring(str) {
  let result = '';
  const strArr = str.split('');
  for(let index = 0; index < str.length -1 ; index ++) {
    let temp = strArr [index];
    for(let cursor = index + 1 ; cursor < str.length; cursor++ ) {
      if (temp.indexOf(strArr[cursor]) > -1 ) {
        break;
      } else {
        temp += strArr[cursor]
      }
    }
    if (temp.length > result.length ) {
      result = temp;
    }
  }
  return result;
}
lengthOfLongestSubstring("adfafwefffdasdcx");

lodash._get 实现

function get(source, path, defaultValue = undefined) {
  // a[3].b -> a.3.b -> [a,3,b]
 // path 中也可能是数组的路径，全部转化成 . 运算符并组成数组
  const paths = path.replace(/\[(\d+)\]/g, ".$1").split(".");
  let result = source;
  for (const p of paths) {
    // 注意 null 与 undefined 取属性会报错，所以使用 Object 包装一下。
    result = Object(result)[p];
    if (result == undefined) {
      return defaultValue;
    }
  }
  return result;
}
// 测试用例
console.log(get({ a: null }, "a.b.c", 3)); // output: 3
console.log(get({ a: undefined }, "a", 3)); // output: 3
console.log(get({ a: null }, "a", 3)); // output: 3
console.log(get({ a: [{ b: 1 }] }, "a[0].b", 3)); // output: 1

// 不考虑数组的情况

const _get = (object, keys, val) => {
  return keys.split(/\./).reduce(
   (o, j)=>( (o || {})[j] ), 
   object
  ) || val
 }
 console.log(get({ a: null }, "a.b.c", 3)); // output: 3
 console.log(get({ a: undefined }, "a", 3)); // output: 3
 console.log(get({ a: null }, "a", 3)); // output: 3
 console.log(get({ a: { b: 1 } }, "a.b", 3)); // output: 1

实现 add(1)(2)(3)

 function add (a) {
   return (b) => {
     return (c) => {
       return a + b + c
     }
   }
 }
 add(1)(2)(3)

 // 扩展 ：多参数
 function addMore (...a) {
  let arr = a
  return (...b) => {
    arr = arr.concat(b)
    return (...c) => {
      arr = arr.concat(c)
      return arr.reduce((i,j) => i+j)
    }
  }
}
addMore(1)(2,3)(4,5)

Promiss实现

// 参数：一个含有异步操作的功能函数。
// 状态管理： Promiss是有三个状态的
// 三要素： resolve，reject，then，
// 链式调用： return this
// 串行
const PENDING = 'pending'
const FULFILLED = 'fulfilled'
const REJECTED = 'rejected'

function MyPromise(execute){

  let state = PENDING,
      resHandlers = [],
      rejHandlers = [],
      value = null,
      reason = ''

  function resolve(val) {
    value = val;
    state = FULFILLED;
    setTimeout(() => {
      resHandlers.forEach((headler) => {
        headler(val);
      })
    }, 0);
  }

  function reject( err ) {
    reason = err || '';
    state = REJECTED;
    setTimeout(() => {
      rejHandlers.forEach((headler) => {
        headler(reason);
      })
    }, 0);
  }

  this.then = ( onFulfilled, onRejected ) => {
    if (state === FULFILLED) {
      typeof onFulfilled === 'function' && onFulfilled(value)
    } else if (this.state === REJECTED) {
      typeof onRejected === 'function' && onRejected(reason)
    } else {
      typeof onFulfilled === 'function' && resHandlers.push(onFulfilled)
      typeof onRejected === 'function' && rejHandlers.push(onRejected)
    } 
    return this;
  }

  execute ( resolve, reject );
}

new MyPromise((resolve) => {
  setTimeout(()=>  {
    resolve('1')
  },3000)
}).then((res)=> {
  console.log("1",res);
}).then((res)=> {
  console.log("2",res);
})

MyPromise.prototype.all = (promisess) => {
  return new MyPromise(( resolve, reject ) => {
    let resultErr = [],
        count = 0;

    promisess.forEach((promise,i) => {
      promise.then((res) => {
        resultErr[i] = res;
        if ( ++count === promisess.length ) {
          resolve(resultErr)
        }
      }, (reason) => {
        reject(reason)
      })
    })
  })
}

手写 发布订阅 （观察者模式）

function MyEventEmiter () {
  let eList = [],
      index = 0

  this.on = (eName, headler) => {
    eName && typeof headler === 'function' && eList.push({ index, eName, headler })
    index ++;
    return this;
  }

  this.off = (_index) => {
    for(var i = 0; i < eList.length ; i++) {
      if (eList[i].index === _index) {
        eList.splice(i,1);
        break;
      }
    }
  }

  this.once = (eName, headler) => {
    const _index = index;
    const _this = this;
    eName && typeof headler === 'function' && 
    eList.push({
      index, 
      eName, 
      headler: (data) => { 
        headler(data);
        _this.off(_index);
      }
    })
    index ++;
    return this;
  }

  this.emit = (eName, data) => {
    eList.forEach((event) => {
      event.eName === eName && event.headler(data);
    })
  }
}

var myEvent = new MyEventEmiter();
myEvent.once('click', (data) => {
  console.log('do click only once', data)
}).on('click', (data) => {
  console.log('do click', data)
})
setTimeout(() => { myEvent.emit('click','first'); },100 )
setTimeout(() => { myEvent.emit('click','second'); },100 )
setTimeout(() => { myEvent.emit('click','third'); },100 )

数组转树

function arrToTree (arrDate) {
  arrDate.forEach((item1) => {
    item1.children = arrDate.filter((item2)=>{ return item2.parentId === item1.id})
  })
  const result = arrDate.filter((a) => { return !a.parentId })
  console.log(arrDate)
  return result
}
// 网友++转对象，只需遍历一次。
function convert(list) {
  const map = list.reduce((acc, item) => {
    acc[item.id] = item
    return acc
  }, {})
  const result = []
  for (const key in map) {
    const item = map[key]
    if (item.parentId === 0) {
      result.push(item)
    } else {
      const parent = map[item.parentId]
      if (parent) {
        parent.children = parent.children || []
        parent.children.push(item)
      }
    }
  }
  return result
}

arrToTree([
  {id:1, parentId: null, name: 'a'},
  {id:2, parentId: null, name: 'b'},
  {id:3, parentId: 1, name: 'c'},
  {id:4, parentId: 2, name: 'd'},
  {id:5, parentId: 1, name: 'e'},
  {id:6, parentId: 3, name: 'f'},
  {id:7, parentId: 4, name: 'g'},
  {id:8, parentId: 7, name: 'h'},
]);

/*有10个篮子，分别装有1，2，4，8，16，32，64，128，256，512 个苹果，篮子编号为 0 ~ 9，请问如果正好想取 825 个苹果， 需要的篮子编号为多少？例如取 5 个苹果，需要 0，2 号篮子（1 + 4 个）。*/

function getAppleBoxIndex(arr,num) {
  const len = arr.length
  let res = [];
  let cur = 0;
  for(let i = len -1; i > -1 ; i--) {
    if (cur + arr[i] === num) {
      res.push(i);
      break;
    } else if (cur + arr[i] < num) {
      cur += arr[i];
      res.push(i);
    }
  }
  return res;
}

getAppleBoxIndex([1,2,4,8,16,32,64,128,256,512],825)

Promise 串行

/**
 * 多个Promise 链式依次执行  
 * 后面promise依赖前面返回的数据
*/

function myCompose(...args){
  let prmLink = Promise.resolve();
  args.forEach((prm) => {
    prmLink = prmLink.then(prm);
  })
  return prmLink
}

let promA = function() { console.log('promA:acc'); return Promise.resolve(1) };
let promB = function(val) { console.log('promB:acc', val); return Promise.resolve(++val) };
let promC = function(val) { console.log('promC:acc', val); return Promise.resolve(++val) };
let promD = function(val) { console.log('promD:acc', val); return Promise.resolve(++val)  };

myCompose(promA,promB,promC,promD).then((val) => {console.log('finally result:', val);});

// promA:acc
// promB:acc 1
// promC:acc 2
// promD:acc 3
// inally result: 4
// Promise {<fulfilled>: undefined}

控制promise并行数量

/**
 * 控制多个 Promise 异步fetch 同时只能并行执行 limit 个任务
*/
function doFetchList(list, limit) {
  const len = list.length;
  let result = [];
  let count = 0;
  return new Promise((resolve, reject)=>{
    while(current < limit) {
      next();
    }
    function next() {
      let current = count++;
      if (current > len) {
        resolve(result);
      }
      fetch(list[current]).then((res) => {
        result[current] = res;
        if (current < len) next();
      },(err) => {
        result[current] = err;
        if (current < len) next();
      })
    }
  }) 
}

异步请求失败重试

function promiseRetry(asyncFn, maxCount) {
    let currentCount = maxCount;
    return new Promise((resolve,reject) => {
      function run () {
        asyncFn().then((res) => {
          resolve(res);
        },(reason) => {
          if (--currentCount) {
            run();
          } else {
            reject(reason)
          }
        })
      }
      run();
    })
}

//测试用例:
function fn() {
  return new Promise((resolve,reject) => {
    console.log('running:', new Date());
    setTimeout(()=> {
      reject('err')
    },1000)
  })
}

promiseRetry(fn,3).then(() => {
  console.log('success');
},(reason) => {
  console.log('err:' + reason);
})

使用闭包实现每隔 1 秒打印 1-500

// 不用promise
function printNum(maxNum) {
  let i = 1
  while(i <= maxNum) {
    ((num) => {
      setTimeout(() => {
        console.log(num);
      }, 1000 * num)
    })(i++)
  }
}
printNum(500);

// v2：
function printNum(maxNum) {
  for(let i = 1; i <= maxNum; ++i) {
    ((i) => {
      setTimeout(() => {
        console.log(i);
      }, 1000 * i)
    })(i)
  }
}
printNum(500);


//使用promise

var sleep = function (time, i) {
  return new Promise(function (resolve, reject) {
    setTimeout(function () {
      resolve(i);
    }, time);
  })
};


var start = async function () {
  for (let i = 0; i < 6; i++) {
    let result = await sleep(1000, i);
    console.log(result);
  }
};
start();

返回一个字符串中出现次数最多的字符。

function getMaxlen(str) {
  if (!str) return '';
  const len = str.length;
  if (len <= 1) return str;
  let strMap = new Map();
  let maxSize = 0;
  let result = [];
  for (let i = 0; i < len; i++) {
    if (strMap.has(str[i])) {
      strMap.set(str[i], strMap.get(str[i]) + 1);
      maxSize = Math.max(maxSize, strMap.get(str[i]) )
    } else {
      strMap.set(str[i],1);
    }
  }
  strMap.forEach((value,key) => {
    if (value === maxSize) {
      result.push(key)
    }
  })
  return result;

}

getMaxlen('abcdccbdb58575') // ["b", "c", "5"]