面试手撕代码合集

2023-01-05

Word count: 8.9k | Reading time≈ 49 min

面试手撕代码合集

面试手撕代码合集

1.柯里化函数

function add() {
    const _args = [...arguments];
    function fn() {
      _args.push(...arguments);
      return fn; //一直重复收集参数
    }
    fn.toString = function() {
      return _args.reduce((sum, cur) => sum + cur);
    }
    return fn;
  }
console.log(add(1)(2)(3)(4).toString()) //10
console.log(add(1,2)(1, 2, 3)(2).toString()) //11

2.千位符转换

// 将金额类型转为数字类型
function toNum(str) {
    return str.replace(/\,|\￥/g, "");
}

// 保留两位小数（四舍五入）
function toPrice(num) {
    num = parseFloat(toNum(num)).toFixed(2).toString().split(".");
    num[0] = num[0].replace(new RegExp('(\\d)(?=(\\d{3})+$)','ig'),"$1,");
    return "￥" + num.join(".");
}

// 保留两位小数（不四舍五入）
function toPrice1(num) {
    num = parseFloat(toNum(num).replace(/(\.\d{2})\d+$/,"$1")).toFixed(2).toString().split(".");
    num[0] = num[0].replace(new RegExp('(\\d)(?=(\\d{3})+$)','ig'),"$1,");
    return "￥" + num.join(".");;
}

// 不处理小数部分
function toPrice2(num) {
    var source = toNum(num).split(".");
    source[0] = source[0].replace(new RegExp('(\\d)(?=(\\d{3})+$)','ig'),"$1,");
    return "￥" + source.join(".")
}

console.log(toPrice('12312.236')) //￥12,312.24
console.log(toPrice1('12312.234')) //￥12,312.23
console.log(toPrice2('1232342312.234')) //￥1,232,342,312.234

3.用setTimeout实现setInterval(计数器)

var i = 10;
let fn = () => {
    console.log(i--);
}
function mySetInterval(fn, delay, times) {
    let timer = setTimeout(function a() {
        fn()
        times--
        timer = setTimeout(a, delay)
        if (times <= 0) {
            clearTimeout(timer)
        }
    }, delay)
}
mySetInterval(fn, 1000, 10)

4.数组扁平化

//递归实现
var arr = [1,2,[3,4,[5,6]]]
function flatten(arr){
    let result = []
    arr.forEach(item => {
        if(Array.isArray(item)){
            result = result.concat(flatten(item))
        }else{
            result.push(item)
        }
    });
    return result
}
console.log(flatten(arr)) //[ 1, 2, 3, 4, 5, 6 ]

//利用reduce函数迭代
var arr1 = [1,2,[3,4,[5,6]]]
function flatten1(arr){
    return arr.reduce((res,next) => {
        return res.concat(Array.isArray(next) ? flatten1(next) : next)
    },[])
}
console.log(flatten1(arr1)) //[ 1, 2, 3, 4, 5, 6 ]

5.深拷贝

function deepClone(obj,hash = new WeakMap()){
    if(obj == null) return obj;
    if(obj instanceof Date) return new Date(obj);
    if(obj instanceof RegExp) return new RegExp(obj);
    if(typeof obj !== 'object') return obj;
    if(hash.get(obj)) return hash.get(obj);
    let cloneObj = new obj.constructor;
    hash.set(obj,cloneObj);
    for(let key in obj){
        if(obj.hasOwnProperty(key)){
            cloneObj[key] = deepClone(obj[key],hash);
        }
    }
    return cloneObj;
}

let obj = {name:1,address:{x:1000}};
let d = deepClone(obj);
obj.address.x = 200;
console.log(d); //{name:1,address:{x:1000}}

6.Promise.all

Promise.prototype.all = function(promises){
    let results = [];
    let promiseCount = 0;
    let promisesLength = promises.length;
    return new Promise(function(resolve,reject){
        for(let val of promises){
            Promise.resolve(val).then(function(res){
                promiseCount++;
                //results.push(res)
                results[i] = res;
                //当所有函数都正确执行了，resolve输出所有返回结果
                if(promiseCount === promisesLength){
                    return resolve(results);
                }
            },function(err){
                return reject(err);
            })
        }
    })
}

//测试
let promise1 = new Promise(function(resolve) {
    resolve(1);
  });
  let promise2 = new Promise(function(resolve) {
    resolve(2);
  });
  let promise3 = new Promise(function(resolve) {
    resolve(3);
  });
  
  let promiseAll = Promise.all([promise1, promise2, promise3]);
  promiseAll.then(function(res) {
    console.log(res);
  });//[1,2,3]

7.Promise.race

Promise.race = function(promises){
    //将可迭代对象转换为数组
    promises = Array.from(promises);
    return new Promise((resolve,reject)=>{
        if(promises.length === 0){
            //空的可迭代对象，用于pending状态
        }else{
            for(let i = 0;i < promises.length;i++){
                Promise.resolve(promises[i]).then((data)=>{
                    resolve(data);
                }).catch((reason)=>{
                    reject(reason)
                })
            }
        }
    })
}

//测试
let p1 = new Promise(function(resolve,reject){
    setTimeout(function(){
     resolve('success')
    },1000)
})
let p2 = new Promise(function(resolve,reject){
    setTimeout(function(){
     resolve('faild')
    },500)
})

Promise.race([p1,p2]).then(result=>{
console.log(result)  //  faild    faild耗时短
})

8.instanceof

function new_instance_of(leftValue,rightValue){
    let rightProto = rightValue.prototype;//取右边表达式的 prototype 值
    leftValue = leftValue.__proto__;//取左表达式的 __proto__ 值
    while(true){
        if(leftValue == null){
            return false;
        }
        if(leftValue === rightProto){
            return true;
        }
        leftValue = leftValue.__proto__;
    }
}
function Foo(){}
console.log(new_instance_of(Foo,Object))//true

9.js继承

1.原型链继承

 // 原型链继承
  function Super(){
    this.color=['red','yellow','black']
  }

  function Sub(){
  }
  //继承了color属性 Sub.prototype.color=['red','yellow','black']
  Sub.prototype=new Super()

  //创建实例 instance1.__proto__.color
  const instance1=new Sub()
  const instance2=new Sub()
  console.log(instance1.__proto__.color===instance2.__proto__.color) //true

2.构造函数继承

function Super(name,age){
    this.name = name;
    this.age = age;
    this.color = ['red','yellow','blue'];
    this.sayHi = function(){
        console.log('hi')
    }
    console.log(this)
}
function Sub(){
    //改变this指向
    Super.apply(this,arguments)
    this.height = 180;
}

var instance1 = new Sub('mengfeng',25);
var instance2 = new Sub('mengfeng123',24);
instance1.sayHi();//hi

3.实例继承

new

4.拷贝继承

//深拷贝

5.组合继承

function Super(name,age){
    this.name = name;
    this.age = age;
    this.color = ['red','yellow','blue']
}

Super.prototype.sayHi = function(){
    console.log('hi')
}

function Sub(name,age,height){
    Super.apply(this,arguments)
    this.height = height;
}

Sub.prototype = new Super('w',22);
Sub.prototype.constructor = Sub;
console.log(Sub.prototype)
Sub.prototype.sayHello = function(){
    console.log('hello')
}

var instance1 = new Sub('mengfeng',23,180);
var instance2 = new Sub('mengfeng123',24,181);
console.log(instance1)

6.寄生组合继承

function inheritPrototype(Sub,Super){
    var subPrototype=Object.create(Super.prototype)
    subPrototype.constructor=Sub
    Sub.prototype=subPrototype
    
  }
  function Super(name){
    this.name=name
  }
  Super.prototype.sayHi=function(){
    console.log(this.name)//ccdida
  }
  function Sub(name){
    Super.call(this,name)
  }
  inheritPrototype(Sub,Super)

  Sub.prototype.sayHello=function(){
    console.log('sayHello')
  }

  var instance1=new Sub('ccdida')
  console.log(instance1.__proto__)
  console.log(instance1.__proto__.__proto__)

10.对象扁平化

//对象扁平化
function flat(obj, key = "", res = {}, isArray = false) { 
    for (let [k, v] of Object.entries(obj)) { 
      if (Array.isArray(v)) { 
        let tmp = isArray ? key + "[" + k + "]" : key + k 
        flat(v, tmp, res, true) 
      } else if (typeof v === "object") { 
        let tmp = isArray ? key + "[" + k + "]." : key + k + "." 
        flat(v, tmp, res) 
      } else { 
        let tmp = isArray ? key + "[" + k + "]" : key + k 
        res[tmp] = v 
      } 
    } 
    return res 
  }
  
  var entryObj = {
    a: {
        b: {
            c: {
                dd: 'abcdd'
            }
        },
        d: {
            xx: 'adxx'
        },
        e: 'ae'
    }
}

console.log(flat(entryObj))

11.发布订阅

class EventEmitter{
    constructor(){
        this._events = {};
    }

    on(eventName, callback){
        if(this._events[eventName]){
            if(this.eventName !== "newListener"){
                this.emit("newListener", eventName)
            }
        }
        const callbacks = this._events[eventName] || [];
        callbacks.push(callback);
        this._events[eventName] = callbacks
    }

    emit(eventName, ...args){
        const callbacks = this._events[eventName] || [];
        callbacks.forEach(cb => cb(...args))
    }

    once(eventName, callback){
        const one = (...args)=>{
            callback(...args)
            this.off(eventName, one)
        }
        one.initialCallback = callback;
        this.on(eventName, one)
    }

     off(eventName, callback){
        const callbacks = this._events[eventName] || []
        const newCallbacks = callbacks.filter(fn => fn != callback && fn.initialCallback != callback /* 用于once的取消订阅 */)
        this._events[eventName] = newCallbacks;
    }
}



const events = new EventEmitter()

events.on("newListener", function(eventName){
    console.log(`eventName`, eventName)
})

events.on("hello", function(){
    console.log("hello");
})

let cb = function(){
    console.log('cb');
}
events.on("hello", cb)

events.off("hello", cb)

function once(){
    console.log("once");
}
events.once("hello", once)

events.off("hello", once)
events.emit("hello")
events.emit("hello")

12.反柯里化函数

Function.prototype.uncurrying = function() {
    var self = this;   //self为Array.prototype.push
    return function() {
        //obj = {0:1, length: 1}, arguments = [2, callee: ƒ, Symbol(Symbol.iterator): ƒ]
        var obj = Array.prototype.shift.call(arguments); 
        
        //Array.ptototype.push(obj, 2)
        return self.apply(obj, arguments);
    }
}
var testObj = {
    length: 1,
    0: 1
}
var push = Array.prototype.push.uncurrying();
push(testObj, 2);
console.log(testObj);   //{0: 1, 1: 2, length: 2}

13.防抖

//scroll方法中的do somthing至少间隔500毫秒执行一次
window.addEventListener('scroll',function(){
    var timer;//使用闭包，缓存变量
    return function(){
    if(timer) clearTimeout(timer);
    timer = setTimeout(function(){
    console.log('do somthing')
},500)
}
}());//此处()作用 - 立即调用return后面函数，形成闭包

14.监测数组变化

// 获取Array的原型，并创建一个新的对象指向这个原型
const arrayMethods = Object.create(Array.prototype)
// 创建一个新的原型，这就是改造之后的数组原型
const ArrayProto = []
// 重新构建Array原型里面的虽有方法
Object.getOwnPropertyNames(Array.prototype).forEach(method => {
    if(typeof arrayMethods[method] === "function"){
        ArrayProto[method] = function(){
            console.log("我已经监听到数组触发了"+method+"事件")
            return arrayMethods[method].apply(this, arguments)
        }
    }else{
        ArrayProto[method] = arrayMethods[method]
    }
})


let list = [1, 2, 3]
// 将数组的原型链指向新构造的原型
list.__proto__ = ArrayProto
// 执行push事件
list.push(2)
// 输出：
我已经监听到数组触发了push事件 // 这个说明监听成功了

15.节流

//scroll方法中当间隔时间大于2s，do somthing执行一次
window.addEventListener('scroll',function(){
    var timer ;//使用闭包，缓存变量
    var startTime = new Date();
    return function(){
    var curTime = new Date();
    if(curTime - startTime >= 2000){
    timer = setTimeout(function(){
    console.log('do somthing')
    },500);
    startTime = curTime;
    }
      } }());//此处()作用 - 立即调用return后面函数，形成闭包

16.拦截全局Promise-reject

// 使用Try catch 只能拦截try语句块里面的
try {
    new Promise((resolve, reject) => {
      reject("WTF 123");
    });
  } catch (e) {
    console.log("e", e);
    throw e;
  }
  
  // 使用 unhandledrejection 来拦截全局错误  （这个是对的）
  window.addEventListener("unhandledrejection", (event) => {
    event && event.preventDefault();
    console.log("event", event);
  });

17.千位符

// 将金额类型转为数字类型
function toNum(str) {
    return str.replace(/\,|\￥/g, "");
}

// 保留两位小数（四舍五入）
function toPrice(num) {
    num = parseFloat(toNum(num)).toFixed(2).toString().split(".");
    num[0] = num[0].replace(new RegExp('(\\d)(?=(\\d{3})+$)','ig'),"$1,");
    return "￥" + num.join(".");
}

// 保留两位小数（不四舍五入）
function toPrice1(num) {
    num = parseFloat(toNum(num).replace(/(\.\d{2})\d+$/,"$1")).toFixed(2).toString().split(".");
    num[0] = num[0].replace(new RegExp('(\\d)(?=(\\d{3})+$)','ig'),"$1,");
    return "￥" + num.join(".");;
}

// 不处理小数部分
function toPrice2(num) {
    var source = toNum(num).split(".");
    source[0] = source[0].replace(new RegExp('(\\d)(?=(\\d{3})+$)','ig'),"$1,");
    return "￥" + source.join(".")
}

console.log(toPrice('12312.236')) //￥12,312.24
console.log(toPrice1('12312.234')) //￥12,312.23
console.log(toPrice2('1232342312.234')) //￥1,232,342,312.234

18.浅拷贝

let Sclone =(obj)=>{        
    // 方法一        
    // let obj1 = {}        
    // obj1 = Object.assign({},obj)        
    // 方法二 
    let obj1 ={...obj}       
    return obj1    
}

19.数组去重

let arr =  [1,2,2,4,null,null,'3','abc',3,5,4,1,2,2,4,null,null,'3','abc',3,5,4] 

//利用key的唯一
let obj = {};
for (let i = 0; i < arr.length; i++) {
  let item = arr[i]
  if (obj[item] !== undefined) {
    arr.splice(i, 1);
    i--; // 解决删除元素后，数组塌陷问题
    continue;
  }
  obj[item] = item
}

console.log(arr)
// arr: [1, 2, 4, null, "3", "abc", 3, 5]


// 交换元素位置从而替换调 splice方法
let obj1 = {};
for (let i = 0; i < arr.length; i++) {
  let item = arr[i]
  if (obj1[item] !== undefined) {
    arr[i] = arr[arr.length-1]
    arr.length--;
    i--; 
    continue;
  }
  obj1[item] = item
}
// arr: [1, 2, 4, null, "3", "abc", 3, 5]


// Array.filter + Array.indexO
let newArr = arr.filter((item, index) => arr.indexOf(item) === index);  
// [1, 2, 4, null, "3", "abc", 3, 5


// Array.filter + Object.hasOwnProperty
let obj2 = {}
arr.filter(item => obj2.hasOwnProperty(typeof item + item) ? false : (obj2[typeof item + item] = true))


// Array.reduce + Array.includes
let newArr1 = arr.reduce((accu, cur) => {
    return accu.includes(cur) ? accu : accu.concat(cur);  // 1. 拼接方法
    // return accu.includes(cur) ? accu : [...accu, cur]; // 2. 扩展运算
}, [])


// Array.indexOf
let newArr2 = []
for (var i = 0; i < arr.length; i++) {
    if (newArr2.indexOf(arr[i]) === -1) newArr2.push(arr[i])  
}
//等同于 forEach 写法
arr.forEach( item => newArr2.indexOf(item) === -1 ? newArr2.push(item) : '')

//Array.includes
let newArr3 = []
for (var i = 0; i < arr.length; i++) {
    if (!newArr3.includes(arr[i]))  newArr3.push(arr[i])
}
//等同于 forEach 写法
arr.forEach( item => !newArr3.includes(item) ? newArr3.push(item) : '')


// new Set + 扩展运算符 || Array.from
let newArr5 = [...new Set(arr)];      // [1, 2, 4, null, "3", "abc", 3, 5]
let newArr4 = Array.from(new Set(arr));      // [1, 2, 4, null, "3", "abc", 3, 5]
let newStr = [...new Set('ababbc')].join('')  //  'abc'


// new Map
let map = new Map();
let newStr6 = [];

for (let i = 0; i < arr.length; i++) {
    if (!map.has(arr[i])) {
        map.set(arr[i], true);
        newStr6.push(arr[i]);
    }
}
console.log(newArr6)  // [1, 2, 4, null, "3", "abc", 3, 5]

20.数组转为tree

let arr= [
    { id: 1, name: '部门A', 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 },
    { id: 18, name: '部门K', parentId: 4 },
    { id: 22, name: '部门zz', parentId: 21 }
]


function arrToTree(arr) {
  arr=JSON.parse(JSON.stringify(arr))
  const newArr = []
  // 1. 构建一个字典：能够快速根据id找到对象。
  const map = {}
  arr.forEach(item => {
    // 为了计算方便，统一添加children
    item.children = []
    // 构建一个字典
    map[item.id] = item
  })
 
  // 2. 对于arr中的每一项
  arr.forEach(item => {
    const parent = map[item.parentId]
    if (parent) {
      //    如果它有父级，把当前对象添加父级元素的children中
      parent.children.push(item)
    } else {
      //    如果它没有父级（pid:''）,直接添加到newArr
      newArr.push(item)
    }
  })
  return newArr
}

console.log(arrToTree(arr))

21.ajax

function ajax(option) {//type,url,obj,timeout,success,error将所有参数换成一个对象{}
    //  0.将对象转换成字符串
    var str = objToString(option.data);
    //  1.创建一个异步对象xmlhttp；
    var xmlhttp, timer;
    if (window.XMLHttpRequest) {
        xmlhttp = new XMLHttpRequest();
    } else {// code for IE6, IE5 
        xmlhttp = new ActiveXObject("Microsoft.XMLHTTP");
    }
    //  2.设置请求方式和请求地址； 
    // 判断请求的类型是POST还是GET
    if (option.type.toLowerCase() === 'get') {
        xmlhttp.open(option.type, option.url + "?t=" + str, true);
        //  3.发送请求；
        xmlhttp.send();
    } else {
        xmlhttp.open(option.type, option.url, true);
        // 注意：在post请求中，必须在open和send之间添加HTTP请求头：setRequestHeader(header,value);
        xmlhttp.setRequestHeader("Content-type", "application/x-www-form-urlencoded");
        //  3.发送请求；
        xmlhttp.send(str);
    }
    //  4.监听状态的变化；
    xmlhttp.onreadystatechange = function () {
        clearInterval(timer);
        if (xmlhttp.readyState === 4) {
            if (xmlhttp.status >= 200 && xmlhttp.status < 300 || xmlhttp.status == 304) {
                //  5.处理返回的结果；
                option.success(xmlhttp);//成功后回调；
            } else {
                option.error(xmlhttp);//失败后回调；
            }
        }
    }
    //处理obj 
    function objToString(data) {
        data.t = new Date().getTime();
        var res = [];
        for (var key in data) {
            //需要将key和value转成非中文的形式，因为url不能有中文。使用encodeURIComponent();
            res.push(encodeURIComponent(key) + " = " + encodeURIComponent(data[key]));
        }
        return res.join("&");
    }
    //判断外界是否传入了超时时间
    if (option.timeout) {
        timer = setInterval(function () {
            xmlhttp.abort();//中断请求
            clearInterval(timer);
        }, timeout);
    }
}

22.apply

Function.prototype.apply2 = function(obj,arr){
    obj = obj?Object(obj):window;
    let _fn = "fn",result;
    while (obj.hasOwnProperty(_fn)) {
      _fn = "fn" + Math.random(); // 循环判断并重新赋值
    }
    obj[_fn] = this;
    if(arr){
      result = obj[_fn](...arr);
    }else{
      result = obj[_fn]();
    }
    delete obj[_fn];
    return result;
  }

23.async和await

function asyncToGen(genFunction) {
    return function (...args) {
      const gen = genFunction.apply(this, args);
      return new Promise((resolve, reject) => {
        function step(key, arg) {
          let genResult;
          try {
            genResult = gen[key](arg);
          } catch (err) {
            return reject(err);
          }
          const { value, done } = genResult;
          if (done) {
            return resolve(value);
          }
          return Promise.resolve(value).then(
            (val) => {
              step('next', val);
            },
            (err) => {
              step('throw', err);
            },
          );
        }
        step('next');
      });
    };
  }
  const getData = () => new Promise(resolve => setTimeout(() => resolve('data'), 1000));
  function* testG() {
    const data = yield getData();
    console.log('data: ', data);
    const data2 = yield getData();
    console.log('data2: ', data2);
    return 'success';
  }
  
  const gen = asyncToGen(testG);
  gen().then(res => console.log(res));

24.bind

Function.prototype.bind2 = function (obj) {
    obj = obj ? Object(obj) : window
    let myArguments = arguments
    let self = this
    if (arguments.length > 1) {
      return function () {
        self.apply(obj, [...[...myArguments].slice(1), ...arguments])
      }
    }
    return function () {
      self.apply(obj, [...arguments])
    }
  }

25.call

Function.prototype.call2 = function(obj){
    obj = obj?Object(obj):window;
    let _fn = "fn",result;
    while (obj.hasOwnProperty(_fn)) {
      _fn = "fn" + Math.random(); // 循环判断并重新赋值
    }
    obj[_fn] = this;
    if(arguments.length>1){
      result = obj[_fn](...([...arguments].slice(1)));
    }else{
      result = obj[_fn]();
    }
    delete obj[_fn];
    return result;
  }

26.filter

Array.prototype.myFilter = function(callback, thisArg) {
    // 确认调用者必须是个数组
    if (Object.prototype.toString.call(this) !== '[object Array]') {
      throw new TypeError('this must be a array');
    }
    if (typeof callback !== 'function') {
      throw new TypeError(callback + 'is not a function');
    }
    // 返回结果的数组
    const res = [];
    // 让O成为回调函数的对象传递（强制转换对象）
    const O = Object(this);
    console.log(O)
    // >>>0 保证len为number，且为正整数
    // 无符号位移计算符
    const len = O.length >>> 0;
    // 对整个数组进行遍历
    for (let i = 0; i < len; i++) {
        // 遍历回调函数调用传参
        // call是传入（新this指向，参数）
        // thisArg新设置的this，这里无设置就是undefined
        // O[i] 是原数组的当前元素
        // i是当前index
        // O是原数组
        if (callback.call(thisArg, O[i], i, O)) {
          res.push(O[i]);
        }
    }
    // 返回结果
    return res;
  }
  console.log([30,20,16,10].myFilter((num) => { return num >= 12}));

27.forEach

Array.prototype.myForEach = function(callback, thisArg) {
    // 判断是否是数组调用，并且传入的是回调函数
    if (this == null) {
      throw new TypeError('this is null or not defined');
    }
    if (typeof callback !== "function") {
      throw new TypeError(callback + ' is not a function');
    }
    const O = Object(this);
    const len = O.length >>> 0;
    let k = 0;
   // 循环所有数据  
   for(let i = 0; i < len; i++) {
    callback.call(thisArg, O[k], k, O);
   }
  }

28.instanceof

function new_instance_of(leftValue,rightValue){
    let rightProto = rightValue.prototype;//取右边表达式的 prototype 值
    leftValue = leftValue.__proto__;//取左表达式的 __proto__ 值
    while(true){
        if(leftValue == null){
            return false;
        }
        if(leftValue === rightProto){
            return true;
        }
        leftValue = leftValue.__proto__;
    }
}
function Foo(){}
console.log(new_instance_of(Foo,Object))//true

29.jsonp

let jsonp=(url,data={},callback='callback')=>{
    //准备好带有padding的请求url
let dataStr=url.indexOf('?')=== -1?'?':'&'
// console.log(dataStr);
for(let key in data){
    dataStr +=`${key}=${data[key]}&`
}
dataStr +=`callback=`+callback

//构造 script
let oScript=document.createElement('script')
oScript.src=url+dataStr
//appendChild () 方法可向节点的子节点列表的末尾添加新的子节点
document.body.appendChild(oScript)

// window[callback]=(data)=>{
//     console.log(data);
// }
return new Promise((resolve,reject)=>{
    window[callback]=(data)=>{
        try{
            resolve(data)
        }catch(e){
            reject(e)
        }finally{
            oScript.parentNode.removeChild(oScript)// 注意这句代码，OScript移除,细节
        }
    }
})
}

jsonp('https://photo.sina.cn/aj/index?a=1',{
    page:1,
    cate:'recommend'
}).then(response=>{
    console.log(response,'-------then');
})

30.map

Array.prototype.myMap = function(callback, thisArg) {
    if (this == undefined) {
      throw new TypeError('this is null or not defined');
    }
    if (typeof callback !== 'function') {
      throw new TypeError(callback + ' is not a function');
    }
    const res = [];
    const O = Object(this);
    const len = O.length >>> 0;
    for (let i = 0; i < len; i++) {
       // 调用回调函数并传入新数组
       res[i] = callback.call(thisArg, O[i], i, O);
    }
    return res;
  }

31.new

/**
 * new 使用Js原生实现
 */
function Parent(name, age) {
    this.name = name;
    this.age = age;
    this.sayName = function () {
        console.log(this.name);
    }
}
const _new = function (Parent, ...rest) {
    //1.以构造器Parent的prototype为原型创建新对象
    const child = Object.create(Parent.prototype);
    //2. 将this和调用参数传给构造器执行
    const result = Parent.apply(child, rest);
    return typeof result === 'object' ? result : child;
}
const p1 = _new(Parent,'www','23');
console.log(p1);
p1.sayName();

32.object-create

Object.myCreate = function (proto, propertyObject = undefined) {
    if (propertyObject === null) {
      // 这里没有判断propertyObject是否是原始包装对象
      throw 'TypeError'
    } else {
      function Fn () {}
      Fn.prototype = proto
      const obj = new Fn()
      if (propertyObject !== undefined) {
        Object.defineProperties(obj, propertyObject)
      }
      if (proto === null) {
        // 创建一个没有原型对象的对象，Object.create(null)
        obj.__proto__ = null
      }
      return obj
    }
  }
  
  // 示例
  // 第二个参数为null时，抛出TypeError
  // const throwErr = Object.myCreate({a: 'aa'}, null)  // Uncaught TypeError
  // 构建一个以
  const obj1 = Object.myCreate({a: 'aa'})
  console.log(obj1)  // {}, obj1的构造函数的原型对象是{a: 'aa'}
  const obj2 = Object.myCreate({a: 'aa'}, {
    b: {
      value: 'bb',
      enumerable: true
    }
  })
  console.log(obj2)  // {b: 'bb'}, obj2的构造函数的原型对象是{a: 'aa'}

33.object-is

Object.is = function(x, y) {
    if (x === y) {
        // 当前情况下，只有一种情况是特殊的，即 +0 -0
        // 如果 x !== 0，则返回true
        // 如果 x === 0，则需要判断+0和-0，则可以直接使用 1/+0 === Infinity 和 1/-0 === -Infinity来进行判断
        return x !== 0 || 1 / x === 1 / y;
    }
    
    // x !== y 的情况下，只需要判断是否为NaN，如果x!==x，则说明x是NaN，同理y也一样
    // x和y同时为NaN时，返回true
    return x !== x && y !== y;
}

34.promise.all

Promise.prototype.all = function(promises){
    let results = [];
    let promiseCount = 0;
    let promisesLength = promises.length;
    return new Promise(function(resolve,reject){
        for(let val of promises){
            Promise.resolve(val).then(function(res){
                promiseCount++;
                results[i] = res;
                if(promiseCount === promisesLength){
                    return resolve(results);
                }
            },function(err){
                return reject(err);
            })
        }
    })
}

let promise1 = new Promise(function(resolve) {
    resolve(1);
  });
  let promise2 = new Promise(function(resolve) {
    resolve(2);
  });
  let promise3 = new Promise(function(resolve) {
    resolve(3);
  });
  
  let promiseAll = Promise.all([promise1, promise2, promise3]);
  promiseAll.then(function(res) {
    console.log(res);
  });

35.promise

const PENDING = 'PENDING';
const FULFILLED = 'FULFILLED';
const REJECTED = 'REJECTED';

const resolvePromise = (promise2, x, resolve, reject) => {
  // 自己等待自己完成是错误的实现，用一个类型错误，结束掉 promise  Promise/A+ 2.3.1
  if (promise2 === x) { 
    return reject(new TypeError('Chaining cycle detected for promise #<Promise>'))
  }
  // Promise/A+ 2.3.3.3.3 只能调用一次
  let called;
  // 后续的条件要严格判断 保证代码能和别的库一起使用
  if ((typeof x === 'object' && x != null) || typeof x === 'function') { 
    try {
      // 为了判断 resolve 过的就不用再 reject 了（比如 reject 和 resolve 同时调用的时候）  Promise/A+ 2.3.3.1
      let then = x.then;
      if (typeof then === 'function') { 
        // 不要写成 x.then，直接 then.call 就可以了 因为 x.then 会再次取值，Object.defineProperty  Promise/A+ 2.3.3.3
        then.call(x, y => { // 根据 promise 的状态决定是成功还是失败
          if (called) return;
          called = true;
          // 递归解析的过程（因为可能 promise 中还有 promise） Promise/A+ 2.3.3.3.1
          resolvePromise(promise2, y, resolve, reject); 
        }, r => {
          // 只要失败就失败 Promise/A+ 2.3.3.3.2
          if (called) return;
          called = true;
          reject(r);
        });
      } else {
        // 如果 x.then 是个普通值就直接返回 resolve 作为结果  Promise/A+ 2.3.3.4
        resolve(x);
      }
    } catch (e) {
      // Promise/A+ 2.3.3.2
      if (called) return;
      called = true;
      reject(e)
    }
  } else {
    // 如果 x 是个普通值就直接返回 resolve 作为结果  Promise/A+ 2.3.4  
    resolve(x)
  }
}

class Promise {
  constructor(executor) {
    this.status = PENDING;
    this.value = undefined;
    this.reason = undefined;
    this.onResolvedCallbacks = [];
    this.onRejectedCallbacks= [];

    let resolve = (value) => {
      if(this.status ===  PENDING) {
        this.status = FULFILLED;
        this.value = value;
        this.onResolvedCallbacks.forEach(fn=>fn());
      }
    } 

    let reject = (reason) => {
      if(this.status ===  PENDING) {
        this.status = REJECTED;
        this.reason = reason;
        this.onRejectedCallbacks.forEach(fn=>fn());
      }
    }

    try {
      executor(resolve,reject)
    } catch (error) {
      reject(error)
    }
  }

  then(onFulfilled, onRejected) {
    //解决 onFufilled，onRejected 没有传值的问题
    //Promise/A+ 2.2.1 / Promise/A+ 2.2.5 / Promise/A+ 2.2.7.3 / Promise/A+ 2.2.7.4
    onFulfilled = typeof onFulfilled === 'function' ? onFulfilled : v => v;
    //因为错误的值要让后面访问到，所以这里也要跑出个错误，不然会在之后 then 的 resolve 中捕获
    onRejected = typeof onRejected === 'function' ? onRejected : err => { throw err };
    // 每次调用 then 都返回一个新的 promise  Promise/A+ 2.2.7
    let promise2 = new Promise((resolve, reject) => {
      if (this.status === FULFILLED) {
        //Promise/A+ 2.2.2
        //Promise/A+ 2.2.4 --- setTimeout
        setTimeout(() => {
          try {
            //Promise/A+ 2.2.7.1
            let x = onFulfilled(this.value);
            // x可能是一个proimise
            resolvePromise(promise2, x, resolve, reject);
          } catch (e) {
            //Promise/A+ 2.2.7.2
            reject(e)
          }
        }, 0);
      }

      if (this.status === REJECTED) {
        //Promise/A+ 2.2.3
        setTimeout(() => {
          try {
            let x = onRejected(this.reason);
            resolvePromise(promise2, x, resolve, reject);
          } catch (e) {
            reject(e)
          }
        }, 0);
      }

      if (this.status === PENDING) {
        this.onResolvedCallbacks.push(() => {
          setTimeout(() => {
            try {
              let x = onFulfilled(this.value);
              resolvePromise(promise2, x, resolve, reject);
            } catch (e) {
              reject(e)
            }
          }, 0);
        });

        this.onRejectedCallbacks.push(()=> {
          setTimeout(() => {
            try {
              let x = onRejected(this.reason);
              resolvePromise(promise2, x, resolve, reject)
            } catch (e) {
              reject(e)
            }
          }, 0);
        });
      }
    });
  
    return promise2;
  }
}

36.promise.race

Promise.race = function(promises){
    //将可迭代对象转换为数组
    promises = Array.from(promises);
    return new Promise((resolve,reject)=>{
        if(promises.length === 0){
            //空的可迭代对象，用于pending状态
        }else{
            for(let i = 0;i < promises.length;i++){
                Promise.resolve(promises[i]).then((data)=>{
                    resolve(data);
                }).catch((reason)=>{
                    reject(reason)
                })
            }
        }
    })
}

let p1 = new Promise(function(resolve,reject){
    setTimeout(function(){
     resolve('success')
    },1000)
})

let p2 = new Promise(function(resolve,reject){
    setTimeout(function(){
     resolve('faild')
    },500)
})

Promise.race([p1,p2]).then(result=>{
console.log(result)             //  faild    faild耗时短
})

37.reduce

Array.prototype.myReduce = function(callback, initialValue) {
    // 判断调用的是否是数组，以及传入的callback是否是函数
    if (this == undefined) {
      throw new TypeError('this is null or not defined');
    }
    if (typeof callback !== 'function') {
      throw new TypeError(callbackfn + ' is not a function');
    }
    // 空数组也是不允许的
    if (this.length == 0) {
     throw new TypeError('Reduce of empty array with no initial value');
    }
    // 让O成为回调函数的对象传递（强制转换对象）
    const O = Object(this);
    // >>>0 保证len为number，且为正整数
    const len = this.length >>> 0;
    // 保存初始值，初始值不传的时候为undefined
    let accumulator = initialValue;
    // 标志位
    let k = 0;
    // 如果第二个参数为undefined的情况，则数组的第一个有效值作为累加器的初始值
    if (accumulator === undefined) {
      // 这里是k++，就是赋值完成之后k再加1
      accumulator = O[k++];
    }
    // 此时如果有初始值，k是0，如果无初始值k是1
    for(k;k<len;k++) {
     accumulator = callback.call(this, accumulator, O[k], k, O);
    }
    return accumulator;
  }
  console.log([2,4,6].myReduce((t,n)=>{return t+n}));
  console.log([2,4,6].myReduce((t,n)=>{return t+n},10));

38.sleep

//Promise
const sleep = time => {
    return new Promise(resolve => setTimeout(resolve,time))
  }
  sleep(1000).then(()=>{
    console.log(1)
  })
  
  //Generator
  function* sleepGenerator(time) {
    yield new Promise(function(resolve,reject){
      setTimeout(resolve,time);
    })
  }
  sleepGenerator(1000).next().value.then(()=>{console.log(1)})
  
  //async
  function sleep(time) {
    return new Promise(resolve => setTimeout(resolve,time))
  }
  async function output() {
    let out = await sleep(1000);
    console.log(1);
    return out;
  }
  output();
  
  //ES5
  function sleep(callback,time) {
    if(typeof callback === 'function')
      setTimeout(callback,time)
  }
  
  function output(){
    console.log(1);
  }
  sleep(output,1000);

39.vue-Reactive

const targetMap = new WeakMap();
let activeEffect = null; // 引入 activeEffect 变量

const effect = eff => {
    activeEffect = eff; // 1. 将副作用赋值给 activeEffect
  activeEffect();     // 2. 执行 activeEffect
  activeEffect = null;// 3. 重置 activeEffect
}

const track = (target, key) => {
    if (activeEffect) {  // 1. 判断当前是否有 activeEffect
        let depsMap = targetMap.get(target);
        if (!depsMap) {
            targetMap.set(target, (depsMap = new Map()));
        }
        let dep = depsMap.get(key);
        if (!dep) {
            depsMap.set(key, (dep = new Set()));
        }
        dep.add(activeEffect);  // 2. 添加 activeEffect 依赖
    }
}

const trigger = (target, key) => {
    const depsMap = targetMap.get(target);
    if (!depsMap) return;
    let dep = depsMap.get(key);
    if (dep) {
        dep.forEach(effect => effect());
    }
};

const reactive = (target) => {
    const handler = {
        get(target, key, receiver) {
            const result = Reflect.get(target, key, receiver);
            track(target, key);
            return result;
        },
        set(target, key, value, receiver) {
            const oldValue = target[key];
            const result = Reflect.set(target, key, value, receiver);
            if (oldValue != result) {
                trigger(target, key);
            }
            return result;
        }
    }

    return new Proxy(target, handler);
}

let product = reactive({ price: 10, quantity: 2 });
let total = 0, salePrice = 0;
// 修改 effect 使用方式，将副作用作为参数传给 effect 方法
effect(() => {
    total = product.price * product.quantity
});
effect(() => {
    salePrice = product.price * 0.9
});
console.log(total, salePrice);  // 20 9
product.quantity = 5;
console.log(total, salePrice);  // 50 9
product.price = 20;
console.log(total, salePrice);  // 100 18

40.算法笔试

1.插入排序

function insertionSort(arr) {
    var len = arr.length;
    var preIndex, current;
    for (var i = 1; i < len; i++) {
        preIndex = i - 1;
        current = arr[i];
        while(preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex+1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex+1] = current;
    }
    return arr;
}
const arr1 = [2,6,8,2,3,5,0,1,6,8]
let res = insertionSort(arr1)
console.log(arr1)//[ 0, 1, 2, 2, 3, 5, 6, 6, 8, 8]

2.堆排序

var len;    // 因为声明的多个函数都需要数据长度，所以把len设置成为全局变量

function buildMaxHeap(arr) {   // 建立大顶堆
    len = arr.length;
    for (var i = Math.floor(len/2); i >= 0; i--) {
        heapify(arr, i);
    }
}

function heapify(arr, i) {     // 堆调整
    var left = 2 * i + 1,
        right = 2 * i + 2,
        largest = i;

    if (left < len && arr[left] > arr[largest]) {
        largest = left;
    }

    if (right < len && arr[right] > arr[largest]) {
        largest = right;
    }

    if (largest != i) {
        swap(arr, i, largest);
        heapify(arr, largest);
    }
}

function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

function heapSort(arr) {
    buildMaxHeap(arr);

    for (var i = arr.length-1; i > 0; i--) {
        swap(arr, 0, i);
        len--;
        heapify(arr, 0);
    }
    return arr;
}

const arr1 = [12,4,6,9,11,0,4,3,7,9]
let res = heapSort(arr1)
console.log(res)//[0, 3, 4,  4,  6, 7, 9, 9, 11, 12]

3.斐波那契数列

//方法一：使用递归
function fibonacci(n) {
    if (n == 1 || n == 2) {
        return 1
    };
    return fibonacci(n - 2) + fibonacci(n - 1);
}
console.log(fibonacci(3))//2

//方法二：改进递归-把前两位数字做成参数避免重复计算
function fibonacci(n) {
    function fib(n, v1, v2) {
        if (n == 1)
            return v1;
        if (n == 2)
            return v2;
        else
            return fib(n - 1, v2, v1 + v2)
    }
    return fib(n, 1, 1)
}
fibonacci(30)

//方法三：改进递归-利用闭包特性把运算结果存储在数组里，避免重复计算
var fibonacci = function () {
    let memo = [0, 1];
    let fib = function (n) {
        if (memo[n] == undefined) {
            memo[n] = fib(n - 2) + fib(n - 1)
        }
        return memo[n]
    }
    return fib;
}()
fibonacci(30)


//方法四：改进递归-摘出存储计算结果的功能函数
var memoizer = function (func) {
    let memo = [];
    return function (n) {
        if (memo[n] == undefined) {
            memo[n] = func(n)
        }
        return memo[n]
    }
};
var fibonacci=memoizer(function(n){
    if (n == 1 || n == 2) {
        return 1
    };
    return fibonacci(n - 2) + fibonacci(n - 1);
})
fibonacci(30)


//方法五：普通for循环
function fibonacci(n) {
    var n1 = 1, n2 = 1, sum;
    for (let i = 2; i < n; i++) {
        sum = n1 + n2
        n1 = n2
        n2 = sum
    }
    return sum
}
fibonacci(30)

//方法六：for循环+解构赋值
var fibonacci = function (n) {
    let n1 = 1; n2 = 1;
    for (let i = 2; i < n; i++) {
        [n1, n2] = [n2, n1 + n2]
    }
    return n2
}
fibonacci(30)

4.归并排序

function mergeSort(arr) {  // 采用自上而下的递归方法
    var len = arr.length;
    if(len < 2) {
        return arr;
    }
    var middle = Math.floor(len / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle);
    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right)
{
    var result = [];

    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }

    while (left.length)
        result.push(left.shift());

    while (right.length)
        result.push(right.shift());

    return result;
}


const arr1 = [1,4,6,1,0,3,4,2,7,3,1]
let res = mergeSort(arr1)
console.log(res)//[0, 1, 1, 1, 2,3, 3, 4, 4, 6,7]

5.汉诺塔问题

/** 
 * @param {圆盘数：number} plates 
 * @param {起始柱子 a：string} source 
 * @param {辅助柱子 b：string} helper 
 * @param {目标柱子 c：string} dest 
 * @param {移动步骤集：Array，数组的长度就是移动的次数} moves 
 */
function hanoi(plates, source, helper, dest, moves = []) {
    if (plates <= 0) {
        return moves;
    }
    if (plates === 1) {
        moves.push([source, dest]);
    } else {
        hanoi(plates - 1, source, dest, helper, moves);
        moves.push([source, dest]);
        hanoi(plates - 1, helper, source, dest, moves);
    }
    return moves;
}

// test
console.log(hanoi(4, 'source', 'helper', 'dest')); // 输出结果如下图展示

6.合并两个有序数组

var merge = function (nums1, m, nums2, n) {
    var p = m + n - 1;//0
    var p1 = m - 1;//-1
    var p2 = n - 1;//0
      // 理论上来说，nums2应该全部填充进去，所以这里以p2作为条件
    while (p2 >= 0) {
        // nums1里面全是0的情况，比如[0], 0, [1], 1
        if (p1 < 0) {
            // 直接用nums2去填补nums1就好了
            nums1[p--] = nums2[p2--]
        // 只有nums2比nums1大才用nus2填补
        } else if (nums2[p2] > nums1[p1]) {
            nums1[p] = nums2[p2];
            p--;
            p2--;
        // 反之用nums1填补
        } else {
            nums1[p] = nums1[p1];
            p--;
            p1--;
        }
    };
    return nums1;
};

let nums1 = [1,2,3,0,0,0], m = 3,nums2 = [2,5,6],n = 3
console.log(merge(nums1, m, nums2, n))//[ 1, 2, 2, 3, 5, 6 ]

7.快速排序

function quickSort(arr, left, right) {
    var len = arr.length,
        partitionIndex,
        left = typeof left != 'number' ? 0 : left,
        right = typeof right != 'number' ? len - 1 : right;

    if (left < right) {
        partitionIndex = partition(arr, left, right);
        quickSort(arr, left, partitionIndex-1);
        quickSort(arr, partitionIndex+1, right);
    }
    return arr;
}

function partition(arr, left ,right) {     // 分区操作
    var pivot = left,                      // 设定基准值（pivot）
        index = pivot + 1;
    for (var i = index; i <= right; i++) {
        if (arr[i] < arr[pivot]) {
            swap(arr, i, index);
            index++;
        }        
    }
    swap(arr, pivot, index - 1);
    return index-1;
}

function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
function partition2(arr, low, high) {
  let pivot = arr[low];
  while (low < high) {
    while (low < high && arr[high] > pivot) {
      --high;
    }
    arr[low] = arr[high];
    while (low < high && arr[low] <= pivot) {
      ++low;
    }
    arr[high] = arr[low];
  }
  arr[low] = pivot;
  return low;
}

function quickSort2(arr, low, high) {
  if (low < high) {
    let pivot = partition2(arr, low, high);
    quickSort2(arr, low, pivot - 1);
    quickSort2(arr, pivot + 1, high);
  }
  return arr;
}

const arr1 = [1,4,6,1,0,3,4,2,7,3,1]
let res = quickSort(arr1,0,11)
console.log(res)//[ 0, 1, 1, 1, 2, 3, 3, 4, 4, 6,7]

8.两数之和

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
const twoSum = (nums, target) => {
    const prevNums = {};                    // 存储出现过的数字，和对应的索引               
  
    for (let i = 0; i < nums.length; i++) {       // 遍历元素   
      const curNum = nums[i];                     // 当前元素   
      const targetNum = target - curNum;          // 满足要求的目标元素   
      const targetNumIndex = prevNums[targetNum]; // 在prevNums中获取目标元素的索引
      if (targetNumIndex !== undefined) {         // 如果存在，直接返回 [目标元素的索引,当前索引]
        return [targetNumIndex, i];
      } else {                                    // 如果不存在，说明之前没出现过目标元素
        prevNums[curNum] = i;                     // 存入当前的元素和对应的索引
      }
    }
  }

  let nums = [2,7,11,15], target = 17
  console.log(twoSum(nums,target))//[ 0, 3 ]

9.冒泡排序

 //双向冒泡排序
 function bubbleSort_twoway(arr) {
    var len = arr.length;    //依次将最大的数放置到数组末尾，将第二大的数放到倒数第二位...
    var flag = false;
    for(var i = 0; i < len/2; i++) {
        flag = false;
        for(var j = i; j < len - 1 - i; j++) {   //从前往后,比较相邻两个数,把大的放在后边.之前已放置成功的可以不再参与比较
            if(arr[j] > arr[j + 1]) {
                var middle = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = middle;
                flag =true;
            }
        }
        if(!flag){
            break;
        }

        for(var j = len - 1 - i; j > i; j--){
            if(arr[j] < arr[j - 1]) {
                var middle = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = middle;
                flag = true;
            }
        }
        if(!flag){
            break;
        }
    }
    return arr;
}

var defaultArr = [3, 5, 32, 15, 7, 26, 10, 55, 45, 12, 28, 88, 18];
var resultArr = bubbleSort_twoway(defaultArr);
console.table(resultArr);

10.爬台阶

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    const sqrt_5 = Math.sqrt(5);
    const fib_n = Math.pow((1 + sqrt_5) / 2, n + 1) - Math.pow((1 - sqrt_5) / 2,n + 1);
    return Math.round(fib_n / sqrt_5);
};


/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    const dp = [];
    dp[0] = 1;
    dp[1] = 1;
    for(let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
};

11.数组交集

//数组功能扩展
//数组迭代函数
Array.prototype.each = function(fn){
    fn = fn || Function.K;
    var a = [];
    var args = Array.prototype.slice.call(arguments, 1);
    for(var i = 0; i < this.length; i++){
    var res = fn.apply(this,[this[i],i].concat(args));
    if(res != null) a.push(res);
    }
    return a;
   };
   //数组是否包含指定元素
   Array.prototype.contains = function(suArr){
    for(var i = 0; i < this.length; i ++){
    if(this[i] == suArr){
    return true;
    }
    }
    return false;
   }
   //不重复元素构成的数组
   Array.prototype.uniquelize = function(){
    var ra = new Array();
    for(var i = 0; i < this.length; i ++){
    if(!ra.contains(this[i])){
    ra.push(this[i]);
    }
    }
    return ra;
   };
   //两个数组的交集
   Array.intersect = function(a, b){
    return a.uniquelize().each(function(o){return b.contains(o) ? o : null});
   };
   //两个数组的差集
   Array.minus = function(a, b){
    return a.uniquelize().each(function(o){return b.contains(o) ? null : o});
   };
   //两个数组的补集
   Array.complement = function(a, b){
    return Array.minus(Array.union(a, b),Array.intersect(a, b));
   };
   //两个数组并集
   Array.union = function(a, b){
    return a.concat(b).uniquelize();
   };


var a = [1,2,3,4,5]
var b = [2,4,6,8,10]
console.log("数组a：", a);
console.log("数组b：", b);
var sa = new Set(a);
var sb = new Set(b);
// 交集
let intersect = a.filter(x => sb.has(x));
// 差集
let minus = a.filter(x => !sb.has(x));
// 补集
let complement = [...a.filter(x => !sb.has(x)), ...b.filter(x => !sa.has(x))];
// 并集
let unionSet = Array.from(new Set([...a, ...b]));
console.log("a与b的交集：", intersect);
console.log("a与b的差集：", minus);
console.log("a与b的补集：", complement);
console.log("a与b的并集：", unionSet);

12.希尔排序

function shellSort(arr) {
    var len = arr.length,
        temp,
        gap = 1;
    while(gap < len/3) {          //动态定义间隔序列
        gap =gap*3+1;
    }
    for (gap; gap > 0; gap = Math.floor(gap/3)) {
        for (var i = gap; i < len; i++) {
            temp = arr[i];
            for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) {
                arr[j+gap] = arr[j];
            }
            arr[j+gap] = temp;
        }
    }
    return arr;
}

var defaultArr = [3, 5, 32, 15, 7, 26, 10, 55, 45, 12, 28, 88, 18];
var resultArr = shellSort(defaultArr);
console.table(resultArr);

13.旋转数组

/**
输入: nums = [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]
 */

let reverse = function(nums, start, end){
    while(start < end){
        [nums[start++], nums[end--]] = [nums[end], nums[start]];
    }
}
let rotate = function(nums, k) {
    k %= nums.length;
    reverse(nums, 0, nums.length - 1);
    reverse(nums, 0, k - 1);
    reverse(nums, k, nums.length - 1);
    return nums;
};

14.选择排序

function selectionSort(arr) {
    var len = arr.length;
    var minIndex, temp;
    for (var i = 0; i < len - 1; i++) {
        minIndex = i;
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {     // 寻找最小的数
                minIndex = j;                 // 将最小数的索引保存
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}
var defaultArr = [3, 5, 32, 15, 7, 26, 10, 55, 45, 12, 28, 88, 18];
var resultArr = selectionSort(defaultArr);
console.table(resultArr);

Donate

Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.