这标题取的好数学 233 ，虽然如此，这些问题其实都遇到过，那么铺平是什么？
数组和对象都可以构成递归结构，暂且把使这类结构平铺成单个对象或者数组的过程称之为铺平，按被铺平的数据类型可以分为两类：
- 数组的铺平
- 对象的铺平
比如
或者
[[1, 2], [3, 4]] 变成 [1, 2, 3, 4]或者
{a: {b: 'hello'}, c: 'world'} 变成 ["a", "b", "c"] 或 ["hello", "world"]# 数组的铺平和它的逆问题 ↵
用递归很好解决铺平
00var flatArr = arr => { 01 if (!Array.isArray(arr)) return [arr]; 02 else { 03 return arr.reduce((acc, cur) => { 04 return acc.concat( flatArr(cur) ) 05 }, []); 06 } 07} 08 09flatArr([1, 2, [3, 4, 5, [[9, 10, 11], [12, 13, 14, 15], 8]], [1, 23, 5, 6, [2, 3, 4, 5], [2]]]) 10// => 11// [1, 2, 3, 4, 5, 9, 10, 11, 12, 13, 14, 15, 8, 1, 23, 5, 6, 2, 3, 4, 5, 2]
它的逆问题其实跟我们平常遇到的
分页 是一样的：00pageArr([1, 2, 3, 4, 5, 6, 7], 3); 01// => 02// [[1, 2, 3], [4, 5, 6], [7]]
可以用
reduce 来实现上述映射：00var pageArr = (arr, n) => { 01 return arr.reduce((acc, cur, idx, its) => { 02 if (idx % n === 0) { 03 let subArr = its.slice(idx, idx + n).map(e => { 04 if (Array.isArray(e)) e = pageArr(e, n); 05 return e; 06 }) 07 08 acc.push(subArr); 09 } 10 11 return acc; 12 }, []); 13} 14 15pageArr([1, 2, [1, 2, 3, 4, 5], 4, 5, 6, 7], 3); 16// => 17// [ [1, 2, [ 18// [1, 2, 3], 19// [4, 5] 20// ] 21// ], 22// [4, 5, 6], 23// [7] 24// ]
子元素也可能是
数组，也得对他们 分页，因此要递归的处理这个问题。# 数组铺平的非递归实现 ↵
补充下，这是最近王小姐考我的（19年1月底），具体实现如下：
00interface NestedArray<T> extends Array<T | NestedArray<T> > {} 01 02function flat<T>(arr: NestedArray<T>): T[] { 03 // 结果存在 result 04 const result: Array<T> = []; 05 // 我自己模拟一个栈 06 const stack: NestedArray<T> = []; 07 08 while (true) { 09 if (stack.length) { 10 // 栈里有东西, 优先处理 11 const list = stack.pop(); 12 13 if (Array.isArray(list)) { 14 if (list.length) { 15 // 嗯 16 const [firstOfList, ...rest] = list; 17 18 if (Array.isArray(firstOfList)) { 19 // 第一个被压入了，第二个要截断，因为 firstOfList 是 list 的第一个 20 stack.push(rest); 21 stack.push(firstOfList); 22 } else { 23 stack.push(rest); 24 result.push(firstOfList); 25 } 26 } else { 27 // 遇到了空数组。。。 不管了 28 // do nothing 29 } 30 } else { 31 result.push(list); 32 } 33 } else { 34 // 从 arr 里取出第一个元素出来。。。 35 const first = arr.shift(); 36 37 if (typeof first === 'undefined') { 38 // arr 没了，该结束了 39 break; 40 } else { 41 // 其余的情况扔进栈 42 stack.push(first); 43 } 44 } 45 } 46 47 return result; 48}
# 对象的铺平和它的逆问题 ↵
实现
flat 处理下面的对象00var o = { 01 "RuntimeSources": { 02 "flask-webapp": { 03 "eb-flask1.3": { 04 "s3url": "" 05 } 06 } 07 }, 08 "DeploymentId": 4, 09 "Serial": 4 10}
使得
flat(o) 得到数组 ["RuntimeSources", "flask-webapp", "eb-flask1.3", "s3url", "DeploymentId", "Serial"]我们可以借助
Object.keys 实现递归地实现 flat ：00var flat = o => { 01 if (typeof o !== 'object') return []; 02 03 // 当层键名 04 var keys = Object.keys(o); 05 06 return keys.reduce((acc, cur) => { 07 return acc.concat( flat(o[cur]) ); 08 }, keys); 09}
以下是简单的调用和返回结果：
00var hello = { 01 hello: '~', 02 wolrd: { 03 nice: '~', 04 to: '~', 05 meet: '~', 06 you: '~' 07 } 08} 09 10flat(hello); 11// => 12// ["hello", "wolrd", "nice", "to", "meet", "you"]
# 另外一个角度解决对象平铺问题 ↵
不论是
数组 还是 对象 都可以作为 JSON.stringify 的参数，并可以被转化成 JSON 字符串。由此，铺平问题就被转化成字符串问题了。
调用处理刚刚的 hello :
JSON.stringify(hello) 可以得到结果："{"hello":"~","wolrd":{"nice":"~","to":"~","meet":"~","you":"~"}}"进一步观察得知：
JSON中，在冒号前的是键名
据此可以实现
flatJSON ，先写几个工具函数：00// 把在 str 中的 willBeReplaced 替换为 toPlace 01var replaceAll = (str, willBeReplaced, toPlace) => { 02 return str.split(willBeReplaced).join(toPlace) 03} 04 05// 把在 str 的全部 willBeCut 替换成 '' 06var cut = (str, willBeCut) => { 07 return replaceAll(str, willBeCut, ''); 08}
使用工具函数实现
flatJSON00var flatJSON = o => { 01 var str = JSON.stringify(o); 02 03 let tokens = ['{', '}', ':', ','].reduce((acc, e) => { 04 // 给 '{' '}' ':' ',' 的两侧补上空格 05 return replaceAll(acc, e, ` ${e} `); 06 07 // 然后调用 split(' ') 把空格删掉， 08 // 最后把空字符串滤掉 09 }, str).split(' ').filter(e => e !== ""); 10 11 // 从 tokens 取得结果 12 // 冒号前的token就是键名 13 return tokens.reduce((acc, cur, idx, its) => { 14 if (cur === ':'){ 15 acc.push(its[idx - 1]); 16 } 17 18 return acc; 19 }, []).map(e => cut(e, '"', '')); 20}
以下是调用
00flatJSON(hello); 01// => 02// ["hello", "wolrd", "nice", "to", "meet", "you"]
# 在上面这个角度上解决数组平铺问题 ↵
00var testArr = [1, 2, [3, 4, 5, [[9, 10, 11], [12, 13, 14, 15], 8]], [1, 23, 5, 6, [2, 3, 4, 5], [2]]]; 01 02console.log(JSON.stringify(testArr)); 03// => 04// [1,2,[3,4,5,[[9,10,11],[12,13,14,15],8]],[1,23,5,6,[2,3,4,5],[2]]]
[1,2,[3,4,5,[[9,10,11],[12,13,14,15],8]],[1,23,5,6,[2,3,4,5],[2]]]进而观察得出：
逗号前的是数组元素
类似解决刚刚上面的那个对象平铺的实现，需要得到 tokens 然后把逗号前的元素挑选出来就 ok 了。
00var flatArrJSON = arr => { 01 let str = JSON.stringify(arr); 02 03 let tokens = ['[', ']', ','].reduce((acc, e) => { 04 // 给 '{' '}' ':' ',' 的两侧补上空格 05 return replaceAll(acc, e, ` ${e} `); 06 07 // 然后调用 split(' ') 把空格删掉， 08 // 最后把空字符串滤掉 09 }, str).split(' ').filter(e => e !== ""); 10 11 return tokens.reduce((acc, cur, idx, its) => { 12 if (cur === ','){ 13 acc.push(its[idx - 1]); 14 } 15 16 return acc; 17 }, []).filter(e => e !== ']'); // 过滤 ']' 因为数组字面量里可能会出现 '],' 这种写法 18} 19 20flatArrJSON(testArr); 21// => 22// ["1", "2", "3", "4", "5", "9", "10", "12", "13", "14", "1", "23", "5", "6", "2", "3", "4"]