Table of contents
LeetCode 挑戰題目總覽：30 Days of LC JavaScript Challenge（從 5 月 5 日起，台灣時間每天早上八點釋出新題目）
第 22 天：Flatten Deeply Nested Array
題目說明
給定一個多維陣列 arr 和深度 n，回傳該陣列的扁平化版本。多維陣列是一個遞迴資料結構，裡面包含整數或其他多維陣列。扁平化陣列是該陣列的版本，其中某些或全部的子陣列被移除，並用該子陣列中的實際元素取代，只有當目前的嵌套深度小於 n 時，才能執行扁平化操作，第一個陣列中元素的深度被認為是 0，在不使用內建的 Array.flat 方法的情況下解決這個問題。
解題方法
先拆解成基本情況
當
n為 0 時，直接返回。會遇到的值有可能是整數或是陣列，只有值為陣列時才需要決定是否要處理。
當值為陣列時用遞迴扁平化。
解題程式碼
本來用 Array.concat() 來組陣列，但發現 Test Case 4 會 Timeout，問 ChatGPT 才知道由於 Array.concat() 會不停建立新的 Array，會增加時間複雜度。
type MultiDimensionalArray = (number | MultiDimensionalArray)[];
const flat = function (
arr: MultiDimensionalArray,
n: number
): MultiDimensionalArray {
if (n === 0) return arr;
return arr.reduce<MultiDimensionalArray>(
(acc, cur) => acc.concat(Array.isArray(cur) ? flat(cur, n - 1) : cur),
[]
);
};
type MultiDimensionalArray = (number | MultiDimensionalArray)[];
const flat = function (
arr: MultiDimensionalArray,
n: number
): MultiDimensionalArray {
if (n === 0) return arr;
return arr.reduce<MultiDimensionalArray>((acc, cur) => {
Array.isArray(cur) ? acc.push(...flat(cur, n - 1)) : acc.push(cur);
return acc;
}, []);
};
官方解題說明
https://leetcode.com/problems/flatten-deeply-nested-array/editorial/
使用情境
數據處理（Data Processing）：當使用嵌套格式的資料（例如 JSON 或 XML ）時，平坦化結構可以簡化資料處理任務。例如，如果從 API 獲得了嵌套的 JSON 回應，並且只需要某些字段，則平坦化 JSON 可以使提取和分析所需資料變得更容易。
const people = [ { name: "Mike", items: ["hammer", "axe"] }, { name: "Steve", items: ["rock", "stick"] }, ]; const allItems = people.map((d) => d.items).flat();樹狀遍歷（Tree Traversal）：在計算機科學中，樹常用於表示層次結構。遍歷樹狀結構時，可以使用平坦化將樹轉換為線性表示，以便更容易導航和操作資料。
遞歸演算法（Recursive Algorithms）：許多演算法涉及資料結構的遞歸操作。對嵌套陣列進行平坦化可以在此情況下有益，例如，在實現深度優先搜索或遞歸回溯算法時，平坦化可以通過提供資料的線性視圖來簡化過程。
資料庫查詢（Database Queries）：在資料庫系統中，可以將嵌套結構儲存為陣列或 JSON 對象。執行查詢時，平坦化嵌套陣列可以用於檢索特定元素或跨不同結構級別進行聚合。
官方解法 1：遞迴方法
時間複雜度在最壞的情況下，每個 arr 中的元素都是一個陣列，且達到最大深度 n，遞迴函式將為每個巢狀陣列在每個層級上進行呼叫，總共 O(k*n) 次遞迴呼叫，其中 k 表示每個層級上的平均巢狀陣列數量，n 是最大深度層級。
空間複雜度取決於深度層級 n，每次遞迴呼叫會在呼叫堆疊上消耗額外的空間，因此為 O(n)。
type MultiDimensionalArray = (number | MultiDimensionalArray)[];
const flat = function (arr: MultiDimensionalArray, n: number): MultiDimensionalArray {
let res: MultiDimensionalArray = [];
// 建立遞迴函式 flattening 接受兩個參數：一個陣列 nums 和一個表示當前深度層級的 l
const flattening = (nums: MultiDimensionalArray, l: number) => {
// 使用 for...of 迴圈遍歷 nums 陣列中的元素
for (const num of nums) {
// 檢查它是否為陣列，並且當前層級 l 是否在指定範圍內
if (Array.isArray(num) && l > 0 && l <= n) {
// 以遞迴的方式調用 flattening 函式，並將巢狀陣列作為參數，同時將層級減 1
flattening(num as MultiDimensionalArray, l - 1);
} else {
// 如果元素不是陣列或層級條件未滿足，則將該元素推入結果陣列 res
res.push(num);
}
}
};
flattening(arr, n);
return res;
};
官方解法 2：使用迭代佇列（Iterative Queue）
type MultiDimensionalArray = (number | MultiDimensionalArray)[];
const flat = function (arr: MultiDimensionalArray, n: number): MultiDimensionalArray {
// 是否還有待攤平的巢狀陣列
let nestedArrayElement = true;
// 儲存在攤平過程中的元素
let queue: MultiDimensionalArray;
// 目前的深度層級
let depth = 0;
// 只要還有單一陣列元素要處理（nestedArrayElement 為 true）且當前深度小於 n，就會繼續執行
while (nestedArrayElement && depth < n) {
// 每次迴圈的開始，先將 nestedArrayElement 重設為 false，表示尚未遇到內嵌陣列
nestedArrayElement = false;
// 儲存目前迴圈的元素
queue = [];
// 遍歷 arr 的每個元素
for (let i = 0; i < arr.length; i++) {
// 如果元素是陣列
if (Array.isArray(arr[i])) {
// 將其元素展開並放入佇列
queue.push(...arr[i] as MultiDimensionalArray);
// 將 nestedArrayElement 設置為 true，表示遇到了巢狀陣列
nestedArrayElement = true;
} else {
// 元素不是陣列，則直接將其推入佇列
queue.push(arr[i]);
}
}
// 在處理完 arr 的所有元素後，將 arr 更新為佇列中的元素
arr = [...queue];
depth++;
}
return arr;
};
官方解法 3：使用迭代堆疊（Iterative Stack）
type MultiDimensionalArray = (number | MultiDimensionalArray)[];
const flat = function (arr: MultiDimensionalArray, n: number): MultiDimensionalArray {
// 初始化一個堆疊 stack，將 arr 的元素與對應的深度層級一起放入堆疊
// 每個項目表示為一對 [item, depth]
const stack: [MultiDimensionalArray, number][] = arr.map((item) => [item, n] as [MultiDimensionalArray, number]);
// 初始化一個空陣列 res，用於儲存攤平後的結果
const res: MultiDimensionalArray = [];
// 只要堆疊中還有元素就進入 while 迴圈
while (stack.length > 0) {
// 使用 pop() 方法從堆疊中彈出頂部項目 [item, depth]
const [item, depth] = stack.pop()!;
// 如果 item 是一個陣列且當前深度 depth 大於 0 代表該元素是一個包含需要進一步攤平的項目的容器
if (Array.isArray(item) && depth > 0) {
// 將陣列 item 的每個元素映射為一對 [el, depth - 1]
// 表示元素以及降低的深度層級（depth - 1）
stack.push(...item.map((el) => [el, depth - 1] as [MultiDimensionalArray, number]));
} else {
// 如果 item 不是陣列或深度為 0，可以直接添加到 res 陣列中
res.push(item);
}
}
// 將包含攤平元素的 res 陣列返回，為了保持原始順序，使用 reverse() 進行反轉
return res.reverse();
};
第 23 天：Array Prototype Last（待補寫）
題目說明
解題方法
解題程式碼
官方解題說明
https://leetcode.com/problems/array-prototype-last/editorial/
第 24 天：Group By（待補寫）
題目說明
解題方法
解題程式碼
官方解題說明
https://leetcode.com/problems/group-by/editorial/
第 25 天：Check if Object Instance of Class（待補寫）
題目說明
解題方法
解題程式碼
官方解題說明
https://leetcode.com/problems/check-if-object-instance-of-class/editorial/
第 26 天：Call Function with Custom Context（待補寫）
題目說明
解題方法
解題程式碼
官方解題說明
https://leetcode.com/problems/call-function-with-custom-context/editorial/
第 27 天：Event Emitter（待補寫）
題目說明
解題方法
解題程式碼
官方解題說明
https://leetcode.com/problems/event-emitter/editorial/
第 28 天：Array Wrapper（待補寫）
題目說明
解題方法
解題程式碼
官方解題說明
https://leetcode.com/problems/array-wrapper/editorial/
第 29 天：Generate Fibonacci Sequence（待補寫）
題目說明
解題方法
解題程式碼
官方解題說明
https://leetcode.com/problems/generate-fibonacci-sequence/editorial/?gio_link_id=xo040MEo
第 30 天：Nested Array Generator（待補寫）
題目說明
解題方法
解題程式碼
官方解題說明
https://leetcode.com/problems/nested-array-generator/editorial/