如何将评论数据从扁平数组结构转为树形结构 我们在之前的文章 如何实现一个楼中楼的评论系统，主要讲解了楼中楼评论系统的设计初衷、数据库表的结构，但没有讲解从数据库中拿到数据后，如何转成楼中楼的结构。 1. 定义下数据结构 # 我是使用的 mysql 数据库，mysql 数据库中是以行为单位，来存储数据的。我们从数据库中拿到的数据是一个数组结构，大致如下，我最初考虑楼中楼最多只嵌套一层，因此加了一个pid字段用来表示该评论在哪个评论里：/** * 从数据库中查询到一篇文章里的所有评论 * id: 当前评论的id * pid: 当前评论在哪个评论里，0表示是顶层评论 * replyid: 该评论回复的是哪个评论，0表示是顶层评论 * content: 内容 */ const list = [ { id: 1, pid: 0, replyid: 0, nick: '111', content: '' }, { id: 2, pid: 0, replyid: 0, nick: '222', content: '' }, { id: 3, pid: 2, replyid: 2, nick: '333', content: '' }, { id: 4, pid: 2, replyid: 3, nick: '444', content: '' }, { id: 5, pid: 2, replyid: 4, nick: '555', content: '' }, { id: 6, pid: 1, replyid: 1, nick: '666', content: '' }, { id: 7, pid: 2, replyid: 3, nick: '777', content: '' }, ]; 接下来，让我们通过代码来实现下数组转为树（楼中楼）的结构。 2. 嵌套一层的楼中楼 # 我们先实现一个只嵌套一层的树结构。我们要实现的结构是这样的，若直接回复上层的评论，则省略该评论回复的是谁，若回复的是楼中楼的评论，则展示出回复的是哪条：- 1 |- 6 - 2 |- 3 |- 4 -> 3 |- 5 -> 4 |- 7 -> 3 我们分析下 list 中数据的特点： 每条数据都有个pid和replyid两个字段，指向他的父级，但若 pid 和 replyid 为 0 时，则表示该评论自己就是最顶层的评论； 后一条评论回复之前的评论，pid 和 replyid 两个字段的值一定是存在的（不可能回复一条不存在的评论）； 依托于 js 中的对象引用的特性：在不同的地方操作相同的对象，所有使用该对象的数据都会发生变化。其实这并不是一个好的特性，但在这里特别好使。我们可以直接把后面的数据添加到前面的数据字段中。const listToTree = (list) => { const newList = JSON.parse(JSON.stringify(list)); // 避免影响外层的数组 const map = new Map(); const result = []; newList.forEach((comment) => { map.set(comment.id, comment); if (comment.pid) { // 楼中楼的评论 const parentComment = map.get(comment.pid); // 回复的该评论，该评论是一定存在的 if (!parentComment.children) { parentComment.children = []; // 通过对象引用，可以直接修改之前的数据 } if (comment.pid !== comment.replyid) { comment.replyNick = map.get(comment.replyid).nick; } parentComment.children.push(comment); } else { result.push(comment); } }); return result; }; 最终实现的效果的示意图： 3. 不限制层数的树结构 # 若我们不限制树结构的层数，该怎么实现呢？我们在这里把 list 数组的结构稍微改下，去掉 pid 的干扰，并再添加几条数据：/** * 从数据库中查询到一篇文章里的所有评论 * id: 当前评论的id * replyid: 该评论回复的是哪个评论，0表示是顶层评论 * content: 内容 */ const list = [ { id: 1, replyid: 0, nick: '111', content: '' }, { id: 2, replyid: 0, nick: '222', content: '' }, { id: 3, replyid: 2, nick: '333', content: '' }, { id: 4, replyid: 3, nick: '444', content: '' }, { id: 5, replyid: 4, nick: '555', content: '' }, { id: 6, replyid: 1, nick: '666', content: '' }, { id: 7, replyid: 3, nick: '777', content: '' }, { id: 8, replyid: 5, nick: '888', content: '' }, { id: 9, replyid: 8, nick: '999', content: '' }, { id: 10, replyid: 9, nick: 'aaa', content: '' }, { id: 11, replyid: 10, nick: 'bbb', content: '' }, ]; 其实不限制树结构的层数，要比固定的层数简单一些，不用判断是否要折叠树结构，一直追加下去即可。 3.1 使用循环的方式 # 我们顺着上面循环的方式，来实现下不限制层数的树结构。const listToTreeDeep = (list) => { const newList = JSON.parse(JSON.stringify(list)); // 避免影响之前的数组 const map = new Map(); const result = []; newList.forEach((comment) => { map.set(comment.id, comment); if (comment.replyid) { // 楼中楼的评论 const parentComment = map.get(comment.replyid); // 回复的该评论，该评论是一定存在的 if (!parentComment.children) { parentComment.children = []; } // 这里按照层级来表示回复关系，不再获取要回复的哪个评论 // if (comment.pid !== comment.replyid) { // comment.replyNick = map.get(comment.replyid).nick; // } parentComment.children.push(comment); } else { result.push(comment); } }); return result; }; 最终实现的效果示意图：具体效果可以查看实现的 demo：【 数组转树结构的自定义层数的循环实现方式 】。 3.2 使用递归的方式 # 无限嵌套的结构也可以使用递归的方式，但这并不是最好的方式，因为每次递归都要用当前 id 循环查找一次。我们在这里用代码实现一次，但不推荐这种方式。/** * @param {any[]} list 评论列表 * @param {number} replyid 回复的那个评论的id **/ const listToTreeRecursion = (list, replyid = 0) => { const newList = JSON.parse(JSON.stringify(list)); // 避免影响之前的数组 const result = []; newList.forEach((comment) => { if (comment.replyid === replyid) { comment.children = listToTreeRecursion(list, comment.id); result.push(comment); } }); return result; }; 递归中我们不使用额外的数据来存储数据，是因为每次的执行，都会从头循环一遍。 4 自定义层数的树结构 # 若再复杂一点，可以自定义层数 n，前 n-1 层一直向内嵌套，最后的第 n 层采用平铺的方式。即把前面的两种展示方式进行结合。这里我们依然分成两部分来讲解。 4.1 使用循环的方式 # 上面不限制层数时，直接往其父级的 children 属性中追加即可。但现在可以自定义层数后，就要在循环时，判断当前节点的深度，若该节点的深度小于 设定的层数 n ，则添加到其父级的 children 中；否则就得添加到其深度为 n-1 的祖先节点的 children 里。我在这里使用了两个字段来进行标记： deep: 当前节点的深度； pid: 该节点所属的父级节点是哪个； 具体的代码实现：/** * @param {any[]} list 评论列表 * @param {number} maxPath 自定义的层数 **/ const listToTreeSelf = (list, maxPath = 4) => { const newList = JSON.parse(JSON.stringify(list)); const map = new Map(); const result = []; newList.forEach((comment) => { map.set(comment.id, comment); if (comment.replyid) { // 楼中楼的评论 const parentComment = map.get(comment.replyid); comment.deep = parentComment.deep + 1; // 当前深度是父级节点的深度+1 if (comment.deep >= maxPath) { // 若当前节点的深度超过了设定的最大深度 // 则该节点不能挂载在其父节点了， // 通过父节点的pid查找父节点挂载在哪个节点上， // 该节点也挂载上面 const ancestorComment = map.get(parentComment.pid); comment.replyNick = parentComment.nick; if (!ancestorComment.children) { ancestorComment.children = []; } // 当前节点挂载的节点 comment.pid = ancestorComment.id; ancestorComment.children.push(comment); } else { // 没有超过设定的最大深度 // 挂载在其父节点上 if (!parentComment.children) { parentComment.children = []; } comment.pid = parentComment.id; parentComment.children.push(comment); } } else { comment.deep = 0; result.push(comment); } }); return result; }; 假设我们设定的最大层数为 4，最终的效果是： 4.2 使用递归的方式 # 在使用递归的方式来构建自定义层数的树形结构时，当深度达到设定的最大层级时，就需要转为循环了。然后开始查找该节点下所有的子节点和子孙节点。 注意：这里不要遗漏子孙节点。 const listToTreeSelfRecursion = (list, maxPath = 4, replyid = 0) => { const newList = JSON.parse(JSON.stringify(list)); // 避免影响之前的数组 const result = []; newList.forEach((comment) => { if (maxPath child.id === comment.replyid); if (child) { comment.replyNick = child.nick; result.push(comment); } } } else { // 还可以继续递归 if (comment.replyid === replyid) { comment.children = listToTreeSelfRecursion(list, maxPath - 1, comment.id); result.push(comment); } } }); return result; }; 5. 不规则的数组 # 我们在上面所有的循环实现中，都默认了父节点在前面，毕竟对评论系统而言，肯定现有的父级评论，才能有当前评论。但比如我们把场景扩展到无限嵌套的部门列表中时，就不一定有序了。最近新创建了一个中间部门，然后把下面所有的部门都归属到这个中间部门里。就会出现父级节点在后面的情况。这里我们只以不限层数的循环实现方式为例，看下若父级节点在后面，如何实现：// 把数据调换下位置 const list = [ { id: 6, pid: 1, replyid: 1, nick: '666', content: '' }, { id: 7, pid: 2, replyid: 3, nick: '777', content: '' }, { id: 8, pid: 2, replyid: 5, nick: '888', content: '' }, { id: 9, pid: 2, replyid: 8, nick: '999', content: '' }, { id: 10, pid: 2, replyid: 9, nick: 'aaa', content: '' }, { id: 11, pid: 2, replyid: 10, nick: 'bbb', content: '' }, { id: 1, pid: 0, replyid: 0, nick: '111', content: '' }, { id: 2, pid: 0, replyid: 0, nick: '222', content: '' }, { id: 3, pid: 2, replyid: 2, nick: '333', content: '' }, { id: 4, pid: 2, replyid: 3, nick: '444', content: '' }, { id: 5, pid: 2, replyid: 4, nick: '555', content: '' }, ]; const listToTreeDeep = (list) => { const newList = JSON.parse(JSON.stringify(list)); // 避免影响之前的数组 const map = new Map(); const result = []; newList.forEach((comment) => { // 可能先把该节点的children存储起来 // 这里把之前存储的数据合并下，然后再存储起来 comment = { ...comment, ...map.get(comment.id) }; map.set(comment.id, comment); if (comment.replyid) { // 楼中楼的评论 const parentComment = map.get(comment.replyid) || {}; // 以空的Object兜底 if (!parentComment.children) { parentComment.children = []; } parentComment.children.push(comment); map.set(comment.replyid, parentComment); } else { result.push(comment); } }); return result; }; 可见在乱序的情况下，逻辑就要多一些。在可行的情况，我们把父级节点放在前面，但若实现起来比较困难，上面的那种方式也是可行的。 6. 总结 # 我们从最开始的二层楼中楼结构，扩展到了无限层级，最终扩展到了可以自定义层级。就目前递归的实现方式来看，并没有循环的性能好，因为每次递归都要循环一遍数据，若在数组节点比较多时，递归的性能就会直线下降。下一篇文章，我们再讨论下，如何把树形结构转成数组结构。

树形结构转为扁平数组结构 我们在之前一篇文章 如何将评论数据从扁平数组结构转为树形结构 ，讲解过如何把数组结构转为树形结构。这里我们讲下，如何将树形结构转为扁平的数组结构。我们先来定义一个树形结构的数据：const tree = [ { id: 1, nick: '111', children: [{ id: 6, nick: '666' }], }, { id: 2, nick: '222', children: [ { id: 3, nick: '333', children: [ { id: 4, nick: '444', children: [ { id: 5, nick: '555', children: [ { id: 8, nick: '888' }, { id: 9, nick: '999' }, { id: 10, nick: 'aaa' }, { id: 11, nick: 'bbb' }, ], }, ], }, { id: 7, nick: '777' }, ], }, ], }, ]; 这是一个多层级的树形结构，我们把它转成数组。这里我们有两个方式来进行转换：深度优先和广度优先。即优先使用当前节点的子节点，还是优先当前节点的兄弟节点。 1. 深度优先转换 # 深度优先，即若当前节点有子节点，优先遍历子节点，直到没有子节点，才遍历其兄弟节点。// 深度优先 const treeToListDepth = (tree) => { let result = []; tree.forEach((item) => { result.push(item); // 将该节点压进去 // 若该节点有子节点，则优先执行子节点 if (Array.isArray(item.children) && item.children.length) { result = result.concat(treeToListDepth(item.children)); } }); return result; }; 我们输出下结果：从数组的排列顺序中，也能看到，子节点要比兄弟节点更靠前。 2. 广度优先转换 # 广度优先，即若当前节点有兄弟，优先遍历兄弟节点，有子节点时，则先存起来，等待后续的遍历。const treeToListBreadth = (tree) => { let queue = tree; // 用一个队列来存储将要遍历的节点 const result = []; while (queue.length) { const item = queue.shift(); result.push(item); // 子节点存储到队列中，等待遍历 if (Array.isArray(item.children) && item.children.length) { queue = queue.concat(item.children); } } return result; }; 我们输出下结果：从数组的排列顺序中，也能看到，兄弟节点要比子节点更靠前。 3. 总结 # 无论是深度优先还是广度优先，复杂度都差不多。从图片上也能看到，这里我们并没有进行特殊的处理，有几个节点的children还在，更细致的话，应该把每个节点的 children 属性去掉。

真没必要再对 axios 进行过度的封装 前几天在某网站上看到一篇文章，说是用 ts 对 axios 进行了下封装，从点赞量、评论量和访问量上来看，有很多人都看过这篇文章了。我之前也看过 axios 的源码，也基于 axios 进行过扩展和二次封装。对 axios 的内部原理和使用方式不可谓不熟悉。虽然很多人在评论里说，收益匪浅啊，写的真棒啊等等，但我通读完整篇文章，得到的结论是：完全没必要。 1. 完全没必要 # 有的开发者喜欢基于 axios 再在外层封装一层，但这种方式实现的成本太高。无论是实现跟 axios 一样的功能，还是外层进行简化，然后再按照 axios 的方式传给 axios，都增加了很多开发的成本。如：const myAxios = async (config) => { /** * 中间各种封装，然后最后再使用axios发起请求1 * */ try { const { status, data } = await axios(config); if (status >= 200 && status { const [loading, setLoading] = useState(false); const [error, setError] = useState(null); const [result, setResult] = useState(null); useEffect(() => { setLoading(true); axios(config) .then(setResult) .catch(setError) .finally(() => { setLoading(false); }); }, []); return { loading, error, result }; }; 更具体的如何在 React 封装一个请求的 hook，可以参考该链接：使用 react 的 hook 实现一个 useRequest。有的封装，是为了减少项目整体的改造成本，和其他人学习新用法的成本。比如之前我也基于 axios，在外层封装过一个请求库。当时为了跟之前的请求方式保持一致，就在外层额外封了一层。后来就出现当需要扩展功能时，特别麻烦，还不如从一开始设计时，就仅仅扩展他的适配器，或者几个简单的配置就行。在封装的时候，首先我们要明白 axios 可以完成什么工作，他实现这些功能都有什么意义，为什么可以传入这些字段，又为什么要返回了那么多字段（我明明只需要接口返回的 data）？想明白这些问题，就知道我们要保留什么，如何进行扩展和封装了。 3. 总结 # 我在很久之前写过一篇文章：前端工程师如何通过造轮子提高自己，但似乎这篇文章的观点与之前的冲突了。其实，并不冲突。造轮子是为了通过模仿成熟的作品来提高自己，但真的在实际应用时，我们就要考虑得更多。自己实现出来的东西，大部分都比不上社区里经过千锤百炼验证过的。而且在使用的过程中，还要考虑减少其他人的学习成本。比如你就不想用 Vue，觉得 Vue 这个框架优点大，然后选择了一个叫mini-vue的框架来开发项目。就社区完善程度来说，这个 mini 版肯定是比不上官方 Vue 的，后来者还得重新学习 mini 版的语法，当遇到问题时，都不知道去问谁，毕竟这个问题，只有 mini 版里才会有，其他人用的少，解答的人也少。

leetcode367 判断该数是否是完全平方数 题目地址 367. 有效的完全平方数。题目要求不能用库函数来直接开平方，本意是希望用二分法来解决该问题。 1. 完全平方数的解决方案 # 两种方式： 直接检索：从 1 开始匹配，挨个儿匹配 num，直到能匹配上（返回 true），或超过 num（返回 false）。时间复杂度为 O(n)； 二分查找：取中间数来匹配 num，匹配上就直接返回，否则根据大小来决定取左边或者右边； 无论使用哪种方式，都应该注意类型范围和精度这两个问题。题目中限制了 num 的范围在[1, 2^31-1]，若我们选择了 int 类型，并且用乘方结果来跟 num 进行匹配时，无论是直接检索还是二分查找，都会极大概率出现超过类型范围的问题。这里应该选择long long类型。同时，取中间值时，不要直接(left+right)/2，这也会超出 int 范围的，应该使用 left + 偏移量的方法：mid = left + (right - left) / 2; 我们换个角度，为避免数字超过类型范围，用 num 来除以这个数 mid，再判断商是否等于 mid。但在 C/C++中，会舍弃小数，导致判断失败，如 10000 和 10001 两个数字：int result0, result1, mid = 100; result0 = 10000 / 100; result1 = 10001 / 100; result0 == mid; // 正确，expect true, receive true result1 == mid; // 错误, expect false, receive true 这里最好再用取余判断下是否可以整除，最终的代码：class Solution { public: bool isPerfectSquare(int num){ int left, right, mid; int square; left = 1; right = num; while (left mid) { left = mid + 1; } else { right = mid - 1; } } // 没找到 return false; } }; 2. 平方根 # 这里还有个上面平方数的姊妹篇：69. x 的平方根，即求 x 的平方根的整数位置。跟上面的思路一样，要考虑取中间数的方式和用于相除来代替相乘，避免超出整型数字范围。最终实现的代码如下：class Solution { public: int mySqrt(int x){ if (x 1); result = x / mid; // 已自动取整 if (result == mid) { return mid; } if (result > mid) { // result大，说明mid做为除数偏小，应当向右移动 left = mid + 1; } else { right = mid - 1; } } return right; } }; 关键点在于 x / mid在强制类型的语言中会自动取整，因此若mid == x / mid时，就说明 mid 是 x 的平方根的整数部分。如数字 4 的平方根正好是 2 ；而 5/2==2，因此 2 就是 5 的平方根的整数部分；数字 6 则是在循环里找不到对应的数字的，会在最后返回 right 指向的值。

leetcode2244 如何使用最少的轮数完成任务 题目链接：2244. 完成所有任务需要的最少轮数。题目的关键点有： 只能完成相同难度级别的任务； 每轮只能完成 2 个或 3 个任务； 使用最少的轮数； 因此我们的思路应当是：统计每个难度级别任务的数量，然后优先 3 个一轮来完成任务，最后剩下的再通过 2 个任务的组合来完成。 只有难度级别的任务的数量为 1 时，无法完成，数量>=1 的，都可以通过 2 和 3 的组合来完成。 优先完成 3 个相同级别的任务，那么最后任务剩余的数量可能是： 0 个：恰好是 3 的倍数； 1 个：还剩下 1 个，但这种情况最后一轮就无法完成了，因此再从前面拿出一个 3，通过 2+2 的方式完成； 2 个：通过完成 2 个相同难度级别的方式完成； 最终实现的 C++代码：class Solution { public: int minimumRounds(vector &tasks){ map location; // 存储每个级别任务的数量 int leftTaskNum; // 相同级别任务3个一轮全部完成，剩余的任务数量 for (int i = 0, size = tasks.size(); i < size; i++) { auto it = location.find(tasks[i]); if (it == location.end()) { location.insert(pair(tasks[i], 1)); } else { it->second += 1; } } map::iterator it = location.begin(); int num = 0; while (it != location.end()) { int item = it->second; if (item