/**
* @param {any[]} arr
* @param {number} depth
* @return {any[]}
*/
var flat = function (arr, n) {
};
2625. 扁平化嵌套数组
请你编写一个函数，它接收一个 多维数组 arr 和它的深度 n ，并返回该数组的 扁平化 后的结果。
多维数组 是一种包含整数或其他 多维数组 的递归数据结构。
数组 扁平化 是对数组的一种操作，定义是将原数组部分或全部子数组删除，并替换为该子数组中的实际元素。只有当嵌套的数组深度大于 n 时，才应该执行扁平化操作。第一层数组中元素的深度被认为是 0。
请在没有使用内置方法 Array.flat 的前提下解决这个问题。
示例 1：
输入 arr = [1, 2, 3, [4, 5, 6], [7, 8, [9, 10, 11], 12], [13, 14, 15]] n = 0 输出 [1, 2, 3, [4, 5, 6], [7, 8, [9, 10, 11], 12], [13, 14, 15]] 解释 传递深度 n=0 的多维数组将始终得到原始数组。这是因为 子数组(0) 的最小可能的深度不小于 n=0 。因此，任何子数组都不应该被平面化。
示例 2：
输入 arr = [1, 2, 3, [4, 5, 6], [7, 8, [9, 10, 11], 12], [13, 14, 15]] n = 1 输出 [1, 2, 3, 4, 5, 6, 7, 8, [9, 10, 11], 12, 13, 14, 15] 解释 以 4 、7 和 13 开头的子数组都被扁平化了，这是因为它们的深度为 0 ， 而 0 小于 1 。然而 [9,10,11] 其深度为 1 ，所以未被扁平化。
示例 3：
输入 arr = [[1, 2, 3], [4, 5, 6], [7, 8, [9, 10, 11], 12], [13, 14, 15]] n = 2 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] 解释 所有子数组的最大深度都为 1 。因此，它们都被扁平化了。
提示：
0 <= arr 的元素个数 <= 1050 <= arr 的子数组个数 <= 105maxDepth <= 1000-1000 <= each number <= 10000 <= n <= 1000原站题解
javascript 解法, 执行用时: 180 ms, 内存消耗: 71.9 MB, 提交时间: 2023-09-20 17:12:38
/**
* @param {any[]} arr
* @param {number} depth
* @return {any[]}
*/
/** 递归写法 */
var flat = function (arr, n) {
// return arr.flat(n);
if(n <= 0) return arr;
const result = [];
for(const item of arr){
result.push(...(Array.isArray(item)?flat(item,n-1):[item]));
}
return result;
};
// dfs
var flat2 = function (arr, n) {
while (n > 0 && arr.some(Array.isArray)) {
arr = [].concat(...arr);
n--;
}
return arr;
};
// bfs
var flat3 = function (arr, n = 0) {
if (n <= 0) {
return arr;
}
const result = [];
const stack = []; // 栈变量，一层层存入
for (let i = 0; i < arr.length; i++) {
const current = arr[i];
if (Array.isArray(current)) {
stack.push(current);
while (stack.length) {
const last = stack[stack.length - 1]; // 获取当前最深的栈
let deeper = false;
while (last.length) {
const c = last.shift();
if (Array.isArray(c) && n > stack.length) {
stack.push(c); // 增加栈深度
deeper = true;
break;
} else {
result.push(c);
}
}
if (!deeper) { // 如果本层拍平没有增加深度则弹出
stack.pop();
}
}
} else {
result.push(current);
}
}
return result;
};
typescript 解法, 执行用时: 192 ms, 内存消耗: 73.1 MB, 提交时间: 2023-04-17 15:51:21
type MultiDimensionalArray<T> = (T | MultiDimensionalArray<T>)[]
function flat<T>(arr: MultiDimensionalArray<T>, n: number): MultiDimensionalArray<T> {
return flatten(arr, n)
function flatten(item: MultiDimensionalArray<T>, todo: number): MultiDimensionalArray<T> {
if (todo <= 0) return item
const res: MultiDimensionalArray<T> = []
item.forEach(v => {
if (Array.isArray(v)) {
res.push(...flatten(v, todo - 1))
} else {
res.push(v)
}
})
return res
}
}