乐趣区

关于javascript:Facebook面试题-用递归和迭代手写Arrayprototypeflat

jiezi

题目起源: https://bigfrontend.dev/probl…

手写 Array.prototype.flat() 看似简略，然而 Facebook 面试一轮通常有两道题目，也就是说要在 15 分钟之内写出 bugfree 的代码，加上现场的缓和曾经还要求清晰的思路表白，还是有挑战的。

题目

咱们须要实现 flat() 来去掉括号，层数由第二个参数来指定

const arr = [1, [2], [3, [4]]];
flat(arr)
// [1, 2, 3, [4]]
flat(arr, 1)
// [1, 2, 3, [4]]
flat(arr, 2)
// [1, 2, 3, 4]

递归

用 recursion 比较简单了，便当数组做如下操作即可：

  1. 如果碰到了 array，就先用flat() 去掉它的括号，而后收集后果
  2. 如果碰到的不是 array，就收集后果

用以上想法就能够简略地失去以下代码。

function flat(arr, depth = 1) {const result = []
  for (let item of arr) {if (Array.isArray(item) && depth > 0) {result.push(...flat(item, depth - 1))
    } else {result.push(item)
    }
  }
  return result
}

用 reduce 重写

有一个 result，有一个 for loop，那就能够用 reduce 玩一点花色进去。不过这个并不没什么卵用，不是实质上的变动。

function flat(arr, depth = 1) {return arr.reduce((result, item) => {if (Array.isArray(item) && depth > 0) {result.push(...flat(item, depth - 1))
    } else {result.push(item)
    }
    return result
  }, [])
}

迭代

刷过面试题都晓得，遇到递归就要尝试一下用迭代来写，能够说必考了。

咱们先手写一下去掉括号的过程。右边是指标 array，左边是后果 array。

[1, [2], [3, [4]]]  => []

从左往右，碰到了 1，不是 array，间接放入后果

[[2], [3, [4]]] => [1]

下一个是 [2]，是 array，去掉括号，从新放回原来的数组。

[2, [3, [4]]] => [1]

下一个是 2，不是 array，放入后果

[[3, [4]]] => [1,2]

反复上述过程，咱们失去以下两头后果。

[3, [4]] => [1,2]
[[4]] => [1,2,3]
[4] => [1,2,3]
[] => [1,2,3,4]

接下来得思考 depth 的问题，咱们不能见到括号就去掉，所以 每个 element 须要有本人的 step，相当于给原数组的 element 减少了一个 depth 属性，咱们用 [element, depth]来示意。

假如 depth 是 1: 初始状态下所有元素都是 depth:1

[[1, 1], [[2], 1], [[3, [4]], 1]] => []

下一个 element 是 1，不是 array，所以放入后果

[[[2], 1], [[3, [4]], 1]] => [1]

下一个 element 是[2]，是 array，depth 是 1，那么它的所有元素的 depth 设为 0，而后从新放回

[[2, 0], [[3, [4]], 1]] => [1]

下一个 element 是 2, 不是 array，放入后果

[[[3, [4]], 1]] => [1, 2]

下一个是 [3,[4]], depth 是 1，把其中元素放回，depth 设为 0 

[[3,0],[[4],0]] => [1, 2]

下一个是 3，间接放入后果

[[[4],0]] => [1, 2, 3]

下一个是 [4]，depth 是 0，因为是 0，所以这个括号没法去掉，把 [4] 放入后果

[] => [1,2,3,[4]]

功败垂成。

把上述过程转换微代码，就比拟容易了。以下是迭代的解法。

function flat(arr, depth = 1) {const result = []
  const stack = [...arr.map(item => ([item, depth]))]
  
  while (stack.length > 0) {const [head, depth] = stack.shift()
    if (Array.isArray(head) && depth > 0) {stack.unshift(...head.map(item => ([item, depth - 1])))
    } else {result.push(head)
    }
  }
  return result
}

这里还有一个 performance 的问题。咱们用到了 shift/unshift，实际上是不太好的，因为shift/unshift 会触发所有元素的 index 发生变化。更好的方法是用 push/pop，这样咱们失去了一个逆序的后果，最初 reverse 一下就好。

function flat(arr, depth = 1) {const result = []
  const stack = [...arr.map(item => ([item, depth]))]
  
  while (stack.length > 0) {const [top, depth] = stack.pop()
    if (Array.isArray(top) && depth > 0) {stack.push(...top.map(item => ([item, depth - 1])))
    } else {result.push(top)
    }
  }
  
  return result.reverse()}

通过撒花! 如果你有趣味能够去 https://BFE.dev 理论挑战一下。

心愿能帮忙到你！接下来 JSer 还会带来更多前端面试代码题解析，欢送关注。

退出移动版