几道JS代码手写题以及一些代码实现

39,624 阅读20分钟

高阶函数实现AOP(面向切面编程)

什么是面向切面编程?

    Function.prototype.before = function (beforefn) {
        let _self = this; // 缓存原函数的引用
        return function () { // 代理函数
            beforefn.apply(this, arguments); // 执行前置函数
            return _self.apply(this, arguments); // 执行原函数
        }
    }

    Function.prototype.after = function (afterfn) {
        let _self = this;
        return function () {
            let set = _self.apply(this, arguments);
            afterfn.apply(this, arguments);
            return set;
        }
    }

    let func = () => console.log('func');
    func = func.before(() => {
        console.log('===before===');
    }).after(() => {
        console.log('===after===');
    });

    func();

输出结果:

===before===
func
===after===   

合并对象

const merge = (obj, target = {}) => {
  Object.keys(obj).forEach(key => {
    if (isObject(obj[key])) {
      if (isObject(target[key])) { // 都是对象
        Object.keys(obj[key]).forEach(prop => {
          target[key][prop] = obj[key][prop]
        })
      } else { // target不是对象 直接重写
        if (target[key]) {
          target[key] = {
            [key]: target[key],
            ...obj[key]
          }
        } else {
          target[key] = obj[key]
        }
        
      }
    } else {
      if (isObject(target[key])) {
        target[key] = {
          ...target[key],
          [key]: obj[key]
        }
      } else {
        target[key] = obj[key]
      }
    }
  })
  return target
}
const obj1 = {
  "pid": 1,  
  "signup": "注册",
  "menu": "菜单",
  "headers": {
    "common": "common"
  }
}
const obj2 = {
  "pid": 2,
  "signup": {
    "sin": 2
  },
  "menu": {
    "id": 1
  },
  "headers": {
    "test": 123
  }
}
const result = merge(obj1, obj2)
// {
//   pid: 2,
//   signup: { signup: '注册', sin: 2 },
//   menu: { menu: '菜单', id: 1 },
//   headers: { common: 'common', test: 123 }
// }
console.log(result)

Lodash 的 getset 方法的简单实现:

class Lodash {
  static get(obj, path, defaultValue) {
    const pathArray = Array.isArray(path)
      ? path
      : path.replace(/\[(\d+)\]/g, '.$1').split('.');
    let result = obj;
    for (let key of pathArray) {
      if (typeof result === 'object' && key in result) {
        result = result[key];
      } else {
        return defaultValue;
      }
    }
    return result;
  }

  static set(obj, path, value) {
    const pathArray = Array.isArray(path) ? path : path.replace(/\[(\d+)\]/g, '.$1').split('.')
    console.log('set', pathArray)
    let current = obj
    for (let i = 0; i < pathArray.length; i++) {
      const key = pathArray[i]
      if (i === pathArray.length - 1) {
        current[key] = value
      } else {
        current[key] = current[key] || {}
        current = current[key]
      }
    }
    return current
  }
}

var object = { a: [{ b: { c: 3 } }] };

console.log(Lodash.get(object, 'a[0].b.c', 2));
// => 3

console.log(Lodash.get(object, ['a', '0', 'b', 'c']));
// => 3

console.log(Lodash.get(object, 'a.b.c', 'default'));
// => 'default'

Lodash.set(object, 'a[0].b.c', 4);
console.log(object.a[0].b.c);
// => 4
 
Lodash.set(object, ['x', '0', 'y', 'z'], 5);
console.log(object.x[0].y.z);
// => 5

实现金额转换

image.png


// function extractDigits(num) {  
//   const unit = ['元', '角', '分']
//   let vals = (num+'').split('')
//   let res = ''
//   for (let i = 0, len = vals.length; i < len; i++) {
//     res = (`${vals.pop()}${unit.pop()}`) + res
//   }
//   return res
// }  
function extractDigits(num) {  
  const unit = ['元', '角', '分']
  let vals = (num+'')
  let res = ''
  let len = vals.length
  let unitLen = unit.length
  while(len-- > 0) {
    res = (`${vals[len]}${unit[--unitLen]}`) + res
  }
  return res
}

function extractDigits(num) {  
  const vals = num + ''
  const unit = ['元', '角', '分'].slice(-vals.length)
  let res = ''
  for (let i = 0, len = vals.length; i < len; i++) {
    res += `${vals[i]}${unit[i]}`
  }
  return res
}  

console.log(extractDigits(172)); 
console.log(extractDigits(72)); 
console.log(extractDigits(372)); 
//1元7角2分
//7角2分
//3元7角2分

阿拉伯数字转中国数字

支持转换范围0~99

  // 12345678910 => 零一二三四五六七八九十
  const transformNum = (num) => {
      const chars = (num + '').split('')
      const capitalNum = '零一二三四五六七八九十'
      if (num <= 10) {
        return capitalNum[num] || num
      }
      let split = ''
      if (num >= 10 && num < 100 && (num % 10 !== 0)) {
        split = '十'
      }
      const str = chars.map(char => {
        if (char == 0) char = 10
        return capitalNum[char] || ''
      }).join(split)
      return num < 20 ? str.slice(-2) : str
  }

支持到万的数字

function toChinesNum(num) {
  let changeNum = ['零', '一', '二', '三', '四', '五', '六', '七', '八', '九', '十']; //changeNum[0] = "零"
  if (num <= 10) {
    return changeNum[num];
  }
  let unit = ['', '十', '百', '千', '万'];
  num = parseInt(num);
  let getWan = temp => {
    let strArr = temp.toString().split('').reverse();
    let newNum = '';
    for (var i = 0; i < strArr.length; i++) {
      newNum =
        (i == 0 && strArr[i] == 0
          ? ''
          : i > 0 && strArr[i] == 0 && strArr[i - 1] == 0
          ? ''
          : changeNum[strArr[i]] + (strArr[i] == 0 ? unit[0] : unit[i])) + newNum;
    }
    return newNum;
  };
  let overWan = Math.floor(num / 10000);
  let noWan = num % 10000;
  if (noWan.toString().length < 4) noWan = '0' + noWan;
  if (overWan) {
    return getWan(overWan) + '万' + getWan(noWan);
  }
  const result = getWan(num);
  if (num > 10 && num < 20) {
    return result.slice(-2);
  }
  return result;
}

## 阶乘

```js
const factorial1 = n => {
  if (n <= 1) return 1
  return n * factorial1(n - 1)
}

// 尾递归优化
const factorial2 = (n, total = 1) => {
  if (n <= 1) return total
  return factorial2(n - 1, total * n)
}

console.log(factorial1(3)) // 6
console.log(factorial2(3)) // 6
console.log(factorial1(5)) // 120
console.log(factorial2(5)) // 120

二分查找

//循环不变式 guess 等于l r中间位置
const bsearch = (A, x) => {
  let l = 0
  let r = A.length - 1
  let guess
  while (l <= r) {
    console.log('find')
    guess = Math.floor((l + r) / 2)
    if (A[guess] === x) return guess
    if (A[guess] > x) r = guess - 1
    else l = guess + 1
  }
  return -1
}

let arr = [1, 2, 3, 4, 5, 6, 7, 8]
console.log(bsearch(arr, 6)) // 5

将二叉树结构变成链表

// 将一个树型结构,变成链表
class LinkNode {
  constructor(val) {
    this.val = val
    this.next = null
  }
}
// const flatten = function(root) {
//   const head = new LinkNode(null)
//   let linkNode = head
//   const midOrder = (node) => {
//     if (node == null) return
//     linkNode.next = new LinkNode(node.val)
//     linkNode = linkNode.next
//     midOrder(node.left)
//     midOrder(node.right)
//   }
//   midOrder(root)
//   return head.next
// }

// 直接修改root
const flatten = function(root) {
  let head = new LinkNode(null)
  const linkHead = head
  const midOrder = (node) => {
    if (node == null) return
    head.next = node
    head = node
    midOrder(node.left)
    midOrder(node.right)
    delete node.left
    delete node.right
  }
  midOrder(root)
  return linkHead.next
}
function TreeNode(val) {
  this.val = val
  this.left = this.right = null
}

const root = new TreeNode(1)
root.left = new TreeNode(2)
root.right = new TreeNode(5)

root.left.left = new TreeNode(3)
root.left.right = new TreeNode(4)
root.right.right = new TreeNode(6)
console.log(JSON.stringify(flatten(root), null, 2))

// {
//   "val": 1,
//   "next": {
//     "val": 2,
//     "next": {
//       "val": 3,
//       "next": {
//         "val": 4,
//         "next": {
//           "val": 5,
//           "next": {
//             "val": 6
//           }
//         }
//       }
//     }
//   }
// }

斐波那契数列

斐波那契数列从第三项开始,每一项都等于前两项之和。指的是这样一个数列:0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 …

得到数列中第n项指向的数值是多少

1.递归

function fib(n) {
  if (n === 1 || n === 2) return n - 1;
  return fib(n - 1) + fib(n - 2)
}
console.log(fib(10)); // 34

时间复杂度为O(2^n)

2.非递归

function fib(n) {
  let a = 0;
  let b = 1;
  let c = a + b;
  for (let i = 3; i < n; i++) {
    a = b;
    b = c;
    c = a + b;
  }
  return c;
}
console.log(fib(10)); // 34

时间复杂度为O(n)

价格区间指定递增

根据指定的价格范围,递增单位也不同。在0到10之间,每次递增1;在10到100之间,每次递增5;在100到1000之间,每次递增10;在1000以上,每次递增20。最小值为0,最大值等于指定值(如500)。

版本一

// 这个函数接受一个最大价格作为参数,并返回从0到最大价格之间的所有可能的价格值。该函数将使用一个
// 包含每个范围的对象数组,然后使用while循环来生成递增的价格列表。最终的结果将作为数组返回并输出到控制台。
// 版本一
function getPriceRangeValues(maxPrice) {
  if (maxPrice == undefined) return []
  const priceRanges = [
    { max: 10, increment: 1 },
    { max: 100, increment: 5 },
    { max: 1000, increment: 10 },
    { max: Infinity, increment: 20 }
  ];

  const values = [];

  let currentPrice = 0;
  // 待优化
  while (currentPrice <= maxPrice) {
    let range = priceRanges.find(range => currentPrice < range.max);

    values.push(currentPrice);

    currentPrice += range.increment;
  }
  values[values.length - 1] < maxPrice && values.push(maxPrice)
  return values;
}
console.log(getPriceRangeValues(120));
结果:[
   0,   1,   2,   3,  4,  5,  6,  7,  8,
   9,  10,  15,  20, 25, 30, 35, 40, 45,
  50,  55,  60,  65, 70, 75, 80, 85, 90,
  95, 100, 110, 120
]

优化版本

    // 版本二
    function getPriceRangeValues(maxPrice) {
      if (maxPrice === undefined) {
        return [];
      }

      const priceRanges = [
        { max: 10, increment: 1 },
        { max: 100, increment: 5 },
        { max: 1000, increment: 10 },
        { max: Infinity, increment: 20 }
      ];

      const values = [];
      let currentPrice = 0;
      // 优化范围递增逻辑
      for (const range of priceRanges) {
        while (currentPrice < range.max && currentPrice <= maxPrice) {
          values.push(currentPrice);
          currentPrice += range.increment;
        }
      }

      if (values[values.length - 1] !== maxPrice) {
        values.push(maxPrice);
      }

      return values;
    }

这段代码的时间复杂度为 O(n),其中 n 是 priceRanges 数组的长度。在最坏情况下,所有价格范围都被遍历一遍,因此循环次数为 priceRanges 数组的长度,即 n。因为函数中有一个循环遍历 priceRanges 数组,每次循环都会执行一个 while 循环,而 while 循环的执行次数取决于当前区间的最大价格和传入的最大价格。因此,时间复杂度为 O(n)。空间复杂度为 O(m),其中 m 是返回的数组的长度,因为函数中创建了一个数组 values 来存储价格区间的值。

实现栈结构

const Stack = (() => {
  const wm = new WeakMap()
  class Stack {
    constructor() {
      wm.set(this, [])
      this.top = 0
    }

    push(...nums) {
      let list = wm.get(this)
      nums.forEach(item => {
        list[this.top++] = item
      })
    }

    pop() {
      let list = wm.get(this)
      let last = list[--this.top]
      list.length = this.top
      return last
    }

    peek() {
      let list = wm.get(this)
      return list[this.top - 1]
    }

    clear() {
      let list = wm.get(this)
      list.length = 0
    }

    size() {
      return this.top
    }

    output() {
      return wm.get(this)
    }

    isEmpty() {
      return wm.get(this).length === 0
    }
  }
  return Stack
})()

let s = new Stack()

s.push(1, 2, 3, 4, 5)
console.log(s.output()) // [ 1, 2, 3, 4, 5 ]

十进制转化为其他进制

function binary(num, base = 2) {
  const stack = []
  const digits = '0123456789ABCDEF'
  while (num > base - 1) {
    stack.push(digits[num % base])
    num = ~~(num / 2)
  }
  stack.push(digits[num])
  return stack.reverse().join('')
}

console.log(binary(10)) // '1010'

十进制转化为其他进制 (利用栈)

function divideBy2(decNumber, base = 2) {
  let remStack = new Stack()
  let rem
  let binaryString = ''
  let digits = '0123456789ABCDEF'
  while (decNumber > 0) {
    rem = Math.floor(decNumber % base)
    remStack.push(rem)
    decNumber = Math.floor(decNumber / base)
  }
  while (!remStack.isEmpty()) {
    binaryString += digits[remStack.pop()].toString()
  }
  return binaryString
}

// 将十进制转换成其他进制
let num = 100345
num.toString(2) // "11000011111111001"
num.toString(8) // "303771"

console.log(divideBy2(num, 2)) // "11000011111111001"
console.log(divideBy2(num, 8)) // "303771"

一道关于Array push的JS题

// 类数组
let obj = {
  '1': 'a',
  '2': 'b',
  length: 2,
  push: Array.prototype.push
};

// Array.prototype.push.call(obj, 'c');
obj.push('c')

console.log(obj); // { '1': 'a', '2': 'c', length: 3 }

push和pop实现

Array的push底层实现是依赖于 数组的length属性的

Array.prototype.push2 = function(...rest){
  this.splice(this.length, 0, ...rest)
  return this.length;
}

对于 pop也是一样

Array.prototype.pop2 = function(){
  return this.splice(this.length - 1, 1)[0];
}

规律题

image.png

function createFloat (i) {
  let dec = 1
  while (i >= Math.pow(2, dec++)) {
  }
  const den = Math.pow(2, dec - 1)
  const mol = i * 2 - den + 1
  console.log(i, mol, den)
}
createFloat(1)
createFloat(2)
createFloat(3)
createFloat(4)
createFloat(5)
createFloat(6)
createFloat(7)
createFloat(8)

算法题

1.在一个数组中 找出里面其中两项相加后的和为num,如果存在就返回两个数的索引位置,否则false

function fn(num = 0, ary = []) {
  for (let i = 0; i < ary.length; i++) {
    let diff = num - ary[i];
    let diffIndex = ary.indexOf(diff);
    if (diffIndex !== -1 && diffIndex !== i) {
      return [i, diffIndex];
    }
  }
  return false;
}

let num = 3;
let arr = [-1, 4, 6, 2];

console.log(fn(num, arr)); // [0, 1]

2. 将两个有序数组合并为一个排好序的大数组

function mergeAry(left = [], right = []) {
  const result = [];
  while (left.length && right.length) {
    result.push(left[0] <= right[0] ? left.shift() : right.shift());
  }
  return result.concat(left, right);
}

console.log(mergeAry([1, 2, 3], [1, 4, 8, 9])); // [ 1, 1, 2, 3, 4, 8, 9 ]

3.在数组中找到三个不同元素 其中两项的和当于第三项 arr[x] + arr[y] = arr[z] 如果数组中存在返回true 否则返回false

如:
[1, 18, 3, 2] => 1 + 2 = 3 => true;
[3, 11, 2, 7] => false

let a1 = [2, 99, 3, 5]
let a2 = [1, 2, 10, 5]

function find(arr) {
  arr.sort((a, b) => a - b)
  for (let i = 0; i < arr.length - 1; i++) {
    let cur = arr[i]
    for (let k = i + 1; k < arr.length; k++) {
      let next = arr[k]
      let diff = next - cur
      if (![cur, next].includes(diff) && arr.includes(diff)) {
        return true
      }
    }
  }
  return false
}

console.log(find(a1)) // true
console.log(find(a2)) // false

去除特殊字符和问号,只保留字母和单引号,对于特殊符号后面问号跟着的如果是字母转换成大写"I'm?���driving�??�to�?beijing�?��after�breakfast"

=> 'I'm driving to Beijing after breakfast'

let str = "I'm?���driving�??�to�?beijing�?��after�breakfast"

const reg1 = /�+\?([a-z])/ig
const reg2 = /[^a-z']+/ig
str = str.replace(reg1, (a, g1) => {
  return ' ' + g1.toUpperCase()
}).replace(reg2, ' ')
console.log(str) // 'I'm driving to Beijing after breakfast'

模板编译

const template = `
  <div class="play" name="{{name}}">{{ value }}</div>
`

const data = {
  name: 'Brolly',
  value: 'FE'
}

const compiler = (str, data) => {
  const reg = /\{\{(.*?)\}\}/g
  return str.replace(reg, (patten, g1) => {
    const key = g1.trim()
    return data[key] ? data[key] : ''
  })
}

const content = compiler(template, data)
// <div class="play" name="Brolly">FE</div>
console.log(content)

字符串repeat实现

// 原生repeat
'ni'.repeat(3); // 'ninini'

// 实现一
String.prototype.repeatString1 = function (n) {
  return Array(n + 1).join(this);
}
console.log('ni'.repeatString1(3));

// 实现二
String.prototype.repeatString2 = function (n) {
  return Array(n).fill(this).join('');
}
console.log('ni'.repeatString2(3));

计时器实现任务调度 周期天为单位,0-23点, 每小时检测一次

class Cron {
  constructor() {
    this.map = new Map()
    this.timer = null
    this.interval = 60 * 60 * 1000
    this._initCron()
    this._runCron()
  }
  addSub (time, fn) {
    if (this.map.has(time)) {
      this.map.get(time).push(fn)
    }
  }
  _run (time) {
    if (this.map.has(time)) {
      this.map.get(time).forEach(fn => fn())
    }
  }
  _initCron() {
    for (let i = 0; i <= 23; i++) {
      this.map.set(i, [])
    }
  }
  resetCron () {
    for (let i = 0; i <= 23; i++) {
      this.map.set(0, [])
    }
  }
  _runCron () {
    this.timer = setInterval(() => {
      const hour = (new Date()).getHours()
      this._run(hour)
    }, this.interval)
  }
  stopCron () {
    clearInterval(this.timer)
  }
  runCron () {
    this._runCron()
  }
}

const cron = new Cron()
cron.addSub(22, () => {
  console.log('我要吃饭')
})
cron.addSub(22, () => {
  console.log('我要工作')
})

每次加三的数组 如 【3,6,9,...】

const addThree = (start, target, arr = []) => {
  if (start === target) {
    arr.push(start)
    return arr
  }
  if (start > target) {
    return arr
  }
  arr.push(start)
  return addThree(start += 3, target, arr)
}
console.log(addThree(3, 40))

当我们 new 一个类的时候 都发生了什么

/**
 * new2 new关键字的代码实现演示
 * @param {function} func 被new的类 (构造函数)
 */
function new2(func) {
    // 创建了一个实例对象 o,并且这个对象__proto__指向func这个类的原型对象 
    let o = Object.create(func.prototype); 
    // (在构造函数中this指向当前实例)让这个类作为普通函数值行 并且里面this为实例对象 
    let k = func.call(o);
    // 最后再将实例对象返回 如果你在类中显示指定返回值k,
    // 注意如果返回的是引用类型则将默认返回的实例对象o替代掉
    return typeof k === 'object' ? k : o;
}

// 实验
function M() { // 即将被new的类
    this.name = 'liwenli';
}

let m = new2(M); // 等价于 new M 这里只是模拟
console.log(m instanceof M); // instanceof 检测实例
console.log(m instanceof Object);
console.log(m.__proto__.constructor === M);

this/bind

let obj = { a: 1};
  function fn() {
    this.b = 100;
    return this.a;
  }
  let fe = fn.bind(obj);
  console.log(fe()); // 1  里面this是obj
  console.log(obj); // { a: 1, b: 100 }
  console.log(new fe()); // 里面this是当前创建实例对象 { b: 100 }

Object.create 兼容实现

        let obj1 = {id: 1};
        Object._create = (o) => {
            let Fn = function() {}; // 临时的构造函数
            Fn.prototype = o;
            return new Fn;
        }
        
        let obj2 = Object._create(obj1);
        console.log(obj2.__proto__ === obj1); // true
        console.log(obj2.id); // 1

        // 原生的Object.create
        let obj3 = Object.create(obj1);
        console.log(obj3.__proto__ === obj1); // true
        console.log(obj3.id); // 1

一道面试题

解法一

function CodingMan(name) { // 主要考察的是 面向对象以及JS运行机制(同步 异步 任务队列 事件循环)
	function Man(name) {
		setTimeout(() => { // 异步
			console.log(`Hi! This is ${name}`);
		}, 0);
	}

	Man.prototype.sleep = function(time) {
		let curTime = new Date();
		let delay = time * 1000;
		setTimeout(() => { // 异步
			while (new Date() - curTime < delay) {} // 阻塞当前主线程
			console.log(`Wake up after ${time}`);
		}, 0);
		return this;
	}

	Man.prototype.sleepFirst = function(time) {
		let curTime = new Date();
		let delay = time * 1000;
		while (new Date() - curTime < delay) {} // 阻塞当前主线程
		console.log(`Wake up after ${time}`);
		return this;
	}

	Man.prototype.eat = function(food) {
		setTimeout(() => { // 异步
			console.log(`Eat ${food}~~`);
		}, 0)
		return this;
	}

	return new Man(name);
}

// CodingMan('Peter');
// CodingMan('Peter').sleep(3).eat('dinner');
// CodingMan('Peter').eat('dinner').eat('supper');
// CodingMan('Peter').sleepFirst(5).eat('supper');

解法二

    function CodingMan(name) {
        function fe() {
            fe.flag = true;
            console.log(`Hi! This is ${name}`);
        }
        fe.flag = false;
        fe.timer = setTimeout(() => {
            clearTimeout(fe.timer);
            if (!fe.flag) fe();
        }, 0);
        return fe;
    }

    Function.prototype.sleep = function (delay) {
        this()
        this.await(delay);
        return this;
    }

    Function.prototype.sleepFirst = function (delay) {
        this.await(delay);
        this();
        return this;
    }

    Function.prototype.eat = function (dinner) {
        setTimeout(() => {
            console.log(`Eat ${dinner}~`);
        });
        return this;
    };

    Function.prototype.await = function (delay) {
        delay = isNaN(delay) ? 0 : delay;
        let startTime = new Date();
        let delayTime = delay * 1000;
        while (new Date() - startTime <= delayTime) {
        }
        console.log(`Wake up after ${delayTime}ms`);
    }
     // CodingMan('peter')
     // CodingMan('peter').sleep(2).eat('hanbao');
     // CodingMan('peter').sleepFirst(2).eat('hanbao');
     CodingMan('peter').eat('haha').eat('hanbao');

currying 函数柯理化

bind 柯理化

  function add(a, b, c) {
    return a + b + c;
  }
  let f1 = add.bind(undefined, 100);
  console.log(f1(2, 3)); // 105 = 100 + 2 + 3
  let f2 = f1.bind(undefined, 200);
  console.log(f2(3)); // 303 = 100 + 200 + 3

curry 柯理化的实现(递归调用 + valueOf)

知识点:对象的valueOf浏览器环境下 隐式转化为基本数据类型(一元操作符+object/字符串拼接 ''+object)时,会调用自身的valueOf方法取值,如果自身也存在toString方法 先调用valueOf 如果valueOf返回值不是基本数据类型 则调用toString, toString的返回值也不是基本数据类型就报错。

valueOf调用场景

let obj = { x: 1, y: 2 };

obj.toString = function() {
  return this.x + this.y;
}

obj.valueOf = function() {
  return this.x + this.y + 100;
}

// 以下情况下自身valueOf被调用
console.log('' + obj); // 103
console.log(+obj); // 103
function fn() {};
fn.valueOf = () => console.log('valueof');
console.log(fn); // valueof
const mul = x => {
    const result = y => mul(x * y); // 递归调用mul
    result.valueOf = () => x;
    return result;
}
console.log(mul(2)(3)); // 6

// 在上面mul每执行一次,就会返回一个valueOf被改写后的新函数result 并且result执行会在里面调用mul(x * y)
// 在result函数的valueOf里保存着 由上一次x * y 传进来的结果x, 也就是上一次x*y 会作为这一次的输出 依然叫x

// 第一次mul(2) 此时 x为2  return result
result 为 result = y => mul(2 * y); 
// 第二次 mul(2)(3) 等价于 第一个mul返回的result(3), result执行 => mul(2 * 3) 再次调用mul 将2*3 = 6 的结果作为mul参数
// 最后mul(6) x = 6 在返回一个新函数result 此时result的valueOf = () => 6

// log(mul(2)(3)) 相当于log的最后返回的result 隐式调用valueOf 返回 6

curry 将多参数函数转换为接收单一参数的函数

function fe(a, b, c) {
    return a + b + c;
}

function curry(fe) {
    let args = []; // 参数集合
    let len = args.length;
    return function bar() {
        args = [...args, ...arguments]; // 收集参数
        if (args.length >= fe.length) {
            return fe.apply(this, args);
        }
        return bar;
    }
}

console.log(curry(fe)(1)(2)(3)); // 6

currying 部分求值

    // currying 函数柯理化
    let currying = function(fn) {
        let args = [];
        return function fe() {
            if (arguments.length === 0) {
                return fn.apply(this, args);
            }
            [].push.apply(args, arguments);
            return fe;
        }
    }
    let count = currying(function (...rest) {
        return rest.reduce((prev, cur) => prev + cur, 0);
    });

    console.log(count(100)(200)(10)()); // 310

收集参数 延迟执行 到达指定次数才执行

   // 参数收集 指定次数后执行
        function fn(...rest) {console.log(rest);};
        function after(fn, time = 1) {
            let params = [];
            return function(...rest) {
                params = [...params, ...rest];
                if (--time === 0) {
                    fn.apply(this, params);
                }
            }
        }
        let newFn = after(fn, 3); // 执行3次 内部fn才会执行
        newFn(2);
        newFn(3);
        newFn(4);

函数节流

throttle 策略的电梯。保证如果电梯第一个人进来后,50毫秒后准时运送一次,不等待。如果没有人,则待机。

        let throttle = (fn, delay = 50) => { // 节流 控制执行间隔时间 防止频繁触发 scroll resize mousemove
            let stattime = 0;
            return function (...args) {
                let curTime = new Date();
                if (curTime - stattime >= delay) {
                    fn.apply(this, args);
                    stattime = curTime;
                }
            }
        }

正则效验 必须包含数字、字母大小写

  // 同时包含 数字 字母大小写
  // let reg = /^(?!([a-zA-Z]+|\d+)$)[a-zA-Z\d]{8,15}$/
  // ^(?![0-9]+$)(?![a-zA-Z]+$)[0-9A-Za-z]
  let reg = /^(?!([a-zA-Z]+|[a-z\d]+|[A-Z\d]+)$)[a-zA-Z\d]{8,15}$/
  console.log(reg.test('lolABC123')) // true
  console.log(reg.test('lol12313123')) // false
  console.log(reg.test('ADF12313123')) // false
  console.log(reg.test('12312313123')) // false
  console.log(reg.test('LLLLLLLLLL')) // false
  console.log(reg.test('aaaaaaass')) // fals

函数防抖完全版

/**
 * @desc 函数防抖
 * @param func 函数
 * @param wait 延迟执行毫秒数
 * @param immediate true 表立即执行,false 表非立即执行
 */
 
function debounce(func,wait,immediate) {
    var timeout;

    return function () {
        var context = this;
        var args = arguments;

        if (timeout) clearTimeout(timeout);
        if (immediate) {
            var callNow = !timeout;
            timeout = setTimeout(function(){
                timeout = null;
            }, wait)
            if (callNow) func.apply(context, args)
        }
        else {
            timeout = setTimeout(function(){
                func.apply(context, args)
            }, wait);
        }
    }
}

防抖动

debounce 策略的电梯。如果电梯里有人进来,等待50毫秒。如果又人进来,50毫秒等待重新计时,直到50毫秒超时,开始运送。

   let debounce = (fn, time = 50) => { // 防抖动 控制空闲时间 用户输入频繁
            let timer;
            return function (...args) {
                let that = this;
                clearTimeout(timer);
                timer = setTimeout(fn.bind(that, ...args), time);
            }
        }

深度拷贝兼容写法(不包括原型属性)

function deepCopy(obj) {
    if (typeof obj !== 'object') return obj;
    if (typeof window !== 'undefined' && window.JSON) { // 浏览器环境下 并支持window.JSON 则使用 JSON
        return JSON.parse(JSON.stringify(obj));
    } else {
        let newObj = obj.constructor === Array ? [] : {};
        for(let key in obj) {
            newObj[key] = typeof obj[key] === 'object' ? deepCopy(obj[key]) : obj[key];
        }
        return newObj;
    }
}

let obj = {a: 1, b: [12]};
let newObj = deepCopy(obj);
newObj.b[1] = 100;
console.log(obj);
console.log(newObj);

深度克隆加强版

function cloneDeep(obj) {
  let type = isType(obj)
  if (type === 'Array' || type === 'Object') {
    return cloneObj(obj)
  } else if (type === 'Date') {
    return obj.constructor(obj)
  } else {
    return obj
  }
}

function cloneObj(obj) {
  let newObj = obj instanceof Array ? [] : {};
  for (let key in obj) {
    newObj[key] = typeof obj[key] === 'object' ? cloneObj(obj[key]) : obj[key]
  }
  return newObj;
}

function isType(o) {
  return /\[object\s(.*?)\]/.exec(Object.prototype.toString.call(o))[1]
}

let fn = function () {
  return 123
}
var a = [[1, 2, 3], [4, 5, 6, 7, fn]];
// let c = new Date();
// var b = cloneDeep(c);
var b = cloneDeep(a);
console.log(b[0], a[0]);
console.log(b[0] === a[0]);

原生数据类型检测简易封装

Object.prototype.isType = function (type) {
  return function (params) {
    return Object.prototype.toString.call(params) === `[object ${type}]`
  }
}

let isString = Object.isType('String')
let isArray = Object.isType('Array')

console.log(isString(1)) // false
console.log(isString('hello')) // true

console.log(isArray(2)) // false
console.log(isArray(['hello'])) // true

Array的reduce实现

Array.prototype._reduce = function (callback, initVal) {
  let i = 0
  let result = initVal
  if (typeof initVal === 'undefined') {
    result = this[0]
    i++
  }

  for (i; i < this.length; i++) {
    result = callback(result, this[i])
  }
  return result
}

const arr = [1, 2, 3]
let result = arr._reduce((a, b) => {
  return a + b
}, 0)
console.log(result) // 6

Function的bind实现

1.es5
    Function.prototype._bind = function(context) {
      let func = this;
      let params = [].slice.call(arguments, 1);
      let Fnop = function() {};
      let fbound = function() {
        params = params.concat([].slice.call(arguments, 0));
        return func.apply(this instanceof Fnop ?
          this : context, params);
      }
      Fnop.prototype = this.prototype;
      fbound.prototype = new Fnop();
      return fbound;
    }

    function foo() {
      this.b = 100;
      return this.a;
    }
    let fe = foo._bind({ a: 1 });
    console.log(fe()); // 1
    console.log(new fe()); // 实例 {b: 100}

2.es6
  Function.prototype.mybind = function(context, ...rest) {
    return (...params) => this.call(context, ...rest, ...params);
  }

函数组合串联compose(reduce中间件)

// 组合串联
let fn1 = (a) => a + 1;
let fn2 = (b) => b + 2;
let fn3 = (c) => c + 3;

let funs = [fn1, fn2, fn3];

let compose = (func) => {
    return arg => func.reduceRight((composed, fn) => fn(composed), arg);
}
console.log(compose(funs)(100)); // 相当于fn1(fn2(fn3(100)))

redux 源码中compose实现(github.com/reduxjs/red…)

export default function compose(...funcs) {
  if (funcs.length === 0) {
    return arg => arg
  }

  if (funcs.length === 1) {
    return funcs[0]
  }

  return funcs.reduce((a, b) => (...args) => a(b(...args)))
}

koa-compose 实现

function compose(middleware) {
  return function(ctx, next) {
    let index = -1;
    return dispatch(0)
    function dispatch(i) {
      if(i <= index) return Promise.reject(new Error('next() called multiple times'));
      index = i;
      let fn = middleware[i]
      if (i === middleware.length) fn = next
      if (!fn) return Promise.resolve()
      try {
        return Promise.resolve(fn(ctx, dispatch.bind(null, i + 1)))
      } catch(e) {
        return Promise.reject(e)
      }
    }
  }
}

let mid1 = (ctx, next) => {
  console.log('ctx1', ctx);
  next()
}

let mid2 = (ctx, next) => {
  console.log('ctx2', ctx);
  next()
}

let mid3 = (ctx, next) => {
  console.log('ctx3', ctx);
}

let co = compose([mid1, mid2, mid3])
co('ctx')

co函数

function *fn(a = 0) {
  console.log('a', a)
  const b = yield 2
  console.log('b', b)
  const c = yield Promise.resolve(3)
  console.log('c', c)
  return a + b + c
}

// const it = fn(1)
// it.next()
// it.next(2)
// it.next(3)
// co(fn, 1)

function fe() {
  return 100
}
run(fn, 10).then(res => {
  console.log(res)
})

function run(gen) {
  const slice = [].slice
  const args = slice.call(arguments, 1)
  return new Promise((resolve, reject) => {
    const ite = (typeof gen === 'function') && gen.apply(this, args)
    if (!ite || typeof ite.next !== 'function') return resolve(ite)
    function next(res) {
      const { value, done } = ite.next(res)
      if (done) {
        resolve(value)
      } else if (value instanceof Promise) {
        value.then(next)
      } else {
        next(value)
      }
    }
    next()
  })
}

es6简版 promise

class Promise {
 constructor(fn) {
   this.status = 'Pending'
   setTimeout(() => {
     fn((data) => {
       this.resolve(data)
     }, (error) => {
       this.reject(error)
     })
   })
 }
 
 resolve(data) {
   if (this.status === 'Pending') {
     this.success(data)
     this.status = 'Fulfilled'
   }
 }

 reject(error) {
   if (this.status === 'Pending') {
     this.error(error)
     this.status = 'Rejected'
   }
 }

 then(success, error) {
   this.success = success
   this.error = error
 }
}

let p1 = new Promise((resolve, reject) => {
 // reject('hello error');
 setTimeout(() => {
   resolve('hello promise')
 }, 1000)
})

p1.then((data) => console.log(data), (err) => console.log(err))

如何主动中止Promise调用链

const p1 = new Promise((resolve, reject) => {
  setTimeout(() => { // 异步操作
      resolve('start')
  }, 1000);
});

p1.then((result) => {
   console.log('a', result); 
   return Promise.reject('中断后续调用'); // 此时rejected的状态将直接跳到catch里,剩下的调用不会再继续
}).then(result => {
   console.log('b', result);
}).then(result => {
   console.log('c', result);
}).catch(err => {
   console.log(err);
});

// a start
// 中断后续调用

bluebird.promisify实现(将异步回调函数api 转换为promise形式)

// promisify.js
module.exports = {
   promisify(fn){
       return function () {
           var args = Array.from(arguments);
           return new Promise(function (resolve, reject) {
               fn.apply(null, args.concat(function (err) {
                   if (err) {
                       reject(err);
                   } else {
                       resolve(arguments[1])
                   }
               }));
           })
       }
   }
}

// main.js
const fs = require('fs');
const {promisify} = require('./promisify.js');

const readFile = promisify('fs.readFile'); // 转换异步读取

// 异步文件 由回调函数形式变成promise形式
readFile('./1.txt', 'utf8').then(data => { 
   console.log(data);
}).catch(err => {
   console.log(err);
});

window.requestAnimationFrame兼容性处理

window._requestAnimationFrame = (function(){
  return  window.requestAnimationFrame       ||
          window.webkitRequestAnimationFrame ||
          window.mozRequestAnimationFrame    ||
          function(callback){
            window.setTimeout(callback, 1000 / 60);
          };
})();

字符串是否符合回文规则

let str = 'My age is 0, 0 si ega ym.';

方法一
function palindrome(params) {
  params = params.replace(/[\W\s_]/ig, '');
 return params.toLowerCase()  === params.split('').reverse().join('').toLowerCase();
}
console.log(palindrome(str));

方法二
function palindrome(params) {
  params = params.replace(/[\W\s_]/ig, '').toLowerCase();
  for (var i = 0, j = params.length-1; i<j; i++, j--) {
    if (params[i] !== params[j]) {
      return false;
    }
  }
  return true;
}

解构

// 将 destructuringArray([1, [2, 3], 4], "[a, [b], c]") => {a: 1, b: 2, c: 4}
const targetArray = [1, [2, 3], 4];
const formater = "[a, [b], c]";

const destructuringArray = (values, keys) => {
  try {
    const obj = {};
    if (typeof keys === 'string') {
      keys = JSON.parse(keys.replace(/\w+/g, '"$&"'));
    }
    
    const iterate = (values, keys) =>
      keys.forEach((key, i) => {
        if(Array.isArray(key)) iterate(values[i], key)
        else obj[key] = values[i]
      })
      
    iterate(values, keys)
    
    return obj;
  } catch (e) {
    console.error(e.message);
  }
}

数组展平

将[[1, 2], 3, [[[4], 5]]] 展平为 [1, 2, 3, 4, 5]

let arr = [[1, 2], 3, [[[4], 5]]]; // 数组展平
function flatten(arr) {
    return [].concat(
        ...arr.map(x => Array.isArray(x) ? flatten(x) : x)
    )
}

二分查找

const arr = [1, 2, 3, 4, 5, 6, 7, 8];
// 二分查找 递归 由中间开始往两边查找 前提是有序的数组 返回对应的索引位置
function binarySearch1(arr, dest, start = 0, end = data.length) {
	if (start > end) {
		return -1
	}
	let midIndex = Math.floor((start + end) / 2); // 中间位置索引
	let mid = arr[midIndex]; // 中间值

	if (mid == dest) {
		return midIndex;
	}
	if (dest < mid) { // 要找的比中间值小 就从中间往开头找 一直到0
		return binarySearch1(arr, dest, 0, midIndex - 1);
	}
	if (dest > mid) { // 要找的比中间值大 就从中间往后找 一直到end结束
		return binarySearch1(arr, dest, midIndex + 1, end);
	}
	return -1; // 找不到返回-1
}
console.log(binarySearch1(arr, 7, 3, 6)); // 6

// 非递归 arr前提有序数组 (从小到大)返回对应的索引位置 
function binarySearch2(arr, dest) {
	let max = arr.length - 1;
	let min = 0;
	while (min <= max) {
		let mid = Math.floor((max + min) / 2); // mid中间位置索引
		if (dest < arr[mid]) { // 如果要找的这项比中间项还要小 说明应该在mid中间位置前面 修改最大边界值max=mid-1 
			max = mid - 1;
		} else if (dest > arr[mid]) { // 如果要找的这项比中间项还要大 说明应该在mid中间位置的后面 修改最小边界值min=mid+1
			min = mid + 1;
		} else {
			return mid;
		}
	}
	return -1; // 找不到返回-1
}
console.log(binarySearch2(arr, 3)); // 2

二分查找题

在一个二维数组中,每一行都按照从左到右递增,每一列都从上到下递增的顺序排序,完成一个函数,输入这个二维数组和一个整数,判断数组中是否含有该整数

思路是一样的,只不过从一维变成了二维,我们遍历思路可以这样子:

  • 选取第一行的最后一个进行判断(这个是第一行中最大的)
  • 如果目标大于该值,行数加1,遍历第二行(因为每列都是递增的)
  • 如果目标小于该值,则在这一行中进行查找

循环以上步骤

function findTarget(arr,target) {
    let i = 0; // i代表行
    let j = arr[i].length -1; // j每行中每项索引位置 从最后项开始比较
    while(i < arr.length && j>=0) { 
        if(target < arr[i][j]) {
            j--;
        } else if (target > arr[i][j]) {
            i++;
        } else {
            return `找到了,位置在${i},${j}`
        }
    }
    return `(${i},${j})`
}

let arr = [
  [1,2,3,4],
  [5,9,10,11],
  [13,20,21,23]
]  //测试

找出数组中重复出现过的元素

// 例如:[1,2,4,4,3,3,1,5,3]
// 输出:[1,3,4]
let arr = [1, 2, 4, 4, 3, 3, 1, 5, 3];

// 方法一
function repeat1(arr){
	var result = [], map = {};
	arr.map(function(num){
	if(map[num] === 1) result.push(num); // 等于1说明之前出现过一次 这次重复出现了
		map[num] = (map[num] || 0) + 1; // 微妙之处 开始第一次出现无值 记为 0 + 1 = 1 下一次从1开始累加
	});
	return result;
}
console.log(repeat1(arr));

// 方法二

function repeat(arr) {
    let result = arr.filter((x, i, self) => {
        return self.indexOf(x) === i && self.lastIndexOf(x) !== i
    }); // 
    return result;
}
console.log(repeat(arr));

根据数组中数字重复出现的次数排序

// 如果次数相同 则按照值排序 比如  2, 2, 21, 1, 1  应排序为 [1, 1, 1, 2, 2, 2]
// 比如 [1, 2, 1, 2, 1, 3, 4, 5, 4, 5, 5, 2, 2] => [3, 4, 4, 1, 1, 1, 5, 5, 5, 2, 2, 2, 2]

const repeatTimeSort = arr => {
  arr.sort((a, b) => a - b)
  let ary = []
  while (arr.length > 0) {
    let a = arr[0]
    let start = arr.indexOf(a)
    let end = arr.lastIndexOf(a) + 1
    ary.push(arr.splice(start, end - start))
  }
  ary.sort((a, b) => a.length - b.length)
  return ary.reduce((prev, cur) => prev.concat(cur), [])
}

// [ 12, 13, 13, 11, 11, 11 ]
console.log(repeatTimeSort([11, 12, 13, 11, 11, 13]))
// [ 3, 4, 4, 1, 1, 1, 5, 5, 5, 2, 2, 2, 2 ]
console.log(repeatTimeSort([1, 2, 1, 2, 1, 3, 4, 5, 4, 5, 5, 2, 2]))

不用循环,创建一个长度为 100 的数组,并且每个元素的值等于它的下标。

// 方法一 递归写法
function createArray(len, arr = []) {

    if (len > 0) {
        arr[--len] = len;
        createArray(len, arr);
    }
    return arr;
}
console.log(createArray(100)); 

// 方法二

// 下面评论中@MaDivH 提供的实现方法 长度为 100 的数组 
Array(100).fill().map((_,i)=>i+1);

// 方法三
[...Array(100).keys()]

将数组转换成关联结构树

const roles = [
  { id: 1, name: 'a', parentId: 0},
  { id: 2, name: 'b', 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: 2}
]
// const output = [{
//     id: 1,
//     name: 'a',
//     parentId: 0,
//     children: [
//       { id: 3, name: 'c', parentId: 1, children: [] },
//       { id: 4, name: 'd', parentId: 1, children: [] }
//     ]
//   },
//   {
//     id: 2,
//     name: 'b',
//     parentId: 0,
//     children: [
//       { id: 5, name: 'e', parentId: 2 },
//       { id: 6, name: 'f', parentId: 2 }
//     ]
//   }
// ]


function convert(roles) {
  const root = []
  const dict = {}
  roles.forEach(item => {
    if (item.parentId === 0) {
      root.push(item)
    }
    item.children = []
    dict[item.id] = item
  })
  
  roles.forEach(item => {
    if (item.parentId !== 0) {
      dict[item.parentId].children.push(item)
    }
  })
  return root
}

console.log(convert(roles))

JSON扁平化的数据转换成树形结构的JSON(json -> tree, tree -> json)

const json = [{
  id: 1,
  name: '1',
  parentId: 0
}, {
  id: 3,
  name: '3',
  parentId: 0
}, {
  id: 11,
  name: '11',
  parentId: 1
}, {
  id: 12,
  name: '12',
  parentId: 1
}, {
  id: 13,
  name: '13',
  parentId: 1
}, {
  id: 111,
  name: '111',
  parentId: 11
}, {
  id: 112,
  name: '112',
  parentId: 2
}, {
  id: 21,
  name: '21',
  parentId: 2
}, {
  id: 211,
  name: '211',
  parentId: 21
}, {
  id: 1111,
  name: '1111',
  parentId: 111
}, {
  id: 2,
  name: '2',
  parentId: 0
}]

// json -> tree JSON扁平数据转换为Tree形数据
const jsonToTree = (jsonData, option) => {
  const _defaultOption = {
    id: 'id',
    pid: 'pid',
    children: 'children',
    rid: 0
  }

  const {
    id,
    pid,
    children,
    rid
  } = Object.assign({}, _defaultOption, option)

  const map = {}
  const tree = []
  jsonData.reduce((map, item) => {
    map[item[id]] = item
    if (item[pid] === rid) {
      tree.push(item)
    }
    return map
  }, map)
  json.forEach(item => {
    if (map[item[pid]]) {
      (map[item[pid]][children] || (map[item[pid]][children] = [])).push(item)
    }
  })
  return tree
}
const treeData = jsonToTree(json, {
  id: 'id',
  pid: 'parentId',
  children: 'children'
})
// console.log('tree', JSON.stringify(treeData, null, 2))

// tree -> json 树结构转换为JSON扁平数据
const treeToJson = (tree, option) => {
  const _defaultOption = {
    pid: 'pid',
    children: 'children',
  }

  const {
    children
  } = Object.assign(_defaultOption, option)

  const json = []
  const map = (data) => {
    const queue = []
    data.forEach(item => {
      queue.push(item)
    })
    while (queue.length) {
      const item = queue.shift()
      const children = item.children
      item.children = null
      delete item.children
      json.push({
        ...item
      })
      if (children) {
        children.forEach(child => queue.push(child))
      }
    }
  }
  map(tree)
  console.log('json', json)
}
treeToJson(treeData, {
  pid: 'parent',
  children: 'kids'
})

根据关键词找出 所在对象id

var docs = [
    {
        id: 1,
        words: ['hello', "world"]
    }, {
        id: 2,
        words: ['hello', "hihi"]
    }, {
        id: 3,
        words: ['haha', "hello"]
    }, {
        id: 4,
        words: ['world', "nihao"]
    }
];
findDocList(docs, ['hello']) // 文档id1,文档id2,文档id3
findDocList(docs, ['hello', 'world']) // 文档id1
function findDocList(docs, word = []) {
    if (word.constructor !== Array) return;
    let ids = [];
    for (let i = 0; i < docs.length; i++) {
        let {id, words} = docs[i];
        let flag = word.every((item) => {
            return words.indexOf(item) > -1;
        });
        flag && ids.push(id);
    }
    return ids;
}
findDocList(docs, ['hello', 'world']);

全排列

const permute = function(nums) {
  if (nums.length <= 1) return [nums]

  const permutes = []
  for (let i = 0; i < nums.length; i++) {
    const num = nums[i]
    const others = nums.slice(0, i).concat(nums.slice(i + 1))
    const list = permute(others)
    list.forEach(item => {
      permutes.push([num].concat(item))
    })
  }
  return permutes
};
const arr = [1, 2, 3]
console.log(permute(arr))

getElementsByClassName 兼容写法

  function getByClass(cName) {
      if ('getElementsByClassName' in this) {
          return this.getElementsByClassName(cName);
      }
      cName = cName.replace(/(^\s+|\s+$)/g, '').split(/\s+/g);
      let eles = this.getElementsByTagName('*');
     for (let i = 0; i < cName.length; i++) {
        let reg = new RegExp(`(^| )${cName[i]}( |$)`);
        let temp = [];
        for (let j = 0; j < eles.length; j++) {
            let cur = eles[j];
            let {className} = cur;
            if (reg.test(className)) {
                temp.push(cur);
            }
        }
        eles = temp;
     }
     return eles;
  }
  console.log(content.getByClass('c1 c2 '));

插入排序

插入排序 从后往前比较 直到碰到比当前项 还要小的前一项时 将这一项插入到前一项的后面

function insertSort(arr) {
  let len = arr.length;
  let preIndex, current;
  for (let 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;
}
function insert(arr, i, x) {
  let prev = i - 1;
  while(prev >= 0 && arr[prev] > x) {
    arr[prev + 1] = arr[prev];
    prev--;
  }
  arr[prev + 1] = x;
}

function insert_sort(arr) {
  for (let i = 1; i < arr.length; i++) {
    insert(arr, i, arr[i]);
  }
  return arr;
}

console.log(insert_sort([1, 10, 3, 0]));

选择排序

选择排序 每次拿当前项与后面其他项进行比较 得到最小值的索引位置 然后把最小值和当前项交换位置

function selectSort(arr) {
  let len = arr.length;
  let temp = null;
  let minIndex = null;
  for (let i = 0; i < len - 1; i++) { // 把当前值的索引作为最小值的索引一次去比较
    minIndex = i; // 假设当前项索引 为最小值索引
    for (let j = i + 1; j < len; j++) { // 当前项后面向一次比小
      if (arr[j] < arr[minIndex]) { // 比假设的值还要小 则保留最小值索引
        minIndex = j; // 找到最小值的索引位置
      }
    }
    // 将当前值和比较出的最小值交换位置
    if (i !== minIndex) {
       temp = arr[i]
       arr[i] = arr[minIndex];
       arr[minIndex] = temp;
    }
  }
  return arr;
}

冒泡排序

冒泡排序 相邻两项进行比较 如果当前值大于后一项 则交换位置

冒泡1


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

function bubleSort(arr) {
  let length = arr.length;
  let temp = null;
  for (let i = 0; i < length - 1; i++) { // 控制轮数
    let flag = false; // 当前这轮是否交换过标识
    for (let l = 0; l < length - i - 1; l++) { // 控制每轮比较次数
      if (arr[l] > arr[l + 1]) {
        // temp = arr[l];
        // arr[l] = arr[l + 1];
        // arr[l + 1] = temp;
        swap(arr, l, l + 1);
        flag = true; // 如果发生过交换flag则为true
      } 
    }
    if (!flag) { // 优化  如果从头到尾比较一轮后 flag依然为false说明 已经排好序了 没必要在继续下去
      temp = null;
      return arr;
    }
  }
  return arr;
}

冒泡2

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

function bubble_sort(arr) {
  for (let i = arr.length - 1; i >= 1; i--) {
    for (let j = 1; j <= i; j++) {
      arr[j - 1] > arr[j] && swap(arr, j - 1, j)
    }
  }
  return arr;
}

console.log(bubble_sort([1, 10, 3, 0]));

快速排序(阮一峰版)

function quickSort(arr) {
    if (arr.length <= 1) return arr;
    let midIndex = Math.floor(arr.length / 2);
    let midNum = arr.splice(midIndex, 1)[0];
    let left = [];
    let right = [];
    for(let i = 0; i < arr.length; i++) {
        let cur = arr[i];
        if (cur <= midNum) {
            left.push(cur);
        } else {
            right.push(cur);
        }
    }
    return quickSort(left).concat(midNum, quickSort(right));
}

let arr = [2, 4, 12, 9, 22, 10, 18, 6];
quickSort(arr);

快速排序 第二版

let array = [9, 6, 20, 3, 2];
// let array = [15, 13, 20, 21, 29];

function quickSort(arr, left = 0, right = arr.length - 1) {
  let len = arr.length;
  let 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) {
  let pivot = left;
  let index = pivot + 1;
  for (let 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, index) {
  [arr[i], arr[index]] = [arr[index], arr[i]];
}
console.log(quickSort(array));

归并排序

let array = [5, 13, 20, 3, 2];
// let array = [15, 13, 20, 21, 29];

function mergeSort(array) {
  let arr = array.slice(0);
  let len = arr.length;
  if (len < 2) {
    return arr;
  }
  let midIndex = Math.floor(len / 2);
  let left = arr.slice(0, midIndex);
  let right = arr.slice(midIndex);
  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  let result = [];
  while(left.length && right.length) {
    result.push(left[0] < right[0] ? left.shift() : right.shift());
  }

  if (left.length && !right.length) {
    result = result.concat(left);
  }

  if (right.length && !left.length) {
    result = result.concat(right);
  }
  return result;
}

console.log(mergeSort(array));

数组去重几种方法

const arr = [1, 2, 1, 2, 3, 4, 2, 1, 3];

// 1 ES6
let newArr = [...new Set(arr)];

// 2
const arr = [1, 2, 1, 2, 3, 4, 'l', 2, 1, 3, 'l'];
const newArr = arr.filter(function(ele, index, array) {
	return index === array.indexOf(ele)
});
console.log(newArr); // [ 1, 2, 3, 4, 'l' ]

// 3
Array.prototype.unique2 = function() {
    let newArr = [];
    let len = this.length;
    for(let i = 0; i < len; i++) {
        let cur = this[i];
        if(newArr.indexOf(cur) === -1) {
            newArr[newArr.length] = cur;
        }
    }
    return newArr;
}
console.log(arr.unique1());

// 4
Array.prototype.unique3 = function() {
    let newArr = this.slice(0);
    let len = this.length;
    let obj = {};
    for(let i = 0; i < len; i++) {
        let cur = newArr[i];
        if(obj[cur]) {
            newArr[i] = newArr[newArr.length - 1];
            newArr.length--;
            i--;
            continue;
        }
        obj[cur] = cur;
    }
    return newArr;
}
console.log(arr.unique3());

// 5
Array.prototype.unique4 = function() {
    let json = {}, newArr = [], len = this.length;
    for(var i = 0; i < len; i++) {
        let cur = this[i];
        if (typeof json[cur] == "undefined") {
            json[cur] = true;
            newArr.push(cur)
        }
    }
    return newArr;
}
console.log(arr.unique4());

千分符

方法一

// 处理数字
let str1 = 2123456789;
let str2 = 2123456789.12;
console.log(str1.toLocaleString()); // 2,123,456,789
console.log(str2.toLocaleString()); // 2,123,456,789.12

方法二

    // 处理字符串
    let str1 = '2123456789';
    let str2 = '2123456789.12';

    // 利用正向预查 匹配 开头一个数字\d 后面匹配这个数字后面必须是三个数字为一组为结尾或小数为结尾
    function thousandth(str) { 
        let reg = /\d(?=(?:\d{3})+(?:\.\d+|$))/g; 
        return str.replace(reg, '$&,');
    }
    console.log(thousandth(str1)); // 2,123,456,789
    console.log(thousandth(str2)); // 2,123,456,789.12

求a的值 什么情况下 满足if (a == 1 & a == 2 & a == 3)这个条件

var a = {
  a: 1,
  valueOf() {
    return this.a++
  }
}

if (a == 1 & a == 2 & a == 3) {
  console.log(1)
}

在一个数组中 如a、b两项, 要保证a和b两项的差 与 a和b两项索引的差 的相加后的结果max 是数组中其他两项max 中的最大值 找出符合条件两项a, b的值 (不可以排序 或改变数组位置) 如:

let max = (a - b) + (a的索引- b的索引); 求a b

答案:

// 思路:其实也就是找出数组中当前的每一项与自身索引相加后的和的最大值以及与索引相加后的最小值的和 找出符合条件的两项即可 如 let result = (maxItem-minItem) + (maxIndex-minIndex) 等价于 (maxItem+maxIndex) - (minItem+minIndex)

// let arr = [1, 2, 3, 4, 5, 6]; // 最简单的测试数组 最小项1 最大项6
// 很显然这个数组中最大值6与索引相加(6+5)是当中最大值11 1与索引相加(1+0)为当中的最小值1(6 + 5)-(1+0)= 10

// 假设法
let arr = [2, 10, 9, 1, 8, 3, 4];
let minItem = arr[0]; // 假设第一项与自身索引的和是最小值 索引为0因此省略
let maxItem = arr[0]; // 假设第一项与自身索引的和是最大值 索引为0因此省略
let min = minItem; // 最小项
let max = maxItem; // 最大项
let minIndex = 0; // 最小项索引
let maxIndex = 0; // 最大项索引
for(let i = 1; i < arr.length; i++) {
    let cur = arr[i] + i; // 当前项和自身索引的和
    cur < minItem ? (minItem = cur, min = arr[i], minIndex = i) : null;
    cur > maxItem ? (maxItem = cur, max = arr[i], maxIndex = i) : null;
}
console.log(maxItem, minItem); // 最大项与索引的和 最小项与索引的和
console.log(max, min); // 最大项 最小项
console.log(maxIndex, minIndex); // 最大项的索引 最小项的索引

检测 字符串中括号表达式是否平衡

// 如 balance('[()') = false; balance('[()()()]') = true
// 一
function match(a, b) {
	return (a === '(' && b === ')') || (a === ')' && b === '(') || (a === '[' && b === ']') || (a === ']' && b === '[');
}

function balance(str) {
	if (str.length % 2 === 0) {
		let len = str.length;
		for (let i = 0, j = len - 1; i < len / 2; i++, j--) {
			if (!match(str[i], str[j])) {
				return false;
			}
		}
		return true;
	}
	return false;
}
console.log(balance('[()()()]')); // true
console.log(balance('[()')); // false
console.log(balance('[]()')); // false
// 二
function is_balance(str) {
	return [...str].reduce((stack, c) => {
		match(stack[stack.length - 1], c) ?
			stack.pop() : stack.push(c);
		return stack;
	}, []).length === 0;
}
console.log(is_balance('[()()()]')); // true
console.log(is_balance('[()')); // false
console.log(is_balance('[]()')); // false

三数之和

// 三数之和
const threeSum = (nums) => {
  nums.sort((a, b) => a - b)

  const result = []
  for (let i = 0, len = nums.length; i < len; i++) {
    if (nums[i] > 0) break
    // 重复值略过
    if (i > 0 && nums[i] === nums[i - 1]) continue
    let l = i + 1 // 左指针
    let r = len - 1 // 右指针
    while (l < r) {
      const sum = nums[i] + nums[l] + nums[r]
      if (sum > 0) {
        r--
      } else if (sum < 0) {
        l++
      } else { // === 0
        result.push([nums[i], nums[l], nums[r]])
        // 下一项是重复值略过
        while (l < r && (nums[l] === nums[l + 1])) l++
        // 下一项是重复值略过
        while (l < r && (nums[r] === nums[r - 1])) r--
        l++
        r--
      }
    }
  }
  return result
}

求相邻两项最大和

// 一
let arr1 = [-1, 3, 1, -5, 2]; // 如 [2, 4, -4, -3] => 4
function sum(arr) {
    let prev = arr[0];
    let sumArr = [];
    let len = arr.length;
    for(let i = 1; i < len; i++) {
        let cur = arr[i];
        sumArr.push(cur + prev);
        prev = cur;
    }   
    return Math.max(...sumArr);
}
console.log(sum(arr1));

// 二
function maxsum(arr) {
    const M = [arr[0]];
    let max = M[0];
    
    for(let i = 1; i < arr.length; i++) {
        M[i] = Math.max(arr[i], M[i - 1] + arr[i]);
        max = Math.max(M[i], max);
    }
    return max;
}

字符串去除相邻的重复项 如:'aabbccddeexxxxaa' => 'abcdexa'

// 正则表达式
let str = 'aabbccddeexxxxaa';
function uniq1(str) {
    // return str.replace(/([a-z])(\1){1,}/g, '$1');
    return str.replace(/(.)(?=\1)/g, '');
}
console.log(uniq1(str));

// 数组方式
function uniq2(str) {
    let arr = str.split('');
    let newArr = [arr[0]];
    for(let i = 1; i < arr.length; i++) {
        let cur = arr[i];
        if (cur !== newArr[newArr.length - 1]) {
            newArr.push(cur);
        }
    }
    return newArr.join('');
}
console.log(uniq2(str));

属性组合

image.png

const permutation = (attr) => {
  const ans = [], keys = Object.keys(attr)
  function dfs(tmp, cur) {
      if (keys.length === cur) return ans.push(tmp.slice());
      const key = keys[cur], arr = attr[key];
      for (let i = 0; i < arr.length; i++) {
          tmp.push(`${key}:${arr[i]}`);
          dfs(tmp, cur + 1);
          tmp.pop();
      }
  }
  dfs([], 0);
  return ans;
}
console.log(permutation(attr))
// [
//   [ 'color:white', 'size:large', 'type:oversize' ],
//   [ 'color:white', 'size:large', 'type:suit' ],
//   [ 'color:white', 'size:large', 'type:tight' ],
//   [ 'color:white', 'size:medium', 'type:oversize' ],
//   [ 'color:white', 'size:medium', 'type:suit' ],
//   [ 'color:white', 'size:medium', 'type:tight' ],
//   [ 'color:white', 'size:small', 'type:oversize' ],
//   [ 'color:white', 'size:small', 'type:suit' ],
//   [ 'color:white', 'size:small', 'type:tight' ],
//   [ 'color:red', 'size:large', 'type:oversize' ],
//   [ 'color:red', 'size:large', 'type:suit' ],
//   [ 'color:red', 'size:large', 'type:tight' ],
//   [ 'color:red', 'size:medium', 'type:oversize' ],
//   [ 'color:red', 'size:medium', 'type:suit' ],
//   [ 'color:red', 'size:medium', 'type:tight' ],
//   [ 'color:red', 'size:small', 'type:oversize' ],
//   [ 'color:red', 'size:small', 'type:suit' ],
//   [ 'color:red', 'size:small', 'type:tight' ],
//   [ 'color:blue', 'size:large', 'type:oversize' ],
//   [ 'color:blue', 'size:large', 'type:suit' ],
//   [ 'color:blue', 'size:large', 'type:tight' ],
//   [ 'color:blue', 'size:medium', 'type:oversize' ],
//   [ 'color:blue', 'size:medium', 'type:suit' ],
//   [ 'color:blue', 'size:medium', 'type:tight' ],
//   [ 'color:blue', 'size:small', 'type:oversize' ],
//   [ 'color:blue', 'size:small', 'type:suit' ],
//   [ 'color:blue', 'size:small', 'type:tight' ]
// ]

资源分享

JavaScript基础在线教程文档

从零开始-打造一个JavaScript完整在线教程文档

Github一些原理实现

JavaScript数据结构与算法pdf资源

百度网盘 密码:ll8d

害怕手写代码 😨 只能硬着头皮

欢迎大家和我一起来补充 上面很多也都是可以优化的 我还是一个成长中的小白,只是分享和记录下自己碰到的问题 后续会持续更新...