Zenn
🦔

BFE.dev解答記録 #3. Array.prototype.flat()を実装する

2020/10/12に公開
JavaScript
frontend
tech

https://bfe.dev/ja はFrontEnd版のLeetCode、GAFAの面接を受けるなら練習した方がいいかなと。
以下は自分の練習記録です。

bfe3.png

BFE.dev#3. Array.prototype.flat()を実装する をみてみよう

目標

ネストされている括弧を除去するための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

Recursionでやるのは簡単、loopしながら集めれば良い。

  1. 配列であれは、flat()を実行してから要素を集める
  2. 配列でなければ、そのまま要素を集める

これを持って、以下のアプローチは自然に出てくる。

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で書き直す

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
  }, [])
}

Iterative Approach

面接を受ける時は、recursionをiterationに書き直すのは常識。

まずステップバイステップで括弧を除去するプロセスを理解しよう。左はターゲットの配列で、右は結果。

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

1、配列ではない、結果にpushする。

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

[2]、配列だ、まず括弧を除去し、またターゲットの配列に戻す

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

2、結果にpushする。

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

上記のステップを繰り返したら、以下の結果になる。

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

問題は depthの処理、全ての括弧を除去するわけではないので、各要素は自分が何層の括弧に入っているのかをトラックしないといけない。

上記のプロセスをやり直そう、今回はdepthつきで。

depthは1とする：

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

1、depth 1、なので結果にpushする。

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

[2]、depth　1、括弧を除去し、2を入れ戻す、depthは0になる。

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

2 、depth 0、結果にpushする。

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

[3,[4]] 、 depth 1、各要素を入れ戻し、depthを0にする。

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

3、depth 0、結果にpushする。

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

[4]、 depth 0。depthは0なので、もう括弧があっても除去することができない。結果に[4]をpushする。

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

以上のプロセスを踏まえて、下記のiterative approachを書くのは難しくない。

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
}

上記の実装ではパフォーマンス問題があるーshift/unshiftは避けるべき、実行するたびに全ての要素のindexが変わるから。

改善するために、pop/pushを使えば良い。そのために、最後に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()
}

通った！

Alt Text

上記のコードはこちらで見れます。https://bigfrontend.dev/ja/problem/implement-Array-prototype.flat/discuss/25

もし興味あれば、 BFE.devでやってみましょう

Discussion