一道实际工作中遇到的算法题

算法题"/>

一道实际工作中遇到的算法题

文章目录

• 前言
• 问题描述
• 解决思路
• 完整代码
• 结语

前言

虽然在实际工作（开发岗位）中几乎很难遇到让自己手写算法的情形，因为往往我们会有两种解决方案：拥有现成的算法api函数库供我们使用以及通过百度直接cv大佬们提供的现成算法代码。
但是，有句古话说得好，常在河边走哪有不湿鞋，这不，天有不测风云，我就湿鞋了。

问题描述

问题很简单，给定一种格式的原数据集，通过某种算法将其转变为目标格式的数据集。
下面，我给出一组实例数据：
原数据集：

const data = [{id: 'Jack',pid: null,status: 'CEO'},{id: 'Lexie',pid: 'Jack',status: 'QA Lead'},{id: 'Anlyiah',pid: 'Jack',status: 'Manager'},{id: 'Elliot',pid: 'Lexie',status: 'QA'},{id: 'Anahi',pid: 'Lexie',status: 'QA'},{id: 'Knox',pid: 'Lexie',status: 'QA'},{id: 'Lucas',pid: 'Anlyiah',status: 'Marketer'},{id: 'Adan',pid: 'Lucas',status: 'Designer'},{id: 'Alex',pid: 'Lucas',status: 'Sales'},
];

目标数据集：

const targetData = {id: 'Jack',pid: null,status: CEO,children: [{id: 'Lexie',pid: 'Jack',status: 'QA Lead',children: [{id: 'Elliot',pid: 'Lexie',status: 'QA'},{id: 'Anahi',pid: 'Lexie',status: 'QA'},{id: 'Knox',pid: 'Lexie',status: 'QA'},]},{id: 'Anlyiah',pid: 'Jack',status: 'Manager',children: [{id: 'Lucas',pid: 'Anlyiah',status: 'Marketer',children: [{id: 'Adan',pid: 'Lucas',status: 'Designer'},{id: 'Alex',pid: 'Lucas',status: 'Sales'}]}]},]
};

仔细看看是不是感觉很像多叉树的某种转换遍历问题，对的，没错，就是它了！
我也给出其用树的形式展现出来的效果图：（只显示出id属性）

解决思路

首先，不难发现树节点之间的关系是通过id与pid之间的关系来构建的，而目标数据与原数据相比多了一个children这个属性，并且需要从原数据的一维数组的形式完全转变为一个树的结构。
核心思路：首先，我们需要找到树的根节点，紧接着找到其第一个子节点并且通过children属性将其连接，继续递归直到找到此分支的叶子节点继而回退拼接其下一条分支，从宏观的角度来看，程序的流程类似于树的先序遍历（根左右），而拼接的逻辑类似于树的后序遍历（左右根）。

完整代码

Talk is cheap,Show you my code!

function mergeData(targetData, children = null) {const data = {};data['id'] = targetData['id'];data['pid'] = targetData['pid'];data['status'] = targetData['status'];if (children) {data['children'] = children;}return data;
}function appendChildren(sourceData, rootParents, pid) {const children = sourceData.filter(data => data.pid === pid);if (children) {children.forEach(child => {//根据是否为叶子节点来进行相应的递归逻辑if (sourceData.some(data => data.pid === child.id)) {const rootChildren = [];rootParents.push(this.mergeData(child, rootChildren));this.appendChildren(sourceData, rootChildren, child.id);} else {rootParents.push(this.mergeData(child));}})}
}function getRoot(sourceData) {//通过在查找不属于id的pid来确定根节点const ids = [];sourceData.forEach(data => ids.push(data.id));const root = sourceData.find(data => !ids.includes(data.pid));return root;
}function formatData(sourceData) {const root = this.getRoot(sourceData);const rootChildren = [];this.appendChildren(sourceData, rootChildren, root.id);return this.mergeData(root, rootChildren);
}

我这里简单解释这四个函数的功能：

• formatData：直接调用此函数即可将原数据格式转换为目标数据格式。
• getRoot：找到根节点数据。
• mergeData：将原数据形式的object转换为目标数据形式的object。
• appendChildren：使用递归的手段来遍历并为目标数据创建树结构。

结语

细心的读者应该不难发现，其实我这算法的效率并不高，我总觉得应该此问题应该还有更高效的算法实现方式，但是我本人的能力仅限于此了，还望有大佬读者能在评论区赐教。
算法这块知识领域虽然在实际工作上难以真正的大展拳脚，但是其本身也是一门及其重要的基本功，所以咱也不能完全的轻视甚至是忽视它，毕竟有还有句经典的古话说得好，不怕一万就怕万一嘛，书到用时方恨少啊！