面试高频手撕代码题

手写一个 flatten 函数（数组降维）

• 方法 1：Array.prototype.flat()

var arr1 = [1, 2, [3, 4]];
arr1.flat();
// [1, 2, 3, 4]

var arr2 = [1, 2, [3, 4, [5, 6]]];
arr2.flat();
// [1, 2, 3, 4, [5, 6]]

var arr3 = [1, 2, [3, 4, [5, 6]]];
arr3.flat(2);
// [1, 2, 3, 4, 5, 6]

//使用 Infinity，可展开任意深度的嵌套数组
var arr4 = [1, 2, [3, 4, [5, 6, [7, 8, [9, 10]]]]];
arr4.flat(Infinity);
// [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

• 方法 2：使用栈

// 无递归数组扁平化，使用堆栈
// 注意：深度的控制比较低效，因为需要检查每一个值的深度
// 也可能在 shift / unshift 上进行 w/o 反转，但是末端的数组 OPs 更快
function flatten(arr) {
  const stack = [...arr];
  const res = [];
  while (stack.length) {
    // 使用 pop 从 stack 中取出并移除值
    const next = stack.pop();
    if (Array.isArray(next)) {
      // 使用 push 送回内层数组中的元素，不会改动原始输入
      stack.push(...next);
    } else {
      res.unshift(next);
    }
  }
  return res;
}

//test
var arr1 = [1, 2, 3, [1, 2, 3, 4, [2, 3, 4]], [2, 3], 4, 5];
flatten(arr1); // [1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 2, 3, 4, 5]

• 方法 3: toString

function flatten(arr) {
  const res = arr.toString().split(',');
  // 这里要注意arr存在空数组的情况要踢掉
  return (result = res.filter(item => item !== '').map(Number));
}
console.log(flatten([1, 9, [2, 3], [], [0, 999, [66, [100, 200]]]]));

• 方法 4：reduce + concat + isArray + recursivity

// 使用 reduce、concat 和递归展开无限多层嵌套的数组
function flatDeep(arr, d = 1) {
  return d > 0
    ? arr.reduce(
        (acc, val) =>
          acc.concat(Array.isArray(val) ? flatDeep(val, d - 1) : val), [])
    : arr.slice()
}

// test
var arr1 = [1, 2, 3, [1, 2, 3, 4, [2, 3, 4]]]
flatDeep(arr1, Infinity)
// [1, 2, 3, 1, 2, 3, 4, 2, 3, 4]

• 方法 5：forEach+isArray+push+recursivity

// forEach 遍历数组会自动跳过空元素
const eachFlat = (arr = [], depth = 1) => {
  const result = []; // 缓存递归结果
  // 开始递归
  (function flat(arr, depth) {
    // forEach 会自动去除数组空位
    arr.forEach((item) => {
      // 控制递归深度
      if (Array.isArray(item) && depth > 0) {
        // 递归数组
        flat(item, depth - 1)
      } else {
        // 缓存元素
        result.push(item)
      }
    })
  })(arr, depth)
  // 返回递归结果
  return result
}

// for of 循环不能去除数组空位，需要手动去除
const forFlat = (arr = [], depth = 1) => {
  const result = [];
  (function flat(arr, depth) {
    for (let item of arr) {
      if (Array.isArray(item) && depth > 0) {
        flat(item, depth - 1)
      } else {
        // 去除空元素，添加非undefined元素
        item !== void 0 && result.push(item)
      }
    }
  })(arr, depth)
  return result
}