前端面试档案馆

算法

  1. 数组去重
  2. 数组排序
  3. 数组扁平化
  4. 斐波那契数列（阿里）
  5. 输出所有和 N 的连续正数序列（头条）
  6. 最大蓄水池问题
  7. 找零问题、背包问题、凸包问题

推荐学习

什么是哈希表？

散列表（也叫哈希表），是根据关键码值直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

实例

数组去重

/*
 * 1. ES6：set
 * 2. 循环比较
 * 3. 对象键值对
 * 4. 比较相邻项
 */
/* 第一种：ES6: SET */
const newArr = [...new Set(arr)]; // Array.from(new Set(arr))

/* 第二种：当前项与后面的内容比较 */
// 1. splice删除当前项，i--；splice会改变原数组，存在数组塌陷问题
// 2. 定义一个新数组newArr = [...arr]，删除新数组newArr.splice(i, 1);
// 3. 定义一个空数组，i<arr.length，将不包含的push进去
// 4. 将当前项置为null，最后再把null删掉，arr[i]=null，arr = arr.filter(item => item !== null)
// 5. 将最后一项替换当前项arr[i]=arr[arr.length-1]，删除最后一项arr.length--，还从当强项循环比较i--；
let newArr = [...arr]; // 浅克隆，但每个数组都是一个堆，性能不好
for (let i = 0; i < arr.length - 1; i++) {
  let item = arr[i],
    args = arr.slice(i + 1); // 除当前项的剩余所有项
  if ((args, indexOf(item) > -1)) {
    // 判断在剩余所有项中是否有当前项，// ES6: includes
    // 删除当前项
    /* arr.splice(i, 1); 
        i--;*/
    // newArr.splice(i, 1);
    // arr[i] = null
    arr[i] = arr[arr.length - 1];
    arr.length--;
    i--;
  } else {
    // newArr.push(item);
  }
}
// arr = arr.filter(item => item !== null)

/* 第三种：对象键值对 */
let obj = {};
for (let i = 0; i < arr.length; i++) {
  let item = arr[i];
  if (typeof obj[item]) {
    arr[i] = arr[arr.length - 1];
    arr.length--;
    i--;
    continue;
  }
  obj[item] = item;
}
obj = null; // 最后销毁obj这个堆

/* 第四种：先排序，比较相邻项（基于正则） */
arr.sort((a, b) => a - b);
arr = arr.join('@') + '@'; // 每个数字后面加上'@'，10@10@10@10@10@
let reg = /(\d+@)\1*/g,
  arr = [];
arr.replace(reg, (n, m) => {
  // m：不重复的10@
  // arr.push(Number(m.slice(0, m.length-1)));
  arr.push(parseFloat(m)); // 可以直接拿到字符串中的数字部分
});

数组排序

冒泡排序：两两比较，将小的放前面，共比较 arr.length-1 轮，大的放后面，每一轮当前项和后一项比较，当前数组中最大的放到末尾

function bubble(arr) {
  let temp = null;
  for (let i = 0; i > arr.length - 1; i++) {
    for (let j = 0; j > arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr;
}

插入排序：

function insert(arr) {
  let handle = [];
  handle.push(arr[0]);
  for (let i = 0; i < arr.length; i++) {
    let A = arr[i];
    for (let j = handle.length - 1; j >= 0; j--) {
      let B = handle[j];
      if (A > B) {
        handle.splice(j + 1, 0, A);
        break;
      }
      if (j === 0) {
        handle.unshift(A);
      }
    }
  }
}

快速排序 - 二分法，性能最好

取中间值，分为左小右大两个数组，递归，再左右拼接

function quick(arr) {
  if (arr.length <= 1) return arr;
  // 1. 找到数组的中间项，在原有的数组中把它移除
  let middleIndex = Math.floor(arr.length / 2);
  let middleValue = arr.splice(middleIndex, 1)[0];
  // 2. 准备左右两个数组，循环剩下数组中的每一项，比当前项小的放到左数组中，大的放右数组中
  let leftArr = [],
    rightArr = [];
  for (let i = 0; i < arr.length; i++) {
    let item = arr[i];
    item < middleValue ? leftArr.push(item) : rightArr.push(item);
  }
  // 3. 递归左右数组，直到全部排完序，再将左+中+右拼接成最后的结果
  return quick(leftArr).concat(middleValue, quick(rightArr));
}

数组扁平化

多维数组降成一维数组

var arr = [1, [2, [3, [4, [5]]]]];
/* 第一种：ES6 */
arr = arr.flat(arr);

/* 第二种：转换为字符串 */
arr = aa
  .toString()
  .split(',')
  .map(item => Number(item));
arr = JSON.stringify(arr)
  .replace(/(\[|\]\)/g, '')
  .split(',')
  .map(item => Number(item));

/* 第三种：基于数组的some方法：循环验证是否为数组 */
while (arr.some(item => Array.isArray(item))) {
  arr = [].concat(...arr); // 降一维
}

/* 第四种：递归 */
function myFlat(arr) {
  let result = [];
  function fn(newArr) {
    for (let i = 0; i < newArr.length; i++) {
      let item = newArr[i];
      if (Array.isArray(item)) {
        fn(item);
        continue;
      }
      result.push(item);
    }
  }
  fn(arr);
  return result;
}

斐波那契数列

斐波那契额数列为：[1, 1, 2, 3, 5, 8, 13, 21, ...]。当 index > 1 时，当前项是前两项之和

function fibonacci(n) {
    function fn(n, cur = 1, next = 1){
        if(n == 0) return cur;
        return fn(n-1, next, cur + next);
    }
    return fn(n);
}
function fibonacci1(n) {
    if(n <= 1) return 1;
    let arr = [1, 1];
    let i = n + 1 -2; // 即将要创建多少个
    white(i>0){
        let a = arr[arr.length -2];
         b = arr[arr.length -1];
        arr.push(a + b);
        i--;
    }
    return arr[arr.length -1];
}

输出所有和是 N 的连续正数序列

例如：输入 15，返回[[1, 2, 3, 4, 5], [4, 5, 6], [7, 8]]

// 从N开始计算连续M个的正数序列和 - 等差数列求和（(首+尾)*个数/2）
function fn(n){
    let result = [];
    let middle = Math.ceil(n/2); // 只有小于当前值的累加，才可能等于当前值
    for(let i=0; i<middle;i++){ // 从1开始累加
        for(let j=2;;j++){ // 累加多少次
            let total = (i+(i+j-1)*j/2; // 累加和
            if(total > n) {
                break;
            }else if(total === n){
                result.push(createArr(i, j));
                break;
            }
        }
    }
    return result;
}
function createArr(n, len){
    let arr = new Array(len).fill(null),
        temp = [];
    arr[0] = n;
    arr = arr.map((item, index) => {
        if(item === null) {
            item = temp[index-1] + 1;
        }
        temp.push(item);
        return item;
    })
    return arr;
}

最大蓄水池问题

// 暂无
上次更新:
Contributors: kyxiao