前端一万五 - 面试篇

// 该版本不符合A+规范，仅为简易版
// 核心思想，订阅发布
const PENDING = 'pending'
const RESOLVED = 'resolved'
const REJECTED = 'rejected'

function MyPromise(fn) {
  this.state = PENDING // 一开始 Promise 的状态应该是 pending
  this.value = null // value 变量用于保存 resolve 或者 reject 中传入的值

  this.resolvedCallbacks = []
  this.rejectedCallbacks = []

  function resolve(value) {
    if (this.state === PENDING) {
      this.state = RESOLVED
      this.value = value
      this.resolvedCallbacks.map(cb => cb(this.value))// 发布
    }
  }

  function reject(value) {
    if (this.state === PENDING) {
      this.state = REJECTED
      this.value = value
      this.rejectedCallbacks.map(cb => cb(this.value))// 发布
    }
  }

  try {
    fn(resolve.bind(this), reject.bind(this)) // 传入promise构造函数的参数(传入函数)
  } catch (e) {
    reject.bind(this)(e)
  }
}

MyPromise.prototype.then = function(onFulfilled, onRejected) {
  onFulfilled = typeof onFulfilled === 'function' ? onFulfilled : v => v
  onRejected = typeof onRejected === 'function' ? onRejected : r => { throw r }
  if (this.state === PENDING) {
    // then: 订阅，将then传入的函数保存到构造函数中声明的数组中，当执行resolve, reject的时候循环执行then函数传入的函数
    this.resolvedCallbacks.push(onFulfilled)
    this.rejectedCallbacks.push(onRejected)
  }
}

new MyPromise((resolve, reject) => {
  console.log('start1')
  setTimeout(() => {
    resolve(1)
  }, 100)
}).then(value => {
  console.log(value)
})

new MyPromise((resolve, reject) => {
  console.log('start2')
  setTimeout(() => {
    reject(2)
  }, 100)
}).then(value => {
  console.log(value)
}, err => {
  console.log('err:' + err)
})

Promise.myAll = (promises) => {
  const promiseResult = []
  return new Promise(function(resolve, reject) {
    let i = 0
    next() // 开始promises数组中的每一个promise加上一个then和catch
    function next() {
      promises[i].then(function(res) {
        promiseResult.push(res) // 存储每次得到的结果
        i++
        if (i === promises.length) { // 如果函数数组中的函数都执行完，便resolve
          resolve(promiseResult)
        } else {
          next() // 执行完一个promise的then, 继续执行下一个promise的then
        }
      }).catch(e => {
        reject(e) // 只要有一个promise到了rejected态，promise.all就reject了
      })
    }
  })
}

function escape(str) {
  str = str.replace(/&/g, '&')
  str = str.replace(/</g, '&lt;')
  str = str.replace(/>/g, '&gt;')
  str = str.replace(/"/g, '&quto;')
  str = str.replace(/'/g, '&#39;')
  str = str.replace(/`/g, '&#96;')
  str = str.replace(/\//g, '&#x2F;')
  return str
}

const url = 'http://i7xy.cn/?a=1&b=2&c=3&d=4'

function get() {
  const re = /[?&](\w+?)=(\w+?)/g
  const params = {}
  while (result = re.exec(url)) {
    params[result[1]] = result[2]
  }
  return params
}

console.log('log => : get(url)', get(url))

var result = "12345678".replace(/(?=\d{3}$)/g, ","); // => "12345,678"
// (?=\d{3}$) 匹配 \d{3}$ 前面的位置。而 \d{3}$ 匹配的是目标字符串最后那 3 位数字。

var result = "112345678".replace(/(?=(\d{3})+$)/g, ","); // => ",112,345,678"

var result = "112345678".replace(/(?!^)(?=(\d{3})+$)/g, ","); // => "112,345,678"

var result = "12345678 123456789".replace(/(?!\b)(?=(\d{3})+\b)/g, ",");
// => "12,345,678 123,456,789"
// (?!\b) = \B so: /\B(?=(\d{3})+\b)/g

const card = '12345678901234567890'
console.log(card.replace(/(\d{4})(?=\d)/g, '$1_')) // (?=\d)表示后面位置是数字, 最后没有数字了就不要加_

Function.prototype.myCall = function(context) {
  if (typeof this !== 'function') {
    throw new TypeError('Error')
  }
  context = context || window // 默认指向为windows
  const fn = Symbol('fn') // 防止和现有属性重复
  context[fn] = this
  const args = [...arguments].slice(1) // 取从index=1开始的所有参数
  const result = context[fn](...args)
  delete context[fn]
  return result
}

Function.prototype.myApply = function(context) {
  if (typeof this !== 'function') {
    throw new TypeError('Error')
  }
  context = context || window
  context.fn = this
  let result
  // 处理参数和 call 有区别
  if (arguments[1]) {
    result = context.fn(...arguments[1]) // apply参数通过数组传递
  } else {
    result = context.fn()
  }
  delete context.fn
  return result
}

Function.prototype.myBind = function (context) {
  if (typeof this !== 'function') {
    throw new TypeError('Error')
  }
  const _this = this
  const args = [...arguments].slice(1)
  // 返回一个函数
  return function F() {
    // 因为返回了一个函数，我们可以 new F()，所以需要判断
    if (this instanceof F) {
      return new _this(...args, ...arguments)
    }
    // 对于直接调用来说，这里选择了 apply 的方式实现，但是对于参数需要注意以下情况：因为 bind 可以实现类似这样的代码 f.bind(obj, 1)(2)，所以我们需要将两边的参数拼接起来，于是就有了这样的实现 args.concat(...arguments)
    return _this.apply(context, args.concat(...arguments))
  }
}

Function.prototype.myBind = function(context, ...args) {
  if (typeof this !== 'function') {
    throw new TypeError('Error')
  }
  const fn = Symbol('fn')
  context[fn] = this
  return function F() {
    if (this instanceof F) {
      return new context[fn](...args, ...arguments)
    } else {
      return context[fn](args.concat(arguments))
    }
  }
}

function create() {
  const obj = {}
  const Con = [].shift.call(arguments) //获取构造函数(第一个参数)
  obj.__proto__ = Con.prototype
  const result = Con.apply(obj, arguments) // 执行构造函数
  return result instanceof Object ? result : obj // 如果构造函数返回了一个对象，则返回该对象作为this指向
}

function foo() {
  this.name = 'arley'
}

function foo2() {
  return {
    name: 'fe',
    age: 19
  }
}
const s1 = create(foo)
const s2 = create(foo2)

console.log('log => : s1', s1)
console.log('log => : s2', s2)

function Parent(value) { // Parent还会被执行两次
  this.val = value
}
Parent.prototype.getValue = function() {
  console.log(this.val)
}
function Child(value) {
  Parent.call(this, value)
}
Child.prototype = new Parent()

const child = new Child(1)

child.getValue() // 1
child instanceof Parent // true

function Parent(value) {
  this.val = value
}
Parent.prototype.getValue = function() {
  console.log(this.val)
}

function Child(value) {
  Parent.call(this, value) // 继承属性
}
Child.prototype = Object.create(Parent.prototype, { // 继承方法
  constructor: {
    value: Child,
    enumerable: false,
    writable: true,
    configurable: true
  }
})

const child = new Child(1)

child.getValue() // 1
child instanceof Parent // true

// func是用户传入需要防抖的函数
// wait是等待时间
const throttle = (func, wait = 50) => {
  // 上一次执行该函数的时间
  let lastTime = 0
  return function(...args) {
    // 当前时间
    let now = +new Date()
    // 将当前时间和上一次执行函数时间对比
    // 如果差值大于设置的等待时间就执行函数
    if (now - lastTime > wait) {
      lastTime = now
      func.apply(this, args)
    }
  }
}

setInterval(
  throttle(() => {
    console.log(1)
  }, 500),
  1
)

// func是用户传入需要防抖的函数
// wait是等待时间
const debounce = (func, wait = 50) => {
  // 缓存一个定时器id
  let timer = 0
  // 这里返回的函数是每次用户实际调用的防抖函数
  // 如果已经设定过定时器了就清空上一次的定时器
  // 开始一个新的定时器，延迟执行用户传入的方法
  return function(...args) {
    if (timer) clearTimeout(timer)
    timer = setTimeout(() => {
      func.apply(this, args)
    }, wait)
  }
}

function Parent(value) {
  this.val = value
}
Parent.prototype.getValue = function() {
  console.log(this.val)
}

function Child(value) {
  Parent.call(this, value) // 继承属性
}

Child.prototype = Object.create(Parent.prototype, { // 继承方法
  constructor: {
    value: Child,
    enumerable: false,
    writable: true,
    configurable: true
  }
})
const child = new Child(1)

child.getValue() // 1
child instanceof Parent // true

function People(name, idCard, age) {
  Object.defineProperty(this, '_idCard', { // 私有
    value: idCard,
    enumerable: false,
    writable: true,
    configurable: true
  })
  this[Symbol('_age')] = age // 私有
  this.name = name // 非私有
}
const p1 = new People('arley', 123456, 18)
p1.name
p1._age
console.log('log => : p1', p1) //  { name: 'arley', [Symbol(_age)]: 18 }
console.log('log => : p1.name', p1.name)
console.log('log => : p1._age', p1._age)

// 实现该函数，start()后等1秒输出1，再等2秒2，再等3秒3.

function Queue() {
  this.queue = []
}

Queue.prototype.task = function(time, fn) {
  this.queue.push({
    time,
    fn
  })
  return this
}
Queue.prototype.start = function() {
  let i = 0
  const last = this.queue.length - 1
  function start() {
    setTimeout(() => {
      this.queue[i].fn()
      i++
      if (i <= last) {
        start.call(this)
      }
    }, this.queue[i].time)
  }
  if (last > 0) {
    start.call(this)
  }
}

new Queue()
  .task(1000, () => console.log(1))
  .task(2000, () => console.log(2))
  .task(3000, () => console.log(3))
  .start()

function toCamel(str) {
  return str.replace(/(-\w)/g, function(match, $1) {
    return $1.toUpperCase()
  })
}

console.log(toCamel('ab-cd-ef'))// ab-Cd-Ef

// [1,2,3,4,6,7,9,13,15] => ['1->4',6->7,'9','13','15'] 实现一下

function arr2Section(arr) {
  let head, tail
  return [...arr, null].reduce((acc, current, index) => {
    if (index === 0) {
      head = tail = current
    } else {
      if (current - tail === 1) {
        tail = current
      } else {
        if (head === tail) {
          acc.push(`${head}`)
        } else {
          acc.push(`${head}->${tail}`)
        }
        head = current
        tail = current
      }
    }
    return acc
  }, [])
}
console.log(arr2Section([1, 2, 3, 4, 6, 7, 9, 13, 15]))

/*
 * @lc app=leetcode.cn id=21 lang=javascript
 *
 * [21] 合并两个有序链表
 *
 * https://leetcode-cn.com/problems/merge-two-sorted-lists/description/
 *
 * algorithms
 * Easy (59.08%)
 * Likes:    947
 * Dislikes: 0
 * Total Accepted:    226.3K
 * Total Submissions: 371.3K
 * Testcase Example:  '[1,2,4]\n[1,3,4]'
 *
 * 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 *
 * 示例：
 *
 * 输入：1->2->4, 1->3->4
 * 输出：1->1->2->3->4->4
 *
 *
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
  if (l1 === null) {
    return l2
  }
  if (l2 === null) {
    return l1
  }
  if (l1.val < l2.val) {
    l1.next = mergeTwoLists(l1.next, l2)
    return l1
  } else {
    l2.next = mergeTwoLists(l1, l2.next)
    return l2
  }
}
// @lc code=end

class Node {
  constructor(val) {
    this.val = val
    this.next = null
  }
}

class LinkList {
  constructor(arr) {
    const head = new Node(arr.shift())
    let next = head
    for (let i = 0, len = arr.length; i < len; i++) {
      next.next = new Node(arr[i])
      next = next.next
    }
    return head
  }

  static toArray(list) {
    const arr = []
    while (list) {
      arr.push(list.val)
      list = list.next
    }
    return arr
  }
}

const list1 = new LinkList([1, 2, 5])
const list2 = new LinkList([0, 3, 4])
console.log('log => : mergeTwoLists(list1, list2)', LinkList.toArray(mergeTwoLists(list1, list2)))

/*
 * @lc app=leetcode.cn id=88 lang=javascript
 *
 * [88] 合并两个有序数组
 *
 * https://leetcode-cn.com/problems/merge-sorted-array/description/
 *
 * algorithms
 * Easy (46.17%)
 * Likes:    470
 * Dislikes: 0
 * Total Accepted:    133.6K
 * Total Submissions: 282.7K
 * Testcase Example:  '[1,2,3,0,0,0]\n3\n[2,5,6]\n3'
 *
 * 给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
 *
 *
 *
 * 说明:
 *
 *
 * 初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
 * 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
 *
 *
 *
 *
 * 示例:
 *
 * 输入:
 * nums1 = [1,2,3,0,0,0], m = 3
 * nums2 = [2,5,6],       n = 3
 *
 * 输出: [1,2,2,3,5,6]
 *
 */

// @lc code=start
/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */

var merge = function(nums1, m, nums2, n) { // 回去等通知解法
  nums1.length = m
  nums1.push(...nums2)
  nums1.sort((a, b) => a - b)
}
// @lc code=end

merge([2, 0], 1, [1], 1)

var merge = function(nums1, m, nums2, n) {
  let length = m + n // 总长度
  while (n > 0) { // nums2的长度 > 0, 直到nums2完全写入
    if (m <= 0) { // 如果数组1的指针已经移到头了，也就是已经排序完数组1了，数组二就全部填剩下的位置
      length--
      n--
      nums1[length] = nums2[n]
      continue
    }
    length-- // 在nums1倒叙填入最大的数字, 谁大写谁, 谁的指针左移
    if (nums1[m - 1] >= nums2[n - 1]) {
      m--
      nums1[length] = nums1[m]
    } else {
      n--
      nums1[length] = nums2[n]
    }
  }
}

/*
 * @lc app=leetcode.cn id=70 lang=javascript
 *
 * [70] 爬楼梯
 *
 * https://leetcode-cn.com/problems/climbing-stairs/description/
 *
 * algorithms
 * Easy (47.54%)
 * Likes:    930
 * Dislikes: 0
 * Total Accepted:    168.8K
 * Total Submissions: 349.7K
 * Testcase Example:  '2'
 *
 * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
 *
 * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 *
 * 注意：给定 n 是一个正整数。
 *
 * 示例 1：
 *
 * 输入： 2
 * 输出： 2
 * 解释： 有两种方法可以爬到楼顶。
 * 1.  1 阶 + 1 阶
 * 2.  2 阶
 *
 * 示例 2：
 *
 * 输入： 3
 * 输出： 3
 * 解释： 有三种方法可以爬到楼顶。
 * 1.  1 阶 + 1 阶 + 1 阶
 * 2.  1 阶 + 2 阶
 * 3.  2 阶 + 1 阶
 *
 *
 */

// @lc code=start
/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
  const map = {}
  function getMap(n) {
    return map[n]
  }
  function setMap(n, val) {
    map[n] = val
    return val
  }
  function walk(n) {
    const number = getMap(n)
    if (typeof number !== 'undefined') {
      return number
    }

    if (n === 2 || n === 1) {
      return setMap(n, n)
    }
    const N1 = walk(n - 1)
    const N2 = walk(n - 2)
    return setMap(n - 1, N1) + setMap(n - 2, N2)
  }
  return walk(n)
}
// @lc code=end

// 直接解，不含备忘录，会重复计算
var climbStairs = function(n) {
  if (n === 2 || n === 1) {
    return n
  }
  return climbStairs(n - 1) + climbStairs(n - 2)
}

/**
 * 数组交换两个Index的值
 * @param {Array} array 数组
 * @param {Number} a 数组Index
 * @param {Number} b 数组Index
 */
function swap(array, a, b) {
  [array[a], array[b]] = [array[b], array[a]]
}

function partition(array, left, right) {
  // 基数: [0,1,2] // 0,2 => 1
  // 偶数: [0,1,2,3] // 0,3 => 1
  const pivot = array[Math.floor((left + right) / 2)] // 主元（取中间元素, 可以取其他位置)
  let i = left // 左指针，找大(停止循环)
  let j = right // 右指针，找小(停止循环)

  while (i <= j) { // 直到左右指针交汇
    while (array[i] < pivot) { // 左指针要找大(停止循环)，当遇到的比主元小，就一直向右移动
      i++
    }
    while (array[j] > pivot) { // 右指针要找小(停止循环)，当遇到的比主元大，就一直往左移动
      j--
    }
    if (i <= j) { // 左右指针都停止的时候(且左<=右)，交换左右指针所指的值
      swap(array, i, j)
      i++ // 左指针继续往右移动
      j-- // 右指针继续往左移动
      // PS: 如果i<=j 还是会继续移动指针，直到left > right
    }
  }
  return i // 返回左指针作为分隔
}
function quick(array, left, right) {
  let index
  if (array.length > 1) {
    index = partition(array, left, right)
    if (left < index - 1) {
      quick(array, left, index - 1)
    }
    if (index < right) {
      quick(array, index, right)
    }
  }
  return array
}
function quickSort(array) {
  return quick(array, 0, array.length - 1)
}

quickSort([3, 5, 1, 6, 4, 7, 2])

// 环形队列
// 1. 队尾插入，对头删除
class Queue {
  constructor(arr = [], max) {
    this.queue = arr
    this.head = 0
    this.tail = arr.length
    this.max = max
  }

  insert(item) {
    if (this.tail === this.max && this.head === 0) {
      return false
    }
    if (this.tail < this.max) {
      this.queue[this.tail] = item
      this.tail++
    }
    if (this.tail === this.max && this.head !== 0) {
      this.tail = 0
      this.queue[this.tail] = item
    }
    return true
  }

  delete() {
    const item = this.queue.shift()
    this.head++
    return item
  }

  show() {
    console.log(this)
  }
}

const queue = new Queue([1], 3)
queue.insert(2)
queue.insert(3)
queue.delete()