用LeetCode寫日記-Day26

今天又恢復正常了，所以這幾天9點看不到到題目到底發生什麼事情….

Day26: Flatten Deeply Nested Array

問題描述：

Given a multi-dimensional array arr and a depth n, return a flattened version of that array.

A multi-dimensional array is a recursive data structure that contains integers or other multi-dimensional arrays.

A flattened array is a version of that array with some or all of the sub-arrays removed and replaced with the actual elements in that sub-array. This flattening operation should only be done if the current depth of nesting is less than n. The depth of the elements in the first array are considered to be 0.

Please solve it without the built-in Array.flat method.

問題難度：Medium

問題限制：

0 <= count of numbers in arr <= 105
0 <= count of subarrays in arr <= 105
maxDepth <= 1000
1000 <= each number <= 1000
0 <= n <= 1000

我的解題過程：

題目要求將一組多維陣列**flattened**，根據n的值來決定。

所謂的**flattened** 用文字我不太會解釋，用案例：

1
2
3

arr = [1, 2, [3, 4, 5], 6]
// **flattened 後
arr = [1, 2, 3, 4, 5, 6]**

因此第一時間想到的就是使用…來把裡面的內容擴展出來。

也就是說我需要遍歷傳進來的這個陣列，依照n的值來決定遞迴的次數，而要執行的code則是類似…arr[i] 然後再把這個值存到array裡面。

const newArr = []
    if (n === 0) return arr
    for (let i = 0; i < n; i++) {
        arr.map((value) => {
            if (Array.isArray(value)) {
                value.map((item) => newArr.push(item))
            } else {
                newArr.push(value)
            }
        })
    }

首先，我最後使用map()來實作這題，我先建立了一個newArr 的變數，用來存放展開後的陣列。

另外當n等於0時，依照題目需求直接回傳原陣列。

因為n是已知的值，所以這邊直接使用for迴圈。

for迴圈裡面的內容則是會先判斷map目前的元素是不是為陣列，然後在依照不同的回傳值有不同的作法。

但提交後，才發現錯誤。

我的第三個測試回傳了2次newArr，因此更改成這樣：

let newArr = []
    if (n === 0) return arr
    for (let i = 0; i < n; i++) {
        newArr = []
        arr.map((value) => {
            if (Array.isArray(value)) {
                value.map((item) => newArr.push(item))
            } else {
                newArr.push(value)
            }
        })
      arr = newArr
    }
    return newArr

測試都通過了，但跟之前的狀況一樣，時間太久LeetCode不承認

我的code:

var flat = function (arr, n) {
    let newArr = []
    if (n === 0) return arr
    for (let i = 0; i < n; i++) {
        newArr = []
        arr.map((value) => {
            if (Array.isArray(value)) {
                value.map((item) => newArr.push(item))
            } else {
                newArr.push(value)
            }
        })
        arr = newArr
    }
    return newArr
};

其他解法：

var flat = function(arr, depth) {
  const stack = [...arr.map(item => [item, depth])];
  const result = [];

  while (stack.length > 0) {
    const [item, depth] = stack.pop();

    if (Array.isArray(item) && depth > 0) {
      stack.push(...item.map(subItem => [subItem, depth - 1]));
    } else {
      result.push(item);
    }
  }

  return result.reverse();
};

結論：

雖然還是超時，但有感覺到自己的進步，以前看到這總難度的題目都會想直接看解答，現在都會自己先嘗試一下。
雖然不能提交但至少我用我理解的寫法完成了測試，就是時間上花了比較久，又超過停損點了，但還好今天只有一次！