# 1. bind、call、apply 的实现原理？

• apply 实现原理：第一个参数是绑定的 this，默认为 window，第二个参数是数组或类数组

  Function.prototype.apply = function(context = window, args) {
    if (typeof this !== 'function') {
      throw new TypeError('Type Error')
    }
    const fn = Symbol('fn')
    context[fn] = this
    const res = context[fn](...args)
    delete context[fn]
    return res
  }
  

• call 的实现原理：与 apply 唯一不同的是，call()方法接受的是一个参数列表

  Function.prototype.call = function(context = window, ...args) {
    if (typeof this !== 'function') {
      throw new TypeError('Type Error')
    }
    const fn = Symbol('fn')
    context[fn] = this
    const res = context[fn](...args)
    delete context[fn]
    return res
  }
  

• bind 的实现原理：返回一个函数，参数与 apply 一样

  Function.prototype.bind = function(context = window, ...args) {
    if (typeof this !== 'function') {
      throw new TypeError('Type Error')
    }
    // 保存this
    let self = this
    return function F() {
      // 考虑new的情况
      if (this instanceof F) {
        return new self(...args, ...arguments)
      } else {
        return self.apply(context, [...args, ...arguments])
      }
    }
  }
  

# 2. 能否手写一个 new？

• 实现 new 操作符的步骤：
  1. 函数接受一个不定量的参数，第一个参数为构造函数，剩余的参数被构造函数使用
  2. 内部创建一个空对象 obj
  3. 因为 obj 对象需要访问到构造函数原型链上的属性，所有通过 setPrototype 将两者关联起来
  4. 将 obj 绑定到构造函数上，并传入剩余参数
  5. 判断构造函数返回值是否是对象，如果为对象就是要构造函数返回的值，否则返回 obj

  function createNew(Con, ...args) {
    if (typeof Con !== 'function') {
      throw new Error('Type Error')
    }
    let obj = {}
    Object.setPrototype(obj, Con.prototype) // 等价于obj.__proto__ = Con.prototype
    let result = Con.apply(obj, ...args)
    return result instanceof Object ? result : obj
  }
  

注意：当 new Object()不传参数时，字面量{}和 new 关键字创建的对象是 Object 的实例一样的；Object.create()传两个参数，第一个为新创建对象的原型对象，第二个为自身定义的属性;为 null，新对象是空对象，没有原型，不继承任何对象；arg 为指定对象，新对象的原型指向指定对象，继承指定对象

# 3. 实现一个 instanceof？

• instanceof 用来检测一个对象在其原型链中是否存在一个构造函数的 prototype 属性

instanceof 运算符用于检测构造函数的 prototype 属性是否出现在某个实例对象的原型链上。

function instanceof(left, right) {
  // 必须是对象或者函数
  if (!(left && ['object', 'function'].includes(typeof left))) {
    return false
  }
  let proto = left.__proto__
  let prototype = right.prototype
  while(true) {
      if (proto === null) return false
      if (proto === prototype) return true
      proto = proto.__proto__ // 等价于proto = Object.getPrototypeOf(proto)
  }
}

// 递归方式：
const instanceOf = (obj, func) => {
  // 必须是对象或者函数
  if (!(obj && ['object', 'function'].includes(typeof obj))) {
    return false
  }
  let proto = Object.getPrototypeOf(obj)
  if (proto === func.prototype) {
    return true
  } else if (proto === null) {
    return false
  } else {
    instanceOf(proto, func)
  }
}

# 4. 实现一个 发布订阅 EventEmitter？

发布订阅模式中，包含发布者，事件调度中心，订阅者三个角色。EventEmitter 的一个实例就是一个事件调度中心，发布者和订阅者是松散耦合的，互不关心对方是否存在，他们关注的是事件本身。发布者借用事件调度中心提供的 emit 方法发布事件，而订阅者则通过 on 进行订阅。

class EventEmitter {
  constructor() {
    this.listeners = {} // 存储所有事件的监听器
  }
  /**
   * 注册事件监听者
   * @param {*} type 事件类型
   * @param {*} cb 回调函数
   */
  on(type, cb) {
    if (!this.listeners[type]) {
      this.listeners[type] = []
    }
    this.listeners[type].push(cb)
  }
  /**
   * 发布事件
   * @param {*} type 事件类型
   * @param  {...any} args 参数列表，把emit传递的参数赋给回调函数
   */
  emit(type, ...args) {
    if (this.listeners[type]) {
      this.listeners[type].forEach((cb) => {
        cb(...args)
      })
    }
  }
  /**
   * 移除某个事件的一个监听者
   * @param {*} type 事件类型
   * @param {*} cb 回调函数
   */
  off(type, cb) {
    if (this.listeners[type]) {
      const targetIndex = this.listeners[type].findIndex((item) => item === cb)
      if (targetIndex !== -1) {
        this.listeners[type].splice(targetIndex, 1)
      }
      if (this.listeners[type].length === 0) {
        delete this.listeners[type]
      }
    }
  }
  offAll(type) {
    if (this.listeners[type]) {
      delete this.listeners[type]
    }
  }
  once(type, cb) {
    const proxyCallback = (...args) => {
      cb(...args)
      // 回调函数执行完成之后就删除事件订阅
      this.off(type, proxyCallback)
    }
    this.on(type, proxyCallback)
  }
}

特点: 发布订阅模式中，对于发布者 Publisher 和订阅者 Subscriber 没有特殊的约束，他们好似是匿名活动，借助事件调度中心提供的接口发布和订阅事件.松散耦合，灵活度高，常用作事件总线

缺点: 当事件类型越来越多时，难以维护，需要考虑事件命名的规范

• 观察者模式 角色很明确，没有事件调度中心作为中间者，目标对象 Subject 和观察者 Observer 都要实现约定的成员方法。双方联系更紧密，目标对象的主动性很强，自己收集和维护观察者，并在状态变化时主动通知观察者更新。

  // 观察者
  class Observer {
    constructor(cb) {
      if (typeof cb === 'function') {
        this.cb = cb
      } else {
        throw new Error('Observer构造器必须传入函数类型！')
      }
    }
    update() {
      this.cb()
    }
  }
  // 被观察者
  class Subject {
    constructor() {
      this.observerList = [] // 维护观察者列表
    }
    addObserver(observer) {
      this.observerList.push(observer)
    }
    notify() {
      this.observerList.forEach((observer) => {
        observer.update()
      })
    }
  }
  

# 5. 数组去重的方式？

const arr = [1, 1, '1', 17, true, true, false, false, 'true', 'a', {}, {}]
// => [1, '1', 17, true, false, 'true', 'a', {}, {}]

• 方式一、利用 Set

const res = Array.from(new Set(arr))

• 方式二、利用 indexOf

const unique = (arr) => {
  const res = []
  for (let i = 0; i < arr.length; i++) {
    if (res.indexOf(arr[i]) === -1) {
      res.push(arr[i])
    }
    // if(!res.includes(arr[i])) {
    //   res.push(arr[i])
    // }
  }
  return res
}

const unique = (arr) => {
  return arr.filter((item, index) => {
    return arr.indexOf(item) === index
  })
}

注意：当然也可以用 include、filter，思路大同小异

• 方式三、两层 for 循环 + splice

const unique = (arr) => {
  let len = arr.length
  for (let i = 0; i < len; i++) {
    for (let j = i + 1; j < len; j++) {
      if (arr[i] === arr[j]) {
        arr.splice(j, 1)
        // 每删除一个树，j--保证j的值经过自加后不变。同时，len--，减少循环次数提升性能
        len--
        j--
      }
    }
  }
  return arr
}

• 方式四、利用 Map

const unique = (arr) => {
  const map = new Map()
  const res = []
  for (let i = 0; i < arr.length; i++) {
    if (map.has(arr[i])) {
      map.set(arr[i], true)
    } else {
      map.set(arr[i], false)
      res.push(arr[i])
    }
  }
  return res
}

• 方式五、sort

const unique = (arr) => {
  arr = arr.sort()
  let array = [arr[0]]
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] !== arr[i - 1]) {
      array.push(arr[i])
    }
  }
  return array
}

# 6. 解析 URL 参数？

• 方式一、split 分割

  function parseParam(url) {
    const paramsStr = /.+\?(.+)$/.exec(url)[1] // 将?后面的字符串取出来
    const paramsArr = paramsStr.split('&') // 将字符串以&分割后存到数组里
    let paramsObj = {} // 将params存到对象中
    paramsArr.forEach((param) => {
      if (/=/.test(param)) {
        // 处理有value的参数
        let [key, val] = param.split('=') // 分割key和value
        val = decodeURIComponent(val) // 解码
        val = /^\d+$/.test(val) ? parseFloat(val) : val // 判断是否转为数字
        if (paramsObj.hasOwnProperty(key)) {
          // 如果对象有key，则添加一个值
          paramsObj[key] = [].concat(paramsObj[key], val)
        } else {
          // 如果对象没有这个key，创建key并设置值
          paramsObj[key] = val
        }
      } else {
        // 处理没有value的参数
        paramsObj[param] = true
      }
    })
    return paramsObj
  }
  

• 方式二、URLSearchParams

  // 创建一个URLSearchParams实例
  const urlSearchParams = new URLSearchParams(window.location.search)
  // 把键值对列表转换为一个对象
  const params = Object.fromEntries(urlSearchParams.entries())
  

# 7. 版本比较？

如果 version1 > version2 返回 1， 如果 version1 < version2 返回 -1， 除此之外返回 0

function compileVersion(version1, version2) {
  // 将两个版本号切割成由修订号组成的数组
  const arr1 = version1.split('.')
  const arr2 = version2.split('.')
  // 比较数组长度，得到最大的数组长度
  const maxLength = Math.max(arr1.length, arr2.length)
  // 遍历数组，分别比较同一个位置上的版本号
  for (let i = 0; i < maxLength; i++) {
    // 从左到右依次比较版本号
    const a = arr1[i] || 0
    const b = arr2[i] || 0
    // 忽略前导0，使用Number()转为数字
    if (Number(a) > Number(b)) {
      return 1
    } else if (Number(a) < Number(b)) {
      return -1
    }

    // 对比结束的时候就返回0
    if (i === maxLength - 1) {
      return 0
    }
  }
}

console.log(compileVersion('0.1', '1.1'))

# 8. 手写 防抖 和 节流？

• debounce 防抖：触发高频时间后 n 秒内函数只会执行一次,如果 n 秒内高频时间再次触发,则重新计算时间（按最后一次算。比如说“停止输入 5s 后才发送请求”）原理：事件响应函数在一段时间后才执行，如果在这段时间内再次调用，则重新计算时间；当预定的时间内没有再次调用该函数，则执行响应函数

  const debounce = (fn, time) => {
    let timeout = null
    return function() {
      clearTimeout(timeout)
      timeout = setTimeout(() => {
        fn.apply(this, arguments) // 改变函数执行函数内部this指向问题，arguments是event指向问题
      }, time)
    }
  }
  
  // 扩展：需要立即执行？
  function debounce(fn, wait, immediate) {
    var timeout, result
    let debounced = function() {
      var _this = this // 改变this指向问题
      var args = arguments // 改变event参数问题
      if (timeout) clearTimeout(timeout)
      if (immediate) {
        var callNow = !timeout // 是否需要立即执行
        timeout = setTimeout(() => {
          timeout = null
        }, wait)
        // 立即执行
        if (callNow) result = fn.apply(_this, args)
      } else {
        // 不立即执行
        timeout = setTimeout(function() {
          fn.apply(_this, args)
        }, wait)
      }
      return result
    }
    debounced.cancel = function() {
      clearTimeout(timeout)
      timeout = null // 清空，防止内存泄漏
    }
    return debounced
  }
  

  防抖常应用于用户进行搜索输入节约请求资源，window 触发 resize 事件时进行防抖只触发一次

  • 防抖的应用场景
    1. scroll 事件滚动触发
    2. 搜索框输入查询
    3. 表单验证
    4. 按钮提交事件
    5. 浏览器窗口缩放，resize 事件等

• throttle 节流：高频时间触发,但 n 秒内只会执行一次,所以节流会稀释函数的执行频率（在 n 秒内只会执行一次，所以节流会稀释函数的执行频率）原理：如果你持续触发事件，每隔一段时间只会执行一次。两种实现方式：一种是时间戳、另一种是定时器[leading, trailing]

  const throttle = (fn, time) => {
    let flag = true
    return function() {
      if (!flag) return
      flag = false
      setTimeout(() => {
        fn.apply(this, arguments)
        flag = true
      }, time)
    }
  }
  
  // 时间戳
  // 第一次触发，最后不会被调用leading: false trailing: true
  function throttle(fn, wait) {
    let _this, args
    let old = 0 // 之前的时间戳
    return function() {
      _this = this
      args = arguments
      // 获取当前的时间戳
      let now = new Date().valueOf()
      if (now - old > wait) {
        fn.apply(_this, args)
        old = now
      }
    }
  
    // 定时器
    // 第一次不触发，最后一次会触发leading: true, trailing: false
    function throttle(fn, wait) {
    let _this, args, timeout
    return function() {
      _this = this
      args = arguments
      if (!timeout) {
        timeout = setTimeout(() => {
          timeout = null // 为了下一次能继续执行
          fn.apply(_this, args)
        }, wait)
      }
    }
  }
  

  节流常应用于鼠标不断点击触发、监听滚动事件

# 9. 你知道判断数组的几种方式？

function isArray(arr) {
  // 1. 通过原型链判断
  // return arr.__proto__ === Array.prototype;
  // 2. 通过 ES6 中 Array.isArray()判断
  // return Array.isArray(arr);
  // 3. 通过 instanceof 判断
  // return arr instanceof Array;
  // 4. 通过 Array.prototype.isPrototypeOf() 判断
  // return Array.prototype.isPrototypeOf(arr);
  // 5. 通过 Object.prototype.toString.call() 判断
  return Object.prototype.toString.call(arr).slice(8, -1) === 'Array'
}

扩展：isPrototypeOf 和 instanceof 的区别？

1. isPrototypeOf 表示对象是否在另一个对象的原型链上
2. instanceof 运算符用来测试一个对象在其原型链中是否存在一个构造函数的 prototype 属性

# 10. 使用 reduce 实现 map?

用数组的 reduce 方法实现 map 方法

arr.reduce((previousValue, currentValue, currentIndex, array) => {},
initialValue)

reduce 接受两个参数，第一个参数，指定了每次迭代调用的函数，函数的返回值为下一次迭代的 previousValue。第二个参数为初始值，是可选的。

1. 若没有指定初始值，那么第一次的 previousValue 为 arr[0], currentValue 为 arr[1], currentIndex 为 1
2. 若指定初始值，那么第一次的 previousValue 为 initialValue, currentValue 为 arr[0], currentIndex 为 0
3. 第二个参数为 thisArg，可选的，表示执行函数时的 this

注意：如果 callback 为箭头函数时，里面的 this 执行外层代码块（非严格模式下为 window），此时指定的 thisArg 无效

Array.prototype.MCmap = function(fn, thisArg) {
  const result = []
  this.reduce((prev, curr, index, array) => {
    result[index] = fn.call(thisArg, array[index], index, array)
  }, 0)
  return result
}
let arr = [1, 2, 3]
let arr1 = arr.MCmap((item) => {
  return item * 2
})
console.log(arr1)

# 11. 手写数据类型判断?

function typeOf(obj) {
  let res = Object.prototype.toString.call(obj).split(' ')[1]
  res = res.substring(0, res.length - 1).toLowerCase()
  return res
  // 更好的写法
  // return Object.prototype.toString.call(obj).slice(8, -1).toLowerCase()
}
typeOf([]) // 'array'
typeOf({}) // 'object'
typeOf(new Date()) // 'date'

# 12. 手写继承?

• 原型链继承
• 借用构造函数实现继承
• 组合继承
• 寄生式继承
• class 实现继承

# 13. 偏函数 & compose & 柯里化？

// 面试问reduce实现compose(组合函数) 柯里化
function sum(a, b, c) {
  return a + b + c
}

function len(str) {
  return str.length
}

function addPrefix(str) {
  return '$' + str
}

const compose = (...fns) => fns.reduce((a, b) => (...args) => a(b(...args)))
console.log(addPrefix(len(sum('a', 'b', 'c'))))
let final = compose(
  addPrefix,
  len,
  sum
)
let r1 = final('a', 'b', 'c')
console.log(r1)

# 14. 能实现一个 JSONP 吗？

script 标签不遵循同源协议，可以用来进行跨域请求，优点就是兼容性好但仅限于 GET 请求

const jsonp = ({ url, params, callbackName }) => {
  const generateUrl = () => {
    let dataSrc = ''
    for (let key in params) {
      if (Object.prototype.hasOwnPrototype.call(params, key)) {
        dataSrc += `${key}=${params[key]}&`
      }
    }
    dataSrc += `callback=${callbackName}`
    return `${url}?${dataSrc}`
  }

  return new Promise((resolve, reject) => {
    const scriptEle = document.createElement('script')
    scriptEle.src = generatorUrl()
    document.body.appendChild(scriptEle)
    window[callbackName] = (data) => {
      resolve(data)
      document.removeChild(scriptEle)
    }
  })
}

# 15. 实现一下原生的 AJAX？

const getJson = function(url) {
  return new Promise((resolve, reject) => {
    const xhr = XMLHttpRequest
      ? new XMLHttpRequest()
      : new ActiveXObject('Microsoft.XMLHttp')
    xhr.open('GET', url, false)
    xhr.setRequestHeader('Accept', 'application/json')
    xhr.onreadystatechange = function() {
      if (xhr.readyState !== 4) return
      if (xhr.status === 200 || xhr.status === 304) {
        resolve(xhr.responseText)
      } else {
        reject(new Error(xhr.responseText))
      }
    }
    xhr.send()
  })
}

# 16. 实现数组原型方法？

• forEach

  // forEach() 方法接受三个参数，没有返回值
  var arr = [1, 2, 3, 4, 5]
  arr.forEach(function(item, index, array) {
    //执行某些操作
  })
  
  Array.prototype.forEach = function(fn, context) {
    context = context || this
    if (typeof fn !== 'function') {
      throw new TypeError(fn + 'is not a function')
    }
    for (var i = 0; i < this.length; i++) {
      fn.call(context, this[i], i, this)
    }
  }
  

• map

  function myMap(arr, callback) {
    if (!arr.length || !Array.isArray(arr) || typeof callback !== 'function') {
      return []
    } else {
      const result = []
      for (let i = 0; i < arr.length; i++) {
        const item = arr[i]
        result.push(callback(item, i, arr))
      }
      return result
    }
  }
  let arr = [1, 2, 3, 4, 5]
  const res = myMap(arr, (item, index, arr) => {
    return item + 'aa'
  })
  console.log(res) // ["1aa", "2aa", "3aa", "4aa", "5aa"]
  

• filter

  function myFilter(arr, callback) {
    if (!arr.length || !Array.isArray(arr) || typeof callback !== 'function') {
      return []
    } else {
      const result = []
      for (let i = 0; i < arr.length; i++) {
        const item = arr[i]
        if (callback(item, i, arr)) {
          result.push(item)
        }
      }
      return result
    }
  }
  let arr = [1, 2, 3, 4, 5]
  const res = myFilter(arr, (item, index, arr) => {
    console.log(item, index, arr)
    return item % 2 !== 0
  })
  console.log(res) // [1, 3, 5]
  

• reduce

  // 实现reduce
  Array.prototype.reduce = function(callback, prev) {
    for (let i = 0; i < this.length; i++) {
      if (!prev) {
        prev = callback(this[i], this[i + 1], i + 1, this)
        i++ // 下次从3开始
      } else {
        prev = callback(prev, this[i], i, this)
      }
    }
    return prev
  }
  

# 17. 实现 Object.create & Object.assign？

• Object.assign(target,…source) 方法用于将所有可枚举的属性的值从一个或多个源对象复制到目标对象。它将返回目标对象。

  function assign(target, source) {
    if (arguments.length < 2) {
      return target
    }
    let sources = [...arguments].slice(1)
    sources.forEach((element) => {
      for (let i in element) {
        if (Object.prototype.hasOwnProperty.call(element, i)) {
          target[i] = element[i]
        }
      }
    })
    return target
  }
  

• Object.create(proto,[propertiesObject]) 方法使用指定的原型对象和其属性创建了一个新的对象。

  // Object.create方法创建一个空对象，然后将空对象的__proto__ = proto，如果还有propertiesObject参数的话，就进行object.assign类似的操作，把属性赋上去。
  function create(proto) {
    let obj = {}
    if (arguments.length === 0) {
      return obj
    } else {
      obj.__proto__ = proto
      // 传入参数中的对象会进行覆盖obj内的属性
      if (arguments.length > 1) {
        let args = [...arguments].slice(1)
        args.forEach((element) => {
          for (let i in element) {
            if (Object.prototype.hasOwnProperty.call(element, i)) {
              obj[i] = element[i]
            }
          }
        })
      }
    }
    return obj
  }
  

# 18. 手写 Promise？

• Promise

  const PENDING = 'PENDING' // 等待态
  const FULFILLED = 'FULFILLED' // 成功态
  const REJECTED = 'REJECTED' // 失败态
  
  // 该方法核心就是判断x
  const resolvePromise = (promise2, x, resolve, reject) => {
    // 判断x和promise2是不是同一个人，是则报错
    if (promise2 === x) {
      return reject(new TypeError('Chaining cycle detected for promise #<promise>'))
    }
    let called // 内部测试的时候，成功和失败都调用
    if (x !== null && (typeof x === 'object' || typeof === 'function')) { // 对象
      try {
        let then = x.then
        if (typeof then === 'function') {
          then.call(x, (y) => {
            // y可能还是一个promise, 递归调用
            if (called) {
              return
            }
            called = true
            resolvePromise(promise2, y, resolve, reject)
          }, (r) => {
            if (called) {
              return
            }
            called = true // 防止多次调用成功和失败
            reject(r)
          })
        } else {
          resolve(x) // {then: 1} 是一个普通对象
        }
      } catch(error => {
        if (called) {
          return
        }
        called = true
        reject(error)
      })
    } else { // 普通值
      resolve(x)
    }
  }
  
  class Promise {
    constructor(executor) {
      if (typeof executor !== 'function') {
        throw new TypeError(`Promise resolver ${executor} is not a function`)
      }
      this.status = PENDING // 初始状态
      this.value = undefined // 成功的值
      this.reason = undefined // 失败的原因
  
      this.onResolvedCallbacks = [] // 成功的回调函数的数组
      this.onRejectedCallbacks = [] // 失败的回调函数的数组
  
      // 成功函数
      let resolve = (value) => {
        if (this.status === PENDING) {
          // 状态只能从等待态变成成功态
          this.value = value
          this.status = FULFILLED
          this.onResolvedCallbacks.forEach((fn) => fn()) // 发布
        }
      }
  
      // 失败函数
      let reject = (reason) => {
        if (this.status === PENDING) {
          this.reason = reason
          this.status = REJECTED
          this.onResolvedCallbacks.forEach((fn) => fn())
        }
      }
      try {
        executor(resolve, reject) // 立即执行
      } catch (error) {
        reject(error)
      }
    }
    then(onfulfilled, onrejected) {
      onfulfilled =
        typeof onfulfilled === 'function' ? onfulfilled : (val) => val
      onrejected =
        typeof onrejected === 'function'
          ? onrejected
          : (err) => {
              throw err
            }
      let promise2 = new Promise((resolve, rejected) => {
        // 同步情况
        if (this.status === FULFILLED) {
          setTimeout(() => {
            try {
              let x = onfulfilled(this.value)
              resolvePromise(promise2, x, resolve, reject)
            } catch(error) {
              reject(error)
            }
          }, 0)
        }
  
        if (this.status === REJECTED) {
          setTimeout(() => {
            try {
              let x = onrejected(this.reason)
              resolvePromise(promise2, x, resolve, reject)
            } catch(error => {
              reject(error)
            })
          }, 0)
        }
  
        // 异步情况
        if (this.status === PENDING) {
          this.onResolvedCallbacks.push(() => {
            setTimeout(() => {
              try {
                let x = onfulfilled(this.value)
                resolvePromise(promise2, x, resolve, reject)
              } catch(error => {
                reject(error)
              })
            }, 0)
          })
  
          this.onRejectedCallbacks.push(() => {
            setTimeout(() => {
              try {
                let x = onRejected(this.reason)
                resolvePromise(promise2, x, resolve, reject)
              } catch(error => {
                reject(error)
              })
            }, 0)
          })
        }
      })
  
      return promise2
    }
  }
  

• isPromise

  function isPromise(value) {
    if (
      typeof value !== null &&
      (typeof value === 'object' || typeof value === 'function')
    ) {
      if (typeof value.then === 'function') {
        return true
      }
    } else {
      return false
    }
  }
  

• resolve

• reject

• all 返回一个 promise 对象，只有当所有 promise 都成功时返回的 promise 状态才成功

  function all(promises) {
    return new Promise((resolve, reject) => {
      if (!Array.isArray(promises)) {
        throw new TypeError('promises must be a array')
      }
      let result = [] // 存放结果
      let count = 0 // 记录有几个resolved
  
      function processData(key, value) {
        result[key] = value
        if (++count === promises.length) {
          resolve(result)
        }
      }
      for (let i = 0; i < promises.length; i++) {
        let current = promises[i]
        if (isPromise(current)) {
          current.then((data) => {
            processData(i, data)
          }, reject)
        } else {
          processData(i, current)
        }
      }
    })
  }
  

  缺陷：在并发请求中，只有有一个请求错误，promise 的状态就是 reject

• race

• allSettled

  Promise.all 需要所有 promise 都成功时才 resolve 或者有一个失败时即 reject

  Promise.allSettled 只关心所有 promise 是不是都被 settle 了，不管其是 rejected 状态的 promise，还是非 rejected 状态(即 fulfilled)的 promise, 我都可以拿到它的最终状态并对其进行处理

  • Promise.allSettled 的结果数组中可能包含以下两种格式的数据

    1. {status:"fulfilled", value:result} 对于成功的响应
    2. {status:"rejected", reason:error} 对于 error

    function allSettled(promises) {
      return new Promise((resolve, reject) => {
        let result = [] // 存放运行的结果
        let index = 0 // 调用的次数和传入的参数个数一直的时候，resolve
        function processData(key, obj) {
          result[key] = obj
          if (++index === promises.length) {
            resolve(result)
          }
        }
        for (let i = 0; i < promises.length; i++) {
          let current = promises[i]
          if (isPromise(current)) {
            current.then(
              (data) => {
                let obj = {
                  status: 'fulfilled',
                  value: data,
                }
                processData(i, obj)
              },
              (err) => {
                let obj = {
                  status: 'rejected',
                  value: err,
                }
                processData(i, obj)
              }
            )
          } else {
            let obj = {
              status: 'fulfilled',
              value: current,
            }
            processData(i, obj)
          }
        }
      })
    }
    

# 19. 排序？

• 冒泡排序

  /**
   * 具体算法描述如下：
   * 1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个
   * 2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数
   * 3. 针对所有的元素重复以上的步骤，除了最后一个
   * 4. 重复步骤1~3，直到排序完成
   */
  function BubbleSort(arr) {
    for (let i = 0; i < arr.length; i++) {
      for (let j = 0; j < arr.length - 1 - i; j++) {
        if (arr[j] > arr[j + 1]) {
          // 相邻元素两两对比
          const temp = arr[j] // 元素交换
          arr[j] = arr[j - 1]
          arr[j - 1] = temp
        }
      }
    }
    return arr
  }
  var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
  console.log(bubbleSort(arr)) //[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
  

• 选择排序 它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

  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 arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
  console.log(selectionSort(arr)) //[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
  

• 插入排序 它的工作原理: 是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

  /**
   * 具体算法描述如下：
   * 1. 从第一个元素开始，该元素可以认为已经被排序
   * 2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
   * 3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
   * 4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
   * 5. 将新元素插入到该位置后
   * 6. 重复步骤2~5
   */
  
  function insertionSort(arr) {
    if (Object.prototype.toString.call(arr).slice(8, -1) === 'Array') {
      for (var i = 0; i < arr.length; i++) {
        var key = arr[i]
        var j = i - 1
        while (j >= 0 && arr[j] > key) {
          arr[j + 1] = arr[j]
          j--
        }
        arr[j + 1] = key
      }
      return arr
    } else {
      return 'arr is not a array'
    }
  }
  

• 快速排序 快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

  /**
   * 快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：
   * 1. 从数列中挑出一个元素，称为 "基准"（pivot）
   * 2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作
   * 3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序
   */
  function quickSort(arr, left, right) {
    if (
      Object.prototype.toString.call(arr).slice(8, -1) === 'Array' &&
      typeof left === 'number' &&
      right === 'number'
    ) {
      if (left < right) {
        var x = arr[right],
          i = left - 1,
          temp
        for (let j = left; j <= right; j++) {
          if (arr[j] <= x) {
            i++
            temp = arr[i]
            arr[i] = arr[j]
            arr[j] = temp
          }
        }
        quickSort(arr, left, i - 1)
        quickSort(arr, i + 1, right)
      }
      return arr
    } else {
      return 'array is not an Array or left or right is not a number!'
    }
  }
  var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
  console.log(quickSort(arr, 0, arr.length - 1)) //[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
  

• 归并排序 归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为 2-路归并。

  /**
   * 具体算法描述如下：
   * 1. 把长度为n的输入序列分成两个长度为n/2的子序列
   * 2. 对这两个子序列分别采用归并排序
   * 3. 将两个排序好的子序列合并成一个最终的排序序列
   */
  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
  }
  var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
  console.log(mergeSort(arr))
  

• 希尔排序 希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。是简单插入排序的改进版；它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序

  /**
   * 先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：
   * 1. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1
   * 2. 按增量序列个数k，对序列进行k 趟排序
   * 3. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度
   */
  function shellSort(arr) {
    var len = arr.length,
      temp,
      gap = 1
    console.time('希尔排序耗时:')
    while (gap < len / 5) {
      //动态定义间隔序列
      gap = gap * 5 + 1
    }
    for (gap; gap > 0; gap = Math.floor(gap / 5)) {
      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
      }
    }
    console.timeEnd('希尔排序耗时:')
    return arr
  }
  var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
  console.log(shellSort(arr)) //[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
  

# 20. 类数组转化为数组的方法？

类数组是具有 length 属性，但不具有数组原型上的方法。常见的类数组有 arguments、DOM 操作方法返回的结果。

• 方式一、Array.from()

  Array.from(document.querySelectorAll('div'))
  

• 方式二、Array.prototype.slice.call()

  Array.prototype.slice.call(document.querySelectorAll('div'))
  

• 方式三、扩展运算符

  ;[...document.querySelectorAll('div')]
  

• 方式四、利用 concat()

  Array.prototype.concat.apply([], document.querySelectorAll('div'))
  

• 方式五、利用 splice

  Array.prototype.splice(document.querySelectorAll('div'), 0)
  

# 21. 列表转成树形结构 & 树形结构转成列表？

let arr = [
  { id: 0, name: '1', parent: -1, childNode: [] },
  { id: 1, name: '1', parent: 0, childNode: [] },
  { id: 99, name: '1-1', parent: 1, childNode: [] },
  { id: 111, name: '1-1-1', parent: 99, childNode: [] },
  { id: 66, name: '1-1-2', parent: 99, childNode: [] },
  { id: 1121, name: '1-1-2-1', parent: 112, childNode: [] },
  { id: 12, name: '1-2', parent: 1, childNode: [] },
  { id: 2, name: '2', parent: 0, childNode: [] },
  { id: 21, name: '2-1', parent: 2, childNode: [] },
  { id: 22, name: '2-2', parent: 2, childNode: [] },
  { id: 221, name: '2-2-1', parent: 22, childNode: [] },
  { id: 3, name: '3', parent: 0, childNode: [] },
  { id: 31, name: '3-1', parent: 3, childNode: [] },
  { id: 32, name: '3-2', parent: 3, childNode: [] },
]

function arrayToTree = (arr, parentId) => {
  // 判断是否是顶层节点，如果是就返回。不是的话就判断是不是自己要找的子节点
  const filterArr = arr.filter(item => {
    return parentId === undefined ? item.parent === -1 ? item.parent === parentId
  })
  // 进行递归调用把子节点加到父节点 的 childNode里面去
  filterArr.map(item => {
    item.childNode = arrayToTree(arr, item.id)
    return item
  })
  return filterArr
}
arrayToTree(arr)

# 22. 大数相加？

JS 在存放整数的时候是有一个安全范围的，一旦数字超过这个范围便会损失精度。所以，我们要用字符串来表示数据！（不会丢失精度）

提示：JS 中整数的最大安全范围可以查到是：9007199254740991

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
}
add(a, b) // 结果为：1243575099254740990

# 23. 数组扁平化 flatten？

数组扁平化是指将一个多维数组变为一个一维数组

const arr = [1, [2, [3, [4, 5]]], 6]
// => [1, 2, 3, 4, 5, 6]

• 方法一、使用 flat()

  const res = arr.flat(Infinity)
  

• 方法二、使用正则

  const res = JSON.stringify(arr)
    .replace(/\[|\]/g, '')
    .split(',')
  数据类型都会变为字符串: `['1', '2', '3', '4', '5', '6']`
  
  正则改良版本
  // JSON.stringify(arr).replace(/\[|\]/g, '') // '1,2,3,4,5,6'
  const res = JSON.parse('[' + JSON.stringify(arr).replace(/\[|\]/g, '') + ']')
  

• 方法三、使用 reduce

  const flatten = (arr) => {
    return arr.reduce((pre, cur) => {
      return pre.concat(Array.isArray(cur) ? flatten(cur) : cur)
    }, [])
  }
  const res = flatten(arr)
  

• 方式四、函数递归

  const res = []
  const flatten = (arr) => {
    for (let i = 0; i < arr.length; i++) {
      if (Array.isArray(arr[i])) {
        flatten(arr[i])
      } else {
        res.push(arr[i])
      }
    }
  }
  flatten(arr)
  

• 方式五、toString

  function flatten(arr) {
    return arr.toString().split(',') // 有缺陷，toString 后无法保持之前的类型
  }
  

• 方式六、rest 运算符

  function flatten(arr) {
    while (arr.some((item) => Array.isArray(item))) {
      // concat方法本身就会把参数中的数组展开，相当于[].concat('1', 2, [3, 4])
      arr = [].concat(...arr)
    }
    return arr
  }
  

扩展：实现一个对象的 flatten 方法

const obj = {
 a: {
        b: 1,
        c: 2,
        d: {e: 5}
    },
 b: [1, 3, {a: 2, b: 3}],
 c: 3
}

flatten(obj) 结果返回如下
// {
//  'a.b': 1,
//  'a.c': 2,
//  'a.d.e': 5,
//  'b[0]': 1,
//  'b[1]': 3,
//  'b[2].a': 2,
//  'b[2].b': 3
//   c: 3
// }

function isObject(val) {
  return typeof val === 'object' && val !== null
}

function flatten(obj) {
  if (!isObject(obj)) { // 不是对象直接返回
    return
  }
  let res = {} // 存放结果
  const dfs = (cur, prefix) => {
    if (isObject(cur)) {
      if (Array.isArray(cur)) { // 如果是数组
        cur.forEach((item, index) => {
          dfs(item, `${prefix}[${index}]`)
        })
      } else { // 普通对象
        for(let key in cur) {
          dfs(cur[key], `${prefix}${prefix ? ".": ""}${key}`)
        }
      }
    } else {
      res[prefix] = cur
    }
  }
  dfs(obj, "")
  return res
}
flatten()

# 24. 算法 -> 全排列？

给定一个字符串，输出该字符串所有排列的可能。如输入“abc”，输出“abc,acb,bca,bac,cab,cba”。

• 思路：定义一个数组存放全排列的情况并返回。判断输入的字符串是否为单个字符串的情况。是，返回其本身。不是，则遍历字符串中的每一个元素，并将字符串中除了该元素的其他元素及你想全排列

  function fullPermutation(str) {
    var result = []
    if (str.length > 1) {
      for (let i = 0; i < str.length; i++) {
        var left = str[i] // 当前元素
        // 除了当前元素的其他元素组合
        var rest = str.slice(0, i) + str.slice(i + 1, str.length)
        // 上一次递归返回的全排列
        var preResult = fullPermutation(rest)
        // 结合在一起
        for (var j = 0; j < preResult.length; j++) {
          var temp = left + preResult[j]
          result.push(temp)
        }
      }
    } else if (str.length === 1) {
      result.push(str)
    }
    return result
  }
  

# 25. 算法 -> 二分查找？

二分搜索法，也称折半搜索，是一种在有序数组中查找特定元素的搜索算法。

• 实现步骤：

  1. 首先从数组中间开始查找对比，若相等则找到，直接返回中间元素的索引
  2. 若查找值小于中间值，则在小于中间值的那一部分执行步骤 1 的操作
  3. 若查找值大于中间值，则在大于中间值的那一部分执行步骤 1 的操作
  4. 否则，返回结果为查不到，返回-1

• 实现方法：

  1. 非递归方式，采用 while 方式，判断是否符合要求

  /**
   * @param {*} arr 已排好的数组
   * @param {*} key 想要查找的值
   */
  function binary_search1(arr, key) {
    var low = 0,
      high = arr.length - 1
    while (low <= high) {
      // var mid = parseInt((low + high) / 2); // 得到中间的数
      var mid = Math.floor((low + high) / 2) // 得到中间的数
      if (key === arr[mid]) {
        return mid
      } else if (key > arr[mid]) {
        // 说明在右边
        low = mid + 1
      } else if (key < arr[mid]) {
        // 说明在左边
        high = mid - 1
      } else {
        return -1
      }
    }
  }
  

  2. 递归方式，采用 if 方式，依次递归，找到相应的值

  function binary_search2(arr, key) {
    return search(arr, key, 0, arr.length - 1)
    /**
     * @param {*} arr 已排好的数组
     * @param {*} key 想要查找的值
     * @param {*} low 第一个值的索引
     * @param {*} high 最后一个值的索引
     * @returns
     */
    function search(arr, key, low, high) {
      if (low > high) {
        return -1
      }
      var mid = Math.floor((low + high) / 2)
      if (key === arr[mid]) {
        return mid
      } else if (key > arr[mid]) {
        // 说明在右边
        return search(arr, key, mid + 1, high)
      } else if (key < arr[mid]) {
        // 说明在左边
        return search(arr, key, low, high - 1)
      }
    }
  }
  

时间复杂度：O(log2n) => O(logn).优点：比较次数少，查找速度快，平均性能好。缺点：要求待查表为有序表，且插入删除困难。结论：适用于不经常变动而查找频繁的有序列表。

# 26. 二叉树

深度优先遍历 & 广度优先遍历

# 27. 动态规划

# 28. 合并区间

https://leetcode-cn.com/problems/merge-intervals/

# 29. 实现一个反转二叉树

# 30. 一个迷宫，最短路径生成

# 31. 实现单向链表反转

# 32. twoSum 得到两个数的之后等于 target

方式一：双重循环

const towSum = (nums, target) => {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j]
      }
    }
  }
}

方式二：Map 取差值

const towSum = (nums, target) => {
  const map = {}
  for (let i = 0; i < nums.length; i++) {
    const value = nums[i]
    const diff = target - value // 计算差值
    if (typeof map[diff] !== 'undefined') {
      return [map[diff], i]
    } else {
      map[value] = i
    }
  }
}

# 33. 实现 add(1)(2)(3)

函数柯里化（curry）是函数式编程里面的概念。只传递给函数一部分参数来调用它，让它返回一个函数去处理剩下的参数。

const add = (x) => (y) => (z) => x + y + z
console.log(add(1)(2)(3))

扩展: 如果要实现：add(1, 2, 3); add(1, 2)(3); add(1)(2, 3);这种呢？

主要思路：要判断当前传入函数的参数个数(args.length)是否大于等于原函数所需参数个数(fn.length), 如果是，则执行当前函数。如果是小于，则返回一个函数

const curry = (fn, ...args) => {
  // 函数的参数个数可以通过函数的.length属性来访问
  args.length >= fn.length
    ? fn(...args)
    : (..._args) => curry(fn, ...args, ..._args)
}
const add = (x, y, z)
const add1 = curry(add)
console.log(add1(1, 2, 3))
console.log(add1(1, 2)(3))

• 柯里化有什么作用：
  1. 参数复用（传入一个参数就可以得出结果，复用之前的参数）
  2. 提前返回（每次调函数时，只接受部分参数，并返回一个函数）
  3. 延迟执行（直到传递所有参数为止）

# 34. 实现千位分隔符?

千位分隔符格式的规则是数字的整数部分每三位一组，以“，”分节。小数部分不分节 。

示例：19,351,235.235767

• 方式一、实现思路是将数字转换为字符数组，再循环整个数组， 每三位添加一个分隔逗号，最后再合并成字符串。

  function numFormat(num) {
    num = num.toString().split('.') // 分割小数点
    var arr = num[0].split('').reverse() // 转换成字符数组并且倒叙排列
    var res = [] // 存放结果
    for (var i = 0, len = arr.length; i < len; i++) {
      if (i % 3 === 0 && i !== 0) {
        res.push(',') // 添加分隔符
      }
      res.push(arr[i])
    }
    res.reverse() // 再次倒叙为正确的顺序
    if (num[1]) {
      // 如果有小数，添加小数部分
      res = res.join('').concat('.' + num[1])
    } else {
      res = res.join('')
    }
    return res
  }
  
  console.log(numFormat(673439.4542)) // 673,439.4542
  console.log(numFormat(1234567894532)) // 1,234,567,894,532
  

• 方式二、JS 中自带的函数 toLocaleString

toLocaleString() 方法返回这个数字在特定语言环境下的表示字符串。

语法： numObj.toLocaleString([locales [, options]])locale 为可选参数，它用来指定格式化对象时使用的语言环境。默认是浏览器当前的语言环境。options 也是一个可选参数，它是对象格式，用来设置对象格式化样式的一些配置属性。

```js
var a = 1234567894532
var b = 673439.4542

console.log(a.toLocaleString()) // 1,234,567,894,532
console.log(b.toLocaleString()) // 673,439.4542
```

1. `Date.prototype.toLocaleString()`

  ```js
  var date = new Date()
  console.log(date.toLocaleString('zh')) // 2019-5-12 14:29:34
  console.log(date.toLocaleString('en')) // 5/12/2019, 2:29:34 PM
  ```

2. `Number.prototype.toLocaleString()`
  ```js
  const num = 2444222
  console.log(num.toLocaleString('zh', { style: 'decimal' })) // 2,444,222
  console.log(num.toLocaleString('zh', { style: 'percent' })) // 244,422,200%
  // style用来设置格式化时使用的样式，它有三个值：decimal表示纯数字，percent表示百分比格式，currency表示货币。默认值是decimal。
  ```

• 方式三、使用正则表达式和replace函数

  function numFormat1(num) {
    var res = num.toString().replace(/\d+/, function(n) {
      // 先提取整数部分
      return n.replace(/(\d)(?=(\d{3})+$)/g, function($1) {
        return $1 + ','
      })
    })
    return res
  }
  
  console.log(numFormat1(673439.4542)) // 673,439.4542
  console.log(numFormat1(1234567894532)) // 1,234,567,894,532
  

# 35. 判断是否是回文数?

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。

• 一些特殊的情况：

  1. 0-9 的数字，都可以称为回文
  2. 不等于 0，且尾数是 0 的数字，都不是回文
  3. 负数都不是回文

• 方式一、字符串的转换

  // 1. 使用高阶函数，思路：先将数字转成字符串A，再经过变成数组，数组反转，数组变成字符串B，比较字符串A和B
  var isPalindrome = function(x) {
    if (x < 0) return false
    let str = '' + x
    return (
      Array.from(str)
        .reverse()
        .join('') === str
    )
  }
  // 2. 以中间数为节点，判断左右两边首位是否相等
  var isPalindrome = function(x) {
    if (x < 0 || (x !== 0 && x % 10 === 0)) {
      return false
    } else if (0 <= x && x < 10) {
      return true
    }
    x = '' + x
    for (let i = 0; i < x.length; i++) {
      if (x[i] !== x[x.length - i - 1]) {
        return false
      }
    }
    return true
  }
  

# 36. 判断一个数是否是素数?

素数：又叫质数，在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数。即只能被 1 和它本身整除的数就是素数

function isPrime(n) {
  if (n === 0 || n === 1) {
    return false
  }
  if (n === 2) {
    return true
  }
  for (var i = 2; i < Math.sqrt(n); i++) {
    if (n % i === 0) {
      return false
    }
    return true
  }
}

• 输出 n 内所有的素数

function primeN(n) {
  var flag = 0
  var result = []
  if (n === 0 || n === 1) {
    result = []
  } else if (n === 2) {
    result = [2]
  } else if (n === 3 || n === 4) {
    result = [2, 3]
  } else {
    result.push(2, 3)
    for (var i = 5; i <= n; i++) {
      for (var j = 2; j <= Math.sqrt(i); j++) {
        if (i % j === 0) {
          flag = 1
          break
        } else {
          flag = 0
        }
      }
      if (flag === 0) {
        result.push(i)
      }
    }
  }
  return result
}

Math.sqrt()方法返回一个数的平方根。如果传递的参数为负，则 Math.sqrt()返回 NaN

# 37. 菲波拉契数

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1

function fibonacci(n) {
  if (n < 2) {
    return n
  }
  let p = 0,
    q = 0,
    r = 1
  for (let i = 2; i <= n; i++) {
    p = q
    q = r
    r = p + q
  }
  return r
}

时间复杂度：O(n) 空间复杂度：O(1)。

# 38. 线性表 -> 合并二维有序数组成一维有序数组

剑指 Offer 25. 合并两个排序的链表

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

// 示例1：
// 输入：1->2->4, 1->3->4
// 输出：1->1->2->3->4->4

// 限制：
// 0 <= 链表长度 <= 1000

• 实现步骤：
  1. 获取 head1 和 head2 中数据值较小的节点，并设置为合并后链表的首节点。
  2. 通过循环，依次获得链表 1 和链表 2 中数据较小的节点，并添加到合并后链表的末尾。
  3. 当步骤 2 执行完毕，如果某一个链表中首节点不为 null, 则将该链表首节点及其之后的节点添加到合并后链表的末尾。

var mergeTwoLists = function(l1, l2) {
  let current = new ListNode()
  let dummy = current

  while (l1 !== null && l2 !== null) {
    if (l1.val < l2.val) {
      current.next = l1
      l1 = l1.next // 指针向后移动
    } else {
      current.next = l2
      l2 = l2.next
    }
    current = current.next
  }

  // 还要考虑，l1或者l2比较完了，另一个链表中的数直接添加
  if (l1 !== null) {
    // l1还剩
    current.next = l1
  }

  if (l2 !== null) {
    current.next = l2
  }

  return dummy.next // dummy会从头返回， dummy.next是为了跳过空节点，直接从最小值返回
}

function merge(l1, l2) {
  if (!l1) return l2
  if (!l2) return l1
  if (l1.val < l2.val) {
    l1.next = merge(l1.next, l2)
    return l1
  } else {
    l2.next = merge(l1, l2.next)
    return l2
  }
}

# 39. 链表 -> 反转链表

剑指 Offer 24. 反转链表

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

// 示例
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
思路：
分别定义多个指针。temp节点用于保存当前节点的下一个位置，cur指针为当前节点，pre指针为当前节点的前面部分，初始值为null
假设要反转的链表结构为 1 -> 2 -> 3 -> 4 -> 5
在最开始我们设置头节点为head，此时cur节点为head，已知cur下一步会往后移一位，此时我们用temp前去保存
这时将cur节点的下一个指向断开，指向pre，此时pre为 1 -> null
将pre节点指向cur（连接上去）
让cur等于刚刚temp所保存的部分

如此反复

var reverseList = function(head) {
  let pre = null,
    cur = head
  let temp
  while (cur) {
    temp = cur.next
    cur.next = pre
    pre = cur
    cur = temp
  }
  return pre
}

# 40. 链表 -> 链表有环

var hasCycle = function(head) {
  if (head === null) {
    return false
  }
  let slow = head
  let fast = head
  while (fast.next !== null && fast.next.next !== null) {
    slow = slow.next // 走一步
    fast = fast.next.next // 走两步
    if (slow === fast) {
      return true
    }
  }
  return false
}

# 41. 堆栈队列 -> 判断括号字符串是否有效

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。 有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。

示例 1：
输入：s = "()"
输出：true

示例 2：
输入：s = "()[]{}"
输出：true

示例 3：
输入：s = "(]"
输出：false

示例 4：
输入：s = "([)]"
输出：false

示例 5：
输入：s = "{[]}"
输出：true

• 根据题目推断出：
  1. 字符串 s 的长度一定是偶数（一对对匹配）
  2. 右括号 前面一定跟着 左括号，才符合匹配条件，具备对称性
  3. 右括号 前面如何不是 左括号，一定不是有效的括号

方式一：

输入：s = "{[()]}"

第一步：可以消除()这一对，结果 s 还剩{[]}

第二步: 可以消除[]这一对，结果 s 还剩{}

第三步: 可以消除{}这一对，结果 s 还剩'' 所以符合题意返回 true

const isValid = (s) => {
  let len = s.length
  s = s
    .replace('()', '')
    .replace('{}', '')
    .replace('[]', '')
  if (s.length === len) {
    return len === 0
  }
}

方式二、栈，特点：后进先出

输入：s = "{[()]}"

第一步：读取 ch = {，属于左括号，入栈，此时栈内有{

第二步：读取 ch = [，属于左括号，入栈，此时栈内有{[

第三步：读取 ch = (，属于左括号，入栈，此时栈内有{[(

第四步：读取 ch = )，属于右括号，尝试读取栈顶元素(和)正好匹配，将(出栈，此时栈内还剩{[

第五步：读取 ch = ]，属于右括号，尝试读取栈顶元素[和]正好匹配，将[出栈，此时栈内还剩{

第六步：读取 ch = }，属于右括号，尝试读取栈顶元素{和}正好匹配，将{出栈，此时栈内还剩''

第七步：栈内只能''，s = "{[()]}"符合有效的括号定义，返回 true

const isValid = (s) => {
  if (!s) {
    // 空字符串符合条件
    return true
  }
  const leftToRight = {
    '(': ')',
    '{': '}',
    '[': ']',
  }
  const stack = []
  for (let i = 0, len = s.length; i < len; i++) {
    const ch = s[i]
    // 左括号
    if (leftToRight[ch]) {
      stack.push(ch)
    } else {
      // 右括号开始匹配
      // 1. 如果站内没有左括号，直接false
      // 2. 有数据但是栈顶元素不是当前的右括号
      if (!stack.length || leftToRight[stack.pop()] !== ch) {
        return false
      }
    }
  }
  // 最后检查栈内还有没有元素，有说明还有未匹配。则不符合
  return !stack.length
}

# 42. 返回数组中第 k 个最大元素

# 43. 实现字符串翻转

var reverseString = function(s) {
  for (var i = 0; i < s.length / 2; i++) {
    const temp = s[i]
    s[i] = s[s.length - i - 1]
    s[s.length - i - 1] = temp
  }
  return s
}

# 44. 实现 LRU 算法

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制 。 实现 LRUCache 类：

1. LRUCache(int capacity) 以正整数作为容量  capacity 初始化 LRU 缓存
2. int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
3. void put(int key, int value)  如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

题目要求的 1 和 2 相对简单，主要是条件 3，当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值。容量和条件 1 相呼应，关键是怎么理解最久未使用呢?

1. 读和写都是在使用数据
2. 假设不管是读还是写，我们都把对应的 key 值放到数组的末尾，那么是不是意味着数组的头部就是最久未使用的了呢？

数组 & 对象方式实现

var LRUCache = function(capacity) {
  this.keys = [] // 用数组记录读和写的顺序
  this.cache = {} // 用对象来保存key value的值
  this.capacity = capacity // 容量
}

LRUCache.prototype.get = function(key) {
  if (this.cache[key]) {
    // 如果存在
    remove(this.keys, key) // 先删除原来的位置
    this.keys.push(key) // 再将其移动到最后一个，保持最新访问
    return this.cache[key] // 返回值
  } else {
    return -1 // 不存在
  }
}

LRUCache.prototype.put = function(key, value) {
  if (this.cache[key]) {
    // 之前存在
    this.cache[key] = value // 存在的时候先更新值
    remove(this.keys, key) // 再删除原来的位置
    this.keys.push(key) // 最后再将其移动到最后一个，保持最新访问
  } else {
    // 之前不存在
    this.cache.push(key) // 直接加入
    this.cache[key] = value
    // 容量如果超过最大值，则删除最近最久未使用的（也就是数组第一个）
    if (this.keys.length > this.capacity) {
      removeCache(this.cache, this.keys, this.keys[0])
    }
  }
}

// 移除数组中的key
function remove(arr, key) {
  if (arr.length) {
    const index = arr.indexOf(key)
    if (index > -1) {
      return arr.splice(index, 1)
    }
  }
}

// 移除缓存中的key
function removeCache(cache, keys, key) {
  cache[key] = null // 删除缓存中的
  remove(keys, key) //
}

使用 Map 方式实现

var LRUCache = function(capacity) {
  this.cache = new Map()
  this.capacity = capacity
}

LRUCache.prototype.get = function(key) {
  if (this.cache.has(key)) {
    var value = this.cache.get(key)
    // 更新位置
    this.cache.delete(key)
    this.cache.set(key, value)
    return value
  } else {
    return -1
  }
}

LRUCache.prototype.put = function(key, value) {
  if (this.cache.has(key)) {
    // 已经存在，就先删除，再插入
    this.cache.delete(key)
  } else {
    // 没有存在
    // 插入数据先判断，size是否符合capacity
    // 如果size大于capacity，需要把最开始插入的数据删除
    // keys()方法得到一个可遍历对象,执行next()拿到一个形如{ value: 'xxx', done: false }的对象
    if (this.cache.size >= this.capacity) {
      this.cache.delete(this.cache.keys().next().value∂)
    }
  }
  this.cache.set(key, value)
}

# 44. 手写 call、apply、bind

# call 的实现原理

Function.prototype.myCall = function(context = window, ...args) {
  if (typeof this !== 'function') {
    throw new TypeError('not a function')
  }
  // context = Object(context) 暴力处理 ctx有可能传非对象
  const fn = Symbol('fn') // 用Symbol生成唯一的key
  context[fn] = this // 这里的this，即要调用的函数
  const res = context[fn](...args) // 将args展开，并且调用fn函数，此时fn函数内部的this也就是context了
  delete context[fn] // 用完之后，将fn从上下文context中删除
  return res
}

# apply 的实现原理

Function.prototype.myApply = function(context = window, args) {
  if (typeof this !== 'function') {
    throw new TypeError('not a function')
  }
  const fn = Symbol('fn')
  context[fn] = this
  const res = context[fn](...args)
  delete context[fn]
  return res
}

# bind 的实现原理

Function.prototype.myBind = function(context = window, ...args) {
  if (typeof this !== 'function') {
    throw new TypeError('not a function')
  }
  let self = this
  return function F() {
    // 考虑new的情况
    if (this instanceof F) {
      return new self(...args, ...arguments)
    } else {
      self.apply(context, [...args, ...arguments])
    }
  }
}

# 45. 实现 trim 方法

• 方式一：去除空格

  const trim = (str) => {
    return str.replace(/^\s*|\s*$/g, '')
  }
  

• 方式二：字符串提取

  const trim = (str) => {
    return str.replace(/^\s*(.*?)\s$/g, '$1')
  }
  

  .*？ 表示匹配任意字符到下一个符合条件的字符

# 46. 将虚拟 DOM 转换为真实 DOM？

{
  tag: 'DIV',
  attrs:{
  id:'app'
  },
  children: [
    {
      tag: 'SPAN',
      children: [
        { tag: 'A', children: [] }
      ]
    },
    {
      tag: 'SPAN',
      children: [
        { tag: 'A', children: [] },
        { tag: 'A', children: [] }
      ]
    }
  ]
}
把上诉虚拟Dom转化成下方真实Dom
<div id="app">
  <span>
    <a></a>
  </span>
  <span>
    <a></a>
    <a></a>
  </span>
</div>

// 真正的渲染函数
function _render(vnode) {
  // 如果是数字类型转化为字符串
  if (typeof vnode === "number") {
    vnode = String(vnode);
  }
  // 字符串类型直接就是文本节点
  if (typeof vnode === "string") {
    return document.createTextNode(vnode);
  }
  // 普通DOM
  const dom = document.createElement(vnode.tag);
  if (vnode.attrs) {
    // 遍历属性
    Object.keys(vnode.attrs).forEach((key) => {
      const value = vnode.attrs[key];
      dom.setAttribute(key, value);
    });
  }
  // 子数组进行递归操作 这一步是关键
  vnode.children.forEach((child) => dom.appendChild(_render(child)));
  return dom;
}