前端算法集合

使用前介绍

// How to export and import 
module.exports = swap; --> 对应 var s = require('../*.js');
// 或：
export default swap --> 对应 import s from '../*.js'
// 或:
export {swap} --> 对应 import {swap} from '../*.js'

不借助临时变量，交换整数

加减乘除法

注意：如果是浮点数，对于加减乘除法需要注意浮点数的精度丢失问题。

// 思想：先求两个数的“和”，再用“和”去减
function swap(a, b) { // 如 [1, 3]
  a = a + b; // a = 1 + 3 = 4
  b = a - b; // b = 4 - 3 = 1
  a = a - b; // a = 4 - 1 = 3
  return [a, b]; // [3, 1]
}

// 思想：先求两个数的“差”，再用“差”去加
function swap(a, b) { // 如 [3, 1]
  a = a - b; // a = 3 - 1 = 2
  b = a + b; // b = 2 + 1 = 3
  a = b - a; // a = 3 - 2 = 1
  return [a, b]; // [1, 3]
}

// 思想：先求两个数的“乘积”，再用“乘积”去除
function swap(a, b) { // 如 [3, 8]
  a = a * b; // a = 3 * 8 = 24
  b = a / b; // b = 24 / 8 = 3
  a = a / b; // a = 24 / 3 = 8
  return [a, b]; // [8, 3]
}

// 思想：先求两个数的“商”，再用“商”去乘
function swap(a, b) { // 如 [8, 3]
  a = a / b; // a = 8 / 3 = 8 / 3
  b = a * b; // b = (8 / 3) * 3 = 8
  a = b / a; // a = 8 / (8 / 3) = 3
  return [a, b]; // [3, 8]
}

对象法

function swap(a, b) { // 如 [1, 3]
  a = {
    a: b,
    b: a
  }
  b = a.b; // 1
  a = a.a; // 3
  return [a, b]; // [3, 1]
}

数组法

function swap(a, b) { // 如 [1, 3]
  a = [a, b];
  b = a[0]; // 1
  a = a[1]; // 3
  return [a, b]; // [3, 1]
}

function swap(a, b) { // 如 [1, 3]
  a = [b, b = a][0]; // a = 3, b = 1;
  return [a, b]; // [3 ,1]
}

ES6数组解构法，推荐

function swap(a, b) { // 如 [1, 3]
  [a, b] = [b, a];
  return [a, b];
}

数组去重

方法1（filter，推荐使用）

// filter函数会过滤出满足条件的元素
function uniqueArr(arr){
  var newArr = arr.filter((item, index, self) => { // 三个参数依次是：当前项、索引值、arr对象
    return self.indexOf(item) === index; // 对于重复的元素，只有第一个元素符合条件，后面的都会被过滤掉
  });
  return newArr;
}

方法2（新数组法）

function uniqueArr(arr){
  var newArr = []; // 一个新的临时数组
  for(var i = 0; i < arr.length; i++){ // 遍历当前数组
    // 如果当前数组的第i项已经保存进了临时数组，那么跳过，
    // 否则把当前项push到临时数组里面
    if (newArr.indexOf(arr[i]) === -1){ // 在新数组中查找原数组的每一项是否存在
      newArr.push(arr[i]); // 如果不存在就加到新数组中
    }
  }
  return newArr;
}

方法3（hash表法）

function uniqueArr(arr) {
  var obj = {}, newArr = []; // obj为hash表，newArr为临时数组
  for(var i = 0; i < arr.length; i++) { // 遍历当前数组 , 可改成 for (var i in arr) {
    if (!obj[arr[i]]){ // 如果hash表中没有当前项
      obj[arr[i]] = true; // 存入hash表
      newArr.push(arr[i]); // 把当前数组的当前项push到临时数组里面
    }
  }
  return newArr;
}

方法4

function uniqueArr(arr) {
  var newArr = [arr[0]]; // 结果数组
  for (var i = 1; i < arr.length; i++) { // 从第二项开始遍历
    // 如果当前数组的第i项在当前数组中第一次出现的位置不是i，
    // 那么表示第i项是重复的，忽略掉。否则存入结果数组
    if (arr.indexOf(arr[i]) === i) {
      newArr.push(arr[i]);
    }
  }
  return newArr;
}

方法5（同时排序）

function uniqueArr(arr){
  arr.sort(); // 数组排序
  var newArr = [arr[0]]; // 先提取最小的
  for (var i = 1; i < arr.length; i++) {
    if (arr[i] !== newArr[newArr.length-1]) { // 将不等于的放在新数组的后面，等于的跳过
      newArr.push(arr[i]);
    }
  }
  return newArr;
}

方法6（set + Array.from）

function uniqueArr(arr) {
  // new Set(arr); // input: [2, 3, 4, 5, 3, 5], output: {2, 3, 4, 5}
  return Array.from(new Set(arr));
}

方法7（set + …扩展运算符）

function uniqueArr(arr) {
  // new Set(arr); // input: [2, 3, 4, 5, 3, 5], output: {2, 3, 4, 5}
  return [...new Set(arr)];
}

实现数组的扁平化

将多维数组变成一位数组：如[1, [2, 3, [4, 5]]] => [1, 2, 3, 4, 5]

toString

局限性：使用 toString() 方法后，所有的元素类型都变成了字符串，再使用Number还原，假设原数组中存在类型不一的元素，则不能还原类型

function flatten(arr) {
  return arr.toString().split(',').map(item => {
    return Number(item)
  })
}
flatten([1, [2, 3, [4, 5]]])

flat

[1, [2, 3]].flat() // 只适用于二维数组

reduce

遍历每一项，如果值为数组，则递归遍历

function flatten(arr) {
  return arr.reduce((result, item, index, arr) => {
    return result.concat(Array.isArray(item) ? flatten(item) : item)
  }, [])
}
flatten([1, [2, 3, [4, 5]]])

递归

function flatten(arr) {
  var result = []
  arr.forEach(item => {
    if (Array.isArray(item)) {
      result = result.concat(flatten(item)) // 此处的递归很巧妙
    } else {
      result.push(item)
    }
  })
  return result
}
flatten([1, [2, 3, [4, 5]]])

es6扩展运算符…

function flatten(arr) {
  while (arr.some(item => Array.isArray(item))) {
    arr = [].concat(...arr)
  }
  return arr
}
flatten([1, [2, 3, [4, 5]]])

数组中含所有不定类型值的去重

普通法

function uniqueArr(arr) {
  for(let i = 0, len = arr.length; i < len; i++){
    // 先处理特殊的类型：array、object、null
    if (typeof arr[i] === 'object' || Array.isArray(arr[i]) || ) {

    }
  }
}

map法

function uniqueArr(arr) {
    var res = [];
    var o = Object.create(null); // 创建一个完全干净的空对象，内部没有__proto__属性
    for(let v of arr) {
        var type = typeof v;
        if(!o[v]) {
            res.push(v);
            o[v] = [type];
        }else if(o[v].indexOf(type) == -1) {
            o[v].push(type);
             res.push(v);
        }
    }
    return res;
}

取数组中的最大最小值

排序法

var arr = [0, 2, 5, 1, 4, 3];

arr.sort(function (a, b) {
  return a - b;
}); // [0, 1, 2, 3, 4, 5]

var min = arr[0];  // 0
var max = arr[arr.length - 1];  // 5

apply方法

Math.max.apply(null, [1, 2, 3, 4]);
Math.min.apply(null, [1, 2, 3, 4]);

// apply()方法
function.apply(thisObj[, argArray]); // 2个参数，参数2为数组

// call()方法
function.call(thisObj[, arg1[, arg2[, [, ...argN]]]]); // 多个参数，其他参数为非数组

// 同理，利用apply方法还可以用于拼接数组：
var arr1 = new Array("1", "2", "3");
var arr2 = new Array("4", "5", "6");
Array.prototype.push.apply(arr1, arr2); // 返回数组长度 6
arr1.push.apply(arr1, arr2); // arr1:["1", "2", "3", "4", "5", "6"]
// 上面的等同于
arr1.push(...arr2); // ES6语法
arr1.concat(arr2); // ES5语法


// 更多apply和call用法见：https://www.cnblogs.com/lengyuehuahun/p/5643625.html

数组排序

参考：segmentfault【wscats】 十大经典排序算法

冒泡排序

1. 比较相邻的元素，如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
5. 实际排序时，由后往前完成排序动作。

function bubbleSort(arr) {
  var len = arr.length;
  for (var i = 0; i < len - 1; i++) {
    for (var j = 0; j < len - 1 - i; j++) {
      if (arr[j] > arr[j+1]) { // 相邻元素两两对比
        // 使用中间变量实现元素交互
        // var temp = arr[j+1];
        // arr[j+1] = arr[j];
        // arr[j] = temp;
        
        // es6数组解构实现元素交互
        [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
      }
    }
  }
  return arr;
}

// 假设arr是一个数组为5的数组
// i  j
// ----
// 0  0
// 0  1
// 0  2
// 0  3
// ----
// 1  0
// 1  1
// 1  2
// ----
// 2  0
// 2  1
// ----
// 3  0

// 由上面可以看出，取arr[j]和arr[j+1]即是两个相邻元素的比较


// 以数组[1, 8, 5, 4, 7, 3, 9, 2, 6]为例，实际冒泡排序如下：
// ① ⑧ 5 4 7 3 9 2 6   // 1与8比较 => 1 8 5 4 7 3 9 2 6
// 1 ⑧ ⑤ 4 7 3 9 2 6   // 8与5比较 => 1 5 8 4 7 3 9 2 6
// 1 5 ⑧ ④ 7 3 9 2 6   // 8与4比较 => 1 5 4 8 7 3 9 2 6
// 1 5 4 ⑧ ⑦ 3 9 2 6   // 8与7比较 => 1 5 4 7 8 3 9 2 6
// 1 5 4 7 ⑧ ③ 9 2 6   // 8与3比较 => 1 5 4 7 3 8 9 2 6
// 1 5 4 7 3 ⑧ ⑨ 2 6   // 8与9比较 => 1 5 4 7 3 8 9 2 6
// 1 5 4 7 3 8 ⑨ ② 6   // 9与2比较 => 1 5 4 7 3 8 2 9 6
// 1 5 4 7 3 8 2 ⑨ ⑥   // 9与6比较 => 1 5 4 7 3 8 2 6 9
// 
// ① ⑤ 4 7 3 8 2 9 6   // 1与5比较 => 1 5 4 7 3 8 2 6 9
// 1 ⑤ ④ 7 3 8 2 6 9   // 5与4比较 => 1 4 5 7 3 8 2 6 9
// 1 4 ⑤ ⑦ 3 8 2 6 9   // 5与7比较 => 1 4 5 7 3 8 2 6 9
// 1 4 5 ⑦ ③ 8 2 6 9   // 7与3比较 => 1 4 5 3 7 8 2 6 9
// 1 4 5 3 ⑦ ⑧ 2 6 9   // 7与8比较 => 1 4 5 3 7 8 2 6 9
// 1 4 5 3 7 ⑧ ② 6 9   // 8与2比较 => 1 4 5 3 7 2 8 6 9
// 1 4 5 3 7 2 ⑧ ⑥ 9   // 8与6比较 => 1 4 5 3 7 2 6 8 9
//
// ① ④ 5 3 7 2 6 8 9   // 1与4比较 => 1 4 5 3 7 2 6 8 9
// 1 ④ ⑤ 3 7 2 6 8 9   // 4与5比较 => 1 4 5 3 7 2 6 8 9
// 1 4 ⑤ ③ 7 2 6 8 9   // 5与3比较 => 1 4 3 5 7 2 6 8 9
// 1 4 3 ⑤ ⑦ 2 6 8 9   // 5与7比较 => 1 4 3 5 7 2 6 8 9
// 1 4 3 5 ⑦ ② 6 8 9   // 7与2比较 => 1 4 3 5 2 7 6 8 9
// 1 4 3 5 2 ⑦ ⑥ 8 9   // 7与6比较 => 1 4 3 5 2 6 7 8 9
// 
// ① ④ 3 5 2 6 7 8 9   // 1与4比较 => 1 4 3 5 2 6 7 8 9
// 1 ④ ③ 5 2 6 7 8 9   // 4与3比较 => 1 3 4 5 2 6 7 8 9
// 1 3 ④ ⑤ 2 6 7 8 9   // 4与5比较 => 1 3 4 5 2 6 7 8 9
// 1 3 4 ⑤ ② 6 7 8 9   // 5与2比较 => 1 3 4 2 5 6 7 8 9
// 1 3 4 2 ⑤ ⑥ 7 8 9   // 5与6比较 => 1 3 4 2 5 6 7 8 9
// 
// ... ...
// 
// ① ② 3 4 5 6 7 8 9   // 1与2比较 => 1 2 3 4 5 6 7 8 9

选择排序

1. 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
2. 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
3. 重复第二步，直到所有元素均排序完毕。

function selectionSort(arr) {
  var len = arr.length;
  var minIndex, temp;
  for (var i = 0; i < len - 1; i++) { // 此处循环到倒数第二项即可，届时最后一项已经完成排序（最大或最小）
    minIndex = i; // 假设次数最小数的索引为当前i

    for (var j = i + 1; j < len; j++) { // 遍历i之后的数
      if (arr[j] < arr[minIndex]) { // 存在比minIndex还小的数
        minIndex = j;               // 将最小数的索引赋给minIndex
      }
    }
    // 此时minIndex可能等于i（即上面遍历之后不存在更小的），也可能不等于i（存在更小的，即arr[minIndex] < arr[i]）;
    // 但是此时minIndex >= i，所以我们交换arr[i]和arr[minIndex]的位置即可

    // 将 minIndex对应的数 放在当前索引对应的数的前面
    // temp = arr[i];
    // arr[i] = arr[minIndex];
    // arr[minIndex] = temp;

    // es6数组结构实现元素交换
    [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
  }
  return arr;
}

// 以数组[1, 8, 5, 4, 7, 3, 9, 2, 6]为例，实际选择排序如下：
// ① 8 5 4 7 3 9 2 6   // 1与1交换
// 
// 1 ⑧ 5 4 7 3 9 ② 6  // 8与2交换
// 1 2 5 4 7 3 9 8 6
// 
// 1 2 ⑤ 4 7 ③ 9 8 6  // 5与3交换
// 1 2 3 4 7 5 9 8 6
// 
// 1 2 3 ④ 7 5 9 8 6   // 4与4交换
// 1 2 3 4 7 5 9 8 6
// 
// 1 2 3 4 ⑦ ⑤ 9 8 6  // 7与5交换
// 1 2 3 4 5 7 9 8 6
// 
// 1 2 3 4 5 ⑦ 9 8 ⑥  // 7与6交换
// 1 2 3 4 5 6 9 8 7
// 
// 1 2 3 4 5 6 ⑨ 8 ⑦  // 9与7交换
// 1 2 3 4 5 6 7 8 9
// 
// 1 2 3 4 5 6 7 ⑧ 9   // 8与8交换
// 1 2 3 4 5 6 7 8 9

快速排序

1. 从数列中挑出一个元素，称为 “基准”（pivot）;
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }

  let leftArr = [];
  let rightArr = [];
  let pivot = arr[0]; // 选择第一项作为基准值
  for (let i = 1; i < arr.length; i++) { // 从1开始遍历，因为0已经作为基准值使用了
    if (arr[i] > pivot) {
      rightArr.push(arr[i]);     
    } else{
      leftArr.push(arr[i]);
    }
  }
  return [].concat(quickSort(leftArr), [pivot], quickSort(rightArr)); // 拼接左分区、基准值、右分区（进行递归）
}

// 以数组[1, 8, 5, 4, 7, 3, 9, 2, 6]为例，实际快速排序如下：
// arr:[1, 8, 5, 4, 7, 3, 9, 2, 6] 
// ├── left: []
// │
// ├── pivot: 1
// │
// └── right:[8, 5, 4, 7, 3, 9, 2, 6]
//     │
//     ├── left: [5, 4, 7, 3, 2, 6]
//     │   │
//     │   ├── left: [4, 3, 2]
//     │   │   │
//     │   │   ├── left: [3, 2]
//     │   │   │   │ 
//     │   │   │   ├── left: [2]
//     │   │   │   │
//     │   │   │   ├── pivot: 3
//     │   │   │   │
//     │   │   │   └── right: []
//     │   │   │    
//     │   │   ├── pivot: 4
//     │   │   │
//     │   │   └── right: []
//     │   │   
//     │   ├── pivot: 5
//     │   │
//     │   └── right: [7, 6]
//     │       │
//     │       ├── left: [6]
//     │       │
//     │       ├── pivot: 7
//     │       │
//     │       └── right: []
//     │ 
//     ├── pivot: 8
//     │
//     └── right: [9]
//     
// 
// 按上图拆分完毕后，从内到外拼接（递归）即可完成排序得到：[1, 2, 3, 4, 5, 6, 7, 8, 9]

插入排序

1. 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
2. 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

function insertionSort(arr) {
  var len = arr.length;
  var preIndex, current;
  for (var i = 1; i < len; i++) {
    preIndex = i - 1;
    current = arr[i];
    while(preIndex >= 0 && arr[preIndex] > current) {
      arr[preIndex+1] = arr[preIndex];
      preIndex--;
    }
    arr[preIndex+1] = current;
  }
  return arr;
}

二路归并排序

将两个按值有序序列合并成一个按值有序序列

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

  while (il < left.length && ir < right.length) {
    if (left[il] < right[ir]) {
      result.push(left[il++]);
    } else {
      result.push(right[ir++]);
    }
  }
  while(left[il]){
    result.push(left[il++]);
  }
  while(right[ir]){
    result.push(right[ir++]);
  }
  return result;
}

希尔排序

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

其他排序应用

数字、英文排序

// 顺序：
function sortArr (arr){
  return arr.sort();
}
// 或：
function sortArr (arr){
  return arr.sort(function (a, b) {
    return a > b
  });
}

// 倒序：
function sortArr (arr){
  return arr.sort(function (a, b) {
    return a < b
  });
}

中文姓名排序

// 顺序
function sortNameArr (arr) {
  return arr.sort(function (a, b) {
    return b.localeCompare(a, 'zh-Hans-CN')
  })
}

// 倒序
function sortNameArr (arr) {
  return arr.sort(function (a, b) {
    return a.localeCompare(b, 'zh-Hans-CN')
    })
}

数组乱序

遍历法

取随机位的值与当前的互换

function shuffle(arr) {
  for (var i = arr.length - 1; i > 0; i--) {
    var j = Math.floor(Math.random() * (i + 1));
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
  return array;
 }

sort法

随机数大于0.5的概率为1/2，然后选择顺序或倒序即可

function shuffle(arr) {
  arr.sort((a, b) => {
    var sign = (Math.random() > 0.5) ? 1 : -1;
    return (a - b) * sign;
  });
}

Number数组中最大差值

function getMaxProfit (arr) {
  var min = arr[0], max = arr[0];
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] < min) {
      min = arr[i];
    }
    if (arr[i] > max) {
      max = arr[i];
    }
  }
  return max - min;
}

打印九九乘法表

for (var n = 1; n <= 9; n++) {
  for (var m = 1; m < n+1; m++) {
    var b = m * n;
    document.write(m + "×" + n + "=" + b + " ");
  }
  document.write("<br/><br/>");
}

求数组交集和差级

ES7方法：

let intersection = a.filter(v => b.includes(v))
 
let difference = a.concat(b).filter(v => !a.includes(v) || !b.includes(v))

字符串翻转

转换成array

function reverseString(str) {
  return str.split('').reverse().join();
}

反向遍历

function reverseString(str){
  var tmp = '';
  for(var i = str.length - 1;i >= 0; i--)
    tmp += str[i];
  return tmp
}

生成随机字符串

function randomString(n){
  var str = 'abcdefghijklmnopqrstuvwxyz0123456789';
  var tmp = '';
  for(var i = 0; i < n; i++)
    tmp += str.charAt(Math.round(Math.random()*str.length));
  return tmp;
}

判断回文

// 算法思想：每次判断第一个字符和最后一个字符是否相等，然后取第二个字符到倒数第二个字符之间的字符串递归
function palindrome(str){
  // \W匹配任何非单词字符，即去除非正常字符。等价于“[^A-Za-z0-9_]”。
  var re = /[\W_]/g;
  // 将字符串变成小写字符,并干掉除字母数字外的字符
  var lowRegStr = str.toLowerCase().replace(re, '');
  // 如果字符串lowRegStr的length长度为0时，字符串即是palindrome
  if(lowRegStr.length === 0)
    return true;
  // 如果字符串的第一个和最后一个字符不相同，那么字符串就不是palindrome
  if(lowRegStr[0] !== lowRegStr[lowRegStr.length - 1])
    return false;
  //递归
  return palindrome(lowRegStr.slice(1, lowRegStr.length - 1));
}

统计出现最多的元素

最常见的思路是先使用object统计出元素和个数，再循环取最大的，但这样无疑会增加复杂度。所以需要在第一次遍历的时候就缓存好最大的元素。

统计字符串中最多的字母和出现的次数

// 算法思想：先遍历，将出现的字符和次数以object的形式输出；再obj遍历，输出次数最多的字符
function findMaxDuplicateChar(str) {
  if(str.length == 1) {
    return str;
  }
  var charObj = {};
  var maxElArr = [str.charAt(0), 0];//  次数最多的元素和次数，默认为第一个
  for(var i = 0; i < str.length; i++) {
    if(!charObj[str.charAt(i)]) {
      charObj[str.charAt(i)] = 1;
    } else {
      charObj[str.charAt(i)] += 1;
      if (charObj[str.charAt(i)] >= maxElArr[1]) {
        maxElArr = [str.charAt(i), charObj[str.charAt(i)]];
      }
    }
  }
  console.log(charObj, maxElArr);
  return maxElArr;
}

统计数组中出现最多次数的元素和次数

function findMaxDuplicateArr(arr) {
  if(arr.length == 1) {
    return arr[0];
  }

  var obj = {};
  var maxElArr = [arr[0], 0]; //  次数最多的元素和次数，默认为第一个
  for(var i = 0; i < arr.length; i++) {
    if(!obj[arr[i]]) {
      obj[arr[i]] = 1;
    } else {
      obj[arr[i]] += 1;
      if (obj[arr[i]] >= maxElArr[1]) {
        maxElArr = [arr[i], obj[arr[i]]];
      }
    }
  }
  console.log(obj, maxElArr);
  return maxElArr;
}

阶乘

1x2x3x4x5…

递归

function factorialize(num) {
  var result = 1;
  if(num < 0) return -1;
  if(num == 0 || num == 1) return 1;
  if(num > 1){
    return num * factorialize(num - 1);
  }
}

非递归

function factorialize(num) {
  var result = 1;
  if(num < 0) return -1;
  if(num == 0 || num == 1) return 1;
  while(num > 1)
    result *= num--;
  return result;
}

生成斐波那契数列

斐波那契数列（黄金分割数列）: 0、1、1、2、3、5、8、13、21、34，考察递归

递归

function getfib(n){
  if (n == 0)
    return 0;
  if (n == 1)
    return 1;
  if (n > 1) {
    return getfib(n - 1) + getfib(n - 2);
  }
}
function fibo(len){
  var fibo = [];
  for(var i = 0; i < len; i++)
    fibo.push(getfib(i));
  return fibo;
}

function getfib(n){
  const res = []
  res[0] = 0
  res[1] = 1
  for (let i = 0; i <= len; i++) {
    res[i] = getfib(i - 1) + getfib(i - 2)
  }
  return res
}

非递归

function getFibonacci(n) {
  var fibarr = [];
  var i = 0;
  while(i < n) {
    if(i <= 1) {
      fibarr.push(i);
    } else {
      fibarr.push(fibarr[i - 1] + fibarr[i - 2])
    }
    i++;
  }
  return fibarr;
}

二分查找

查找某个值是否在有序数组中，有则返回索引，数组必须是有序的

注意：
还有一种不传起始和终止下标参数，通过在函数体内使用slice取到新的arr，整体没有这种方法好。

递归

/**
 * 递归实现二分查找，前提必须是有序数组，返回索引位置
 * @param {*} arr 目标数组
 * @param {*} value 查询的值
 * @param {*} start 从arr数查询的起始位置
 * @param {*} end 从arr中查询的结束位置
 * @returns i
 */
function binaryQuery (arr, value, start, end) {
  start = start || 0
  end = end || arr.length - 1
  const center = parseInt((start + end) / 2)

  if (arr[center] === value) {
    // 找到直接跳出
    return center
  } else if (arr[center] < value) {
    // 在右区间递归
    return binaryQuery(arr, value, center + 1, end)
  } else if (arr[center] > value) {
    // 在左区间递归
    return binaryQuery(arr, value, start, center - 1)
  }
}
binaryQuery([1, 2, 3, 4, 5, 6], 5)

非递归

/**
 * while二分查找，前提必须是有序数组，返回索引位置
 * @param {*} arr 目标数组
 * @param {*} value 查询的值
 * @returns i
 */
function binaryQuery (arr, key) {
  var start = 0,
    end = arr.length - 1;
  while (start <= end) {
    var mid = parseInt((start + end) / 2)
    if (key === arr[mid]) {
      return mid;
    } else if (key > arr[mid]) {
      start = mid + 1;
    } else if (key < arr[mid]) {
      end = mid - 1;
    }
  }
  return -1;
}
binaryQuery([1, 2, 3, 4, 5, 6], 5)

找出数组当中的质数

质数：也称素数，>1, 有无限个。除1和它自身之外不能被其他数整除，如2、3、5、7等，否则称为合数。

// 思想：m % n === 0, 等于0表示能整除，即不是质数

// 循环生成一个100内的数组
var i, arr = [];
for (i = 1; i < 100; i++) {
  arr.push(i);
}

var getPrimes = arr.filter((el) => {
  var flag = true; // 定义一个boolean值，filter返回布尔值

  if (el < 2) { // 小于2的直接排除
    flag = false;
  } else {
    // 使用小于当前元素的数值去整除当前当前元素，有一个可以整除则跳出循环
    for (var j = 2; j < el; j++) {
      if (el % j === 0) {
        flag = false;
        break;
      }
    }
  }

  return flag;
});
console.log(getPrimes)

js求1! + 2! + 3! + 4! + 5!(阶乘)

思路：s
转换成 1! + (2 * 1!) + (3 * 2!) + (4 * 3!) + (5 * 4!)

var sum = 0, // 总和
  sum2 = 1;

for (var i = 1; i <= 5; i++) {
  sum2 *= i; // 当前第一数
  sum += sum2;
}

console.log(sum)

两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
示例

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解答

// 常规错误想法
// 原因：未考虑相同位相加，如[3, 2, 4]，会返回[0, 0]，因为相同位的3 + 3已经满足了条件
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    for (var i = 0; i < nums.length; i++) {
        for (var j = 0; j < nums.length; j++) {
            if (nums[i] + nums[j] === target) {
                return [i, j];
            }
        }
    }
};



// 正确解法: 双重循环式避开i和j相等的情况
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    for (var i = 0; i < nums.length; i++) {
        for (var j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] === target) {
                return [i, j];
            }
        }
    }
};

无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例
示例 1:

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

解答

// 暴力法：耗时过长
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    var maxLen = 0;
    for (var i = 0; i < s.length; i++) {
        for (var j = i + 1; j <= s.length; j++) {
            // 通过确定i、j来获取所有的连续的子串，再通过方法查找该子串中是否存在重复的字符
            if (allUnique(s, i, j)) maxLen = Math.max(maxLen, j - i);
        }
    }
    return maxLen;
};
    
/**
 * 检查一个子字符串是否含有重复的字符
 * @param {string} str
 * @param {number} start
 * @param {number} end
 * @return {boolean}
 */
var allUnique = function(str, start, end) {
    var tempStr = '';
    for (var i = start; i < end; i++) {
        // 查看临时字符串中是否已经包含了当前字符
        if (tempStr.includes(str.charAt(i))) return false;
        tempStr += str.charAt(i); // 不包含则存储
    }
    return true;
}

整数反转

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
示例
示例 1:

输入: 123
输出: 321

示例 2:

输入: -123
输出: -321

示例 3:

输入: 120
输出: 21

假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−2^31, 2^31 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。

解答

/**
 * @param {number} x
 * @return {number}
 */
var reverse = function(x) {
    let sum = 0, // 翻转后的
        num = Math.abs(x); // 取绝对值
    
    // 核心
    while(num) {
        sum = sum * 10 + num % 10;
        num = parseInt(num / 10);
    }

    // 核心代码壳可改成：借助数组reverse方法直接翻转
    // sum = parseInt(String(num).split('').reverse().join(''));
    
    sum = x > 0 ? sum : -sum; // 补上原先的正负符号
    
    // 判断溢出情况
    if (sum > Math.pow(2, 31) || sum < -Math.pow(2, 31)) {
        return 0;
    }
    
    return sum;
};

走楼梯

10个台阶，每次只能上1个、2个或3个，一共有多少种走法？

拆分：
如果上10个台阶，可以分解以下情况：

1. 上9个台阶，最后上1个台阶，假设这种前面9个的走法是 m 种。
2. 上8个台阶，最后上2个台阶，假设这种前面8个的走法是 n 种。
3. 上7个台阶，最后上3个台阶，假设这种前面7个的走法是 l 种。
   所以上10个台阶的方法其实就是 m + n + l 种

同理：
1 中的上9个台阶也可以分为：

1. 上8个台阶，最后上1个台阶，假设这种前面8个的走法是 m 种。
2. 上7个台阶，最后上2个台阶，假设这种前面7个的走法是 n 种。
3. 上6个台阶，最后上3个台阶，假设这种前面6个的走法是 l 种。
   所以上9个台阶的方法其实就是 x + y + z 种

可以递归为：
f(n) = f(n - 1) + f(n - 2) + f(n - 3)

// 从后往前递归

// 每次可走1、2步
function step(n) {
  if (n === 1) return 1 // 1
  else if (n === 2) return 2 // 1+1、2
  else return step(n - 1) + step(n - 2)
}
// 89


// 每次可走1、2、3步
function step(n) {
  if (n === 1) return 1 // 1
  else if (n === 2) return 2 // 1+1、2
  else if (n === 3) return 4 // 1+1+1+1、1+1+2、2+2、1+3
  else return step(n - 1) + step(n - 2) + step(n - 3)
}
// 274

今日头条算法推导题

假设在今日头条里面，有很多工作人员检查新闻是不是属于虚假新闻，所有新闻真实率到达了98%，工作人员在检验一个真实的新闻把它检验为一个虚假的新闻的概率为2%，而一个虚假的新闻被检验为真实的新闻的概率为5%. 那么，一个被检验为真实的新闻确实是真实的新闻的概率是多大?

A.0.9991

B.0.9989

C.0.9855

D.0.96

答案:B

分析条件得到：
真的新闻：98%
假的新闻：2%
真的->假的：2%
假的->真的：5%

分析要求：被检验为真实的新闻确实是真实的新闻

首先要明确被检验为真实的新闻包括了（本来是真的和本来是假的）所以分子为（真->真），分母为（真->真 + 假->真）

结果为：（真->真）/（真->真 + 假->真） = (98%(1-2%)) / (98%(1-2%) + 2%*5%) = 0.9604/0.9614 = 0.9989……

求排列组合

[a] 得到 [a]
[a, b] 得到 [a, b, ab]
[a, b, c] 得到 [a, b, ab, c, ac, bc, abc]
[a, b, c, d] 得到 [a, b, ab, c, ac, bc, abc, d, ad, bd, abd, cd, acd, bcd, abcd]

分析：

1. [a]的结果为[a]，数量为1
2. 从[a]到[a, b]，结果其实是[a]的结果加上b元素，然后再将[a]结果中的每一个元素和b进行组合，得到[a, b, ab]，总数为 1+1+1=3
3. 从[a, b]到[a, b, c]，结果其实是[a, b]的结果加上c元素，然后将[a, b]结果中的每一个元素和c进行组合，得到[a, b, ab, c, ac, bc, abc]，总数为3+1+3 = 7

所以，n个元素的排列组合为：fn = f(n-1) + 1 + f(n-1)

要实现多个元素的排列组合，可以从1个元素开始算，随着遍历往后移动，将前一个的结算结果与新元素拼接，然后进行组合，完成之后再覆盖临时变量

实现：

function fn (arr) {
  let res = [] // 存放最终的结果
  let temp = [] // 临时存放
  for (let i = 0; i < arr.length; i++) {
    temp.push(arr[i]) // 暂存单个元素
    for (let j = 0; j < res.length; j++) {
      temp.push(res[j] + arr[i]) // 将上一轮得到的结果与新增元素进行一轮组合
    }
    res = [...temp] // 将这一轮的结果全部存入res中
    // 或：
    // res.push(temp)
    // temp = []
  }
  return res
}

// ['a']: ['a']
// ['a', 'b']: ["a", "b", "ab"]
// ['a', 'b', 'c']: ["a", "b", "ab", "c", "ac", "bc", "abc"]

如果变换一下需求，如果想：
[a] 得到 [a]
[a, b] 得到 [a, ab]
[a, b, c] 得到 [a, ab, abc]
[a, b, c, d] 得到 [a, ab, abc, abcd]

最简单结合slice方法如下：

function fn (arr) {
  let res = []
  for (let i = 0; i < arr.length; i++) {
    res.push(arr.slice(0, i + 1).join(''))
  }
  return res
}

如果不可以使用slice方法：

function fn (arr) {
  let res = [] // 存放最终的结果
  for (let i = 0; i < arr.length; i++) {
    if (!res.length) {
      res.push(arr[i])
    } else {
      res.push(res[res.length - 1] + arr[i])
    }
  }
  return res
}

用两个栈实现一个队列

// 用两个栈（后进先出 push、pop）实现队列（先进先出 push shift）

var stack1 = [] // 存放元素，实际以stack1为准
var stack2 = []

// 尾部添加
function addFn (val) {
  stack1.push(val)
}
// 头部删除
function deleteFn () {
  // 把stack1中的元素倒序放入stack2中
  while (stack1.length) {
    const stackTop = stack1.pop()
    if (stackTop) stack2.push(stackTop)
  }

  // 此时stack2有元素，stack1无元素，获取栈顶元素
  const res = stack2.pop()

  // 再把stack2中的元素再次倒序放回到stack1中（复原stack1，此时栈顶元素已被移除）
  while (stack2.length) {
    const stackTop = stack2.pop()
    if (stackTop) stack1.push(stackTop)
  }

  // 注意删除元素时会返回该元素
  return res || null
}

实现不规范版本号的排序

// ['1.1.1', '1.1.1.1.1', '65.1.1', '6.5.1', '7']
// 从大到小排列
function sort (arr) {
  return arr.sort((a, b) => {
    const aArr = a.split('.')
    const bArr = b.split('.')
    let i = 0
    while (true) {
      const s1 = aArr[i]
      const s2 = bArr[i]
      i++
      if (!s1 || !s2) return bArr.length - aArr.length
      if (s1 === s2) continue
      return s2 - s1
    }
  })
}

sort(['1.1.1', '1.1.1.1.1', '65.1.1', '6.5.1', '7'])
// ["65.1.1", "7", "6.5.1", "1.1.1.1.1", "1.1.1"]

输入一组数，输出最大组合数

// 例如：[31, 3, 34]，输出 34331
// 例如：[12, 7, 50]，输出 75012

unction getBigNumber (arr) {
  return Number(arr.sort((a, b) => {
    // 方法1: 直接比较法
    // return Number(`${b}${a}`) - Number(`${a}${b}`) // 从大到小为b-a，从小到大为a-b

    // 方法2: 按位比较法，获取最优的顺序
    a = String(a)
    b = String(b)
    let aLen = a.length
    let bLen = b.length
    let aIndex = 0
    let bIndex = 0

    while (1) {
      // 从前往后比较数字
      if (a[aIndex] === b[bIndex]) {
        aIndex++
        bIndex++
        if (aIndex === aLen && bIndex < bLen) {
          // a遍历结束，b未结束，即 aLen < bLen，如 5 和 53，取a的第一元素和b的超出位第1个元素比较（5 和 3 比较）
          return b[bIndex] - a[0]
        }
        if (bIndex === bLen && aIndex < aLen) {
          // b遍历结束，a未结束，即 aLen > bLen，如 53 和 5，取a的超出位第1个元素和b的第1个元素比较（3 和 5 比较）
          return b[0] - a[aIndex]
        }
        if (aIndex === aLen && bIndex === bLen) {
          // a、b都遍历结束
          return b[bIndex] - a[aIndex]
        }
      } else {
        // 不等则进行排序，从大到小
        return b[bIndex] - a[aIndex]
      }
    }
  }).join(''))
}

getBigNumber([31, 3, 34]) // 34331
getBigNumber([12, 7, 50]) // 75012

二叉树排列（从上到下，从左到右）

二叉树的蛇形排列（从上到下，奇数行从左到右，偶数行从右到左）

// 基数行按照从左到右，偶数行按照从右到左
function zigzagLevelOrder (root) {
  const res = []
  helpr(root, 0, res)
  // return res
  // 此时res是一个二维数组

  // 如果想返回一维数组，需要增加一个数组扁平化的操作
  return res.toString().split(',')
  // return flatten(res)

}
function helper(node, level, res) {
  if (!node) return
  if (!res[level]) {
    // res[level] = []
    res.push([])
  }
  if (level % 2 === 0) {
    // 偶数行（从左到右，push）
    res[level].push(node.val)
  } else {
    // 奇数行（从右到左，unshift）
    res[level].unshift(node.val)
  }

  helper(node.left, level + 1, res)
  helper(node.right, level + 1, res)
}


// 多维数组数组扁平化
function flatten (arr) {
  return arr.toString().split(',')
}
function flatten1 (arr) {
  return arr.reduce((prev, cur, index, self) => {
    return prev.concat(Array.isArray(cur) ? flatten(cur) : cur)
  })
}
function flatten2 (arr) {
  const result = []
  arr.forEach((item) => {
    if (Array.isArray(item)) {
      result = result.concat(flatten2(item))
    } else {
      result = result.concat(item)
    }
  })
  return result
}
function flatten3 (arr) {
  while (arr.some(item => Array.isArray(item))) {
    arr = [].concat(...arr)
  }
  return arr
}
function flatten3 (arr) {
  return arr.flat() // 默认只能拉平一层，参数传2，就拉平2层，传3就拉平3层
}

二维有序数组的查找

// [
//   [1,2,8,9],
//   [2,4,9,12],
//   [4,7,10,13],
//   [6,8,11,15]
// ]
// 给定 target = 7，返回 true。
// 给定 target = 3，返回 false。

for循环 + includes、indexOf

function find(target, array) {
  for (let i = 0; i < array.length; i++) {
    if (array[i].includes(target)) {
      return true
    }
  }
}

some + includes、indexOf

function find(target, array) {
  return array.some(arr => arr.includes(target))
}

线性查找

// 从右上角开始查找：比目标数大向左走，比目标数小向下走
function find(target, array) {
  let x = array.length
  let y = array[0].length
  let i = 0
  let j = y - 1
  while (i < x && j >= 0) {
    if (array[i][j] === target) return true
    else if (array[i][j] > target) i -= 1
    else if (array[i][j] < target) j += 1
  }
  return false
}

// 从左下角开始查找：比目标数大向上走，比目标数小向右走
function find(target, array) {
  let x = array.length
  let y = array[0].length
  let i = x - 1
  let j = 0
  while (i >= 0 && j < y) {
    if (array[i][j] === target) return true
    else if (array[i][j] > target) i -= 1
    else if (array[i][j] < target) j += 1
  }
  return false
}

防疲劳设置

弹窗每 10s 内只能出现 3次，假定弹窗本身只能看，不能操作

function showAlert (count) {
	console.log('alert visible:', count)
}
function fn (time, n) {
	var count = 0
	return function () {
		if (count >= n) return
		showAlert(count)
		count++
		setTimeout(() => {
			count--
		}, time * 1000)
	}
}
var f = fn(10, 3)


// 执行结果（sleep不需要实现）
console.log('sleep_0')
f()	// 打印
setTimeout(() => {
  console.log('sleep_' + 3*10e2)
	f()	// 打印
}, 3*10e2)
setTimeout(() => {
  console.log('sleep_' + 6*10e2)
	f()	// 打印
}, 6*10e2)
setTimeout(() => {
  console.log('sleep_' + 11*10e2)
	f() // 打印
}, 11*10e2)
setTimeout(() => {
  console.log('sleep_' + 13*10e2)
	f() // 不打印
}, 13*10e2)
setTimeout(() => {
  console.log('sleep_' + 14*10e2)
	f() // 打印
}, 14*10e2)
setTimeout(() => {
  console.log('sleep_' + 15*10e2)
	f() // 不打印
}, 15*10e2)
setTimeout(() => {
  console.log('sleep_' + 18*10e2)
	f() // 打印
}, 18*10e2)
setTimeout(() => {
  console.log('sleep_' + 20*10e2)
	f() // 不打印
}, 20*10e2)

链式调用实现执行、等待执行、先执行操作

/**
 * waitFirst 优先级大于 wait，先执行waitFirst，再执行前面的，再执行后面的
 * 
 * fn('msg')
 * 		console.log('hello msg')
 * 
 * fn('msg').wait(5).do('str')
 * 		console.log('hello msg')
 * 		... wait 5s
 * 		console.log('hello str')
 * 
 * fn('msg').wait(5).do('str').do('name')
 * 		console.log('hello msg')
 * 		... wait 5s
 * 		console.log('hello str')
 * 		console.log('hello name')
 * 		
 * fn('msg').waitFirst(5).do('str').do('name')
 * 		... wait 5s
 * 		console.log('hello msg')
 * 		console.log('hello str')
 * 		console.log('hello name')
 */

链式调用的原理：一个对象里面的多个方法，每个方法内部return this，这样后面的方法在调用的时候就可以继续在this环境下执行。

const obj = {
  eat () {
    console.log('eat')
    return this
  },
  drink () {
    console.log('drink')
    return this
  }
}

obj.eat().drink() // eat、drink
obj.drink().eat() // drink、eat

本题实现

function Fn (msg) {
  this.msg = msg
  this.queue = [] // 使用任务队列（先进先出的思想模拟执行顺序）

  const fn = () => {
    console.log(`hello ${msg}`)
    this.next() // 执行完之后取出队列下一个函数执行
  }
  this.queue.push(fn)
  
  setTimeout(() => {
    console.log(this)
    this.next()
  }, 0) // 异步，先等prototype执行完，将所以事件进行收集再执行

  return this
}

Fn.prototype = {
  wait (time) {
    const fn = () => {
      setTimeout(() => {
        this.next()
      }, time * 1000)
    }
    this.queue.push(fn) // 普通级别的放在队尾
    return this
  },
  waitFirst (time) {
    const fn = () => {
      setTimeout(() => {
        this.next()
      }, time * 1000)
    }
    this.queue.unshift(fn) // 优先级高的放入队首
    return this
  },
  do (name) {
    const fn = () => {
      console.log(`hello ${name}`)
      this.next()
    }
    this.queue.push(fn) // 普通级别的放在队尾
    return this
  },
  // 从任务队列中取出函数执行
  next () {
    const fn = this.queue.shift() // 从头部取出函数 
    fn && fn()
  }
}

// new Fn('msg')
// new Fn('msg').wait(2).do('aaa')
// new Fn('msg').wait(2).do('aaa').do('bbb')
// new Fn('msg').waitFirst(2).do('aaa').do('bbb')
new Fn('msg').waitFirst(2).wait(2).do('bbb')