V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
lyshine
V2EX  ›  编程

一道前端算法题, 想了要好久没想出来如何写 . 请大神指导一下

  •  
  •   lyshine · 2019-05-21 09:33:32 +08:00 · 5487 次点击
    这是一个创建于 1774 天前的主题,其中的信息可能已经有所发展或是发生改变。

    题目是:

    给一个数据结构如下
    var data = [
    {
        "name": "手机",
        "childs": [
            {
                "name": "iPhone",
                "childs": [
                    {"name": "iPhone X"},
                    {"name": "iPhone XR"},
                    {"name": "iPhone XS"},
                ]
            },
            {
                "name": "HUAWEI",
                "childs": [
                    {"name": "HUAWEI Mate 20"},
                    {"name": "HUAWEI Mate 20 X"},
                    {"name": "HUAWEI Mate 20 Pro"},
                ]
            }
        ]
    }
    

    ];

    然后让封装一个函数, 根据名称得到其遍历的路径. 例如参数是  HUAWEI Mate 20. 那么函数返回 手机 / HUAWEI/HUAWEI Mate 20.  要求函数可以适用多层的数据结构, 例如上面的数据只有三层深度, 如果扩展为 10 层的话函数仍然可以适用. 
    
    这个题目的其实就是一个树的遍历, 然后返回这个遍历路径. 但是想了半天没想到如何写
    
    30 条回复    2023-05-18 10:59:39 +08:00
    zakarycode
        1
    zakarycode  
       2019-05-21 09:47:54 +08:00
    递归考虑下
    Chrisssss
        2
    Chrisssss  
       2019-05-21 09:50:13 +08:00
    递归,把当前的路径传下去就行了。
    geehero
        3
    geehero  
       2019-05-21 09:50:33 +08:00 via iPhone
    To iterate is human, to recurse divine.
    lyshine
        4
    lyshine  
    OP
       2019-05-21 10:05:06 +08:00
    递归我试了, 往下传路径的时候似乎有问题, 各位答主最好能给个可以运行的代码
    voidbit
        5
    voidbit  
       2019-05-21 10:09:36 +08:00 via iPhone   ❤️ 1
    用栈吖,回溯法
    asukanoir
        6
    asukanoir  
       2019-05-21 10:11:34 +08:00
    @lyshine 虽然好多年不写代码了。。。给个愚见:利用栈的思路,执行递归,先深度再广度,然后返回的时候上层调用函数自然会保留父节点路径,按说没有你说的这种问题吧。
    wly19960911
        7
    wly19960911  
       2019-05-21 10:35:55 +08:00   ❤️ 1
    function findPhone(name, node, path ) {
    const newPath = path + '/' + node.name;
    if (node.name != name) {
    if (node.childs) {
    for (let item of node.childs) {
    const result = findPhone(name, item, newPath)
    if(result) {
    return result;
    }
    }
    return false;
    } else {
    return false;
    }
    } else {
    return newPath;
    }
    }

    findPhone('iPhone X', data[0], '');

    实现上可能复杂了点,但是我感觉没必要用栈就是。还得维护状态,直接用基础类型参数连状态都不用管
    noviceiOS
        8
    noviceiOS  
       2019-05-21 10:49:13 +08:00   ❤️ 1
    function getPathByName(data,objName){
    var conf = {};
    function getConf(_data,_path){
    for(var i in _data){
    var __path = _path? _path + "/"+_data[i].name:_data[i].name;
    conf[_data[i].name] = __path;
    if(_data[i].childs){
    getConf(_data[i].childs,__path);
    }
    }
    }
    getConf(data,"");
    return conf[objName];
    }
    alert(getPathByName(data,"HUAWEI Mate 20 Pro"));
    lyshine
        9
    lyshine  
    OP
       2019-05-21 10:53:25 +08:00
    @wly19960911 首先感谢你的回答. 我感觉这个 result 很关键. 这个我就没想到. 我当时就没想到如何在递归中摒弃不需要的路径
    noviceiOS
        10
    noviceiOS  
       2019-05-21 10:59:52 +08:00
    function getPathByName(data,objName){
    var path="";
    function getConf(_data,_path){
    for(var i in _data){
    var __path = _path? _path + "/"+_data[i].name:_data[i].name;
    if(objName==_data[i].name){
    path = __path;
    return;
    }
    if(_data[i].childs){
    getConf(_data[i].childs,__path);
    }
    }
    }
    getConf(data,"");
    return path;
    }
    alert(getPathByName(data,"HUAWEI Mate 20 Pro"));
    lyshine
        11
    lyshine  
    OP
       2019-05-21 11:01:29 +08:00
    @noviceiOS 谢谢, 很棒的回答, 我需要慢慢看下
    shyling
        12
    shyling  
       2019-05-21 11:16:29 +08:00
    为什么不直接预处理一下 { name: a, childs: [b,c,d] } 转成 { b: 'a/b', ... }
    Laumm
        13
    Laumm  
       2019-05-21 11:39:38 +08:00
    path = ""
    function query(tree,name) {
    path += "/" + tree.name
    if (tree.name == name) {
    console.log(path)
    return
    }
    var childs = tree.childs
    if (childs != undefined) {
    for ( var i = 0; i <childs.length; i++){
    query(childs[i],name)
    }
    }
    path= path.substring(0,path.lastIndexOf('/'))
    }


    不太擅长 js
    Laumm
        14
    Laumm  
       2019-05-21 11:43:58 +08:00
    query(data[0],"name")
    Aliennnnnn
        15
    Aliennnnnn  
       2019-05-21 11:50:57 +08:00
    function phoneSearch(targetName, data, path){
    data.map(function (item) {
    let currentPath = path + '/' + item.name;
    if(item.name === targetName){
    return currentPath;
    }else if (item.children) {
    phoneSearch(targetName, item.children, currentPath);
    }
    })
    }

    phoneSearch('HUAWEI Mate 20', data, '');
    geelaw
        16
    geelaw  
       2019-05-21 12:19:48 +08:00 via iPhone
    先 preprocess 把结构 flatten,每次询问时进行路径压缩。

    但是这个数据结构品位很差,因为 child 的复数是一 children。
    Sapp
        17
    Sapp  
       2019-05-21 12:21:31 +08:00
    ```
    const data = [
    {
    name: "手机",
    childs: [
    {
    name: "iPhone",
    childs: [
    { name: "iPhone X" },
    { name: "iPhone XR" },
    { name: "iPhone XS" }
    ]
    },
    {
    name: "HUAWEI",
    childs: [
    { name: "HUAWEI Mate 20" },
    { name: "HUAWEI Mate 20 X" },
    { name: "HUAWEI Mate 20 Pro" }
    ]
    }
    ]
    }
    ];

    const query = (items, arg) =>
    items.map(item => {
    // 如果名字相同
    if (item.name === arg) return item.name;

    // 如果没有子集
    if (!item.childs) return null;

    // 遍历查找子级,并过滤不相干内容
    const childrenResult = query(item.childs, arg).filter(item => !!item);

    // 找到了内容,携带当前名字一同返回上一级
    if (childrenResult.length) return `${item.name} => ${childrenResult[0]}`;

    // 子级也未找到
    return null;
    }).filter(item => !!item);

    query(data, 'HUAWEI Mate 20 Pro')

    // ["手机 => HUAWEI => HUAWEI Mate 20 Pro"]

    ```

    没做任何优化,还是挺好懂得吧
    jjwjiang
        18
    jjwjiang  
       2019-05-21 13:41:30 +08:00
    这不就是最纯粹的递归吗?怎么看楼上一堆还传 path 进去的,还有写 2 个函数的?这就是最简单的递归模式啊

    function getPath(data, name ) {
    for (var i = 0; i < data.length; i++) {
    if (data[i].name == name)
    return "/" + name;
    else if (data[i].childs) {
    var next = getPath(data[i].childs, name);
    if (next)
    return "/" + data[i].name + next;
    }
    }
    return "";
    }
    getPath(data, "HUAWEI Mate 20 X");
    zqx
        19
    zqx  
       2019-05-21 13:47:38 +08:00 via Android
    有人考虑过把结构压扁,然后用字符串操作吗
    panshao
        20
    panshao  
       2019-05-21 14:41:55 +08:00
    function getPhone(node, phone, path) {
    path = path + '/' + node.name;
    if (node.name === phone) {
    return path;
    }
    if (node.childs) {
    for (const child of node.childs) {
    const res = getPhone(child, phone, path);
    if (res) { return res; }
    }
    }
    }
    console.log(getPhone(data[0], 'HUAWEI Mate 20 Pro', ''));
    poisedflw
        21
    poisedflw  
       2019-05-21 15:26:07 +08:00
    function getPhonePath(data = [], name, prefix = []) {
    for (let i = 0, len = data.length; i < len; i++) {
    let tmp = data[i];
    if (prefix.isFind) return prefix;
    prefix.push(tmp.name);
    if (tmp.name === name && (prefix.isFind = true)) return prefix;
    if (tmp.childs) getPhonePath(tmp.childs, name, prefix)
    !prefix.isFind && prefix.pop();
    }
    return [...prefix];
    }

    console.log(getPhonePath(data, "HUAWEI Mate 20 X"));

    加个标志,可以少一层循环。
    nikandaoleshenme
        22
    nikandaoleshenme  
       2019-05-21 16:38:33 +08:00
    @lyshine 竟然从这跑去 sf 了
    redbuck
        23
    redbuck  
       2019-05-21 17:09:35 +08:00
    递归就完了
    ```
    function name2path(list, name, path) {
    return list.reduce((prev, item) => {
    if (item.name === name) {
    return path + '/' + item.name
    }
    else {
    if (item.children) {
    return name2path(item.children, name, path + '/' + item.name) || prev
    }
    return prev
    }
    }, path)
    }
    ```
    redbuck
        24
    redbuck  
       2019-05-21 17:22:11 +08:00
    @redbuck

    错了 reduce 第二个参数应该是''

    function name2path(list, name, path) {
    return list.reduce((prev, item) => {
    // ...
    }, '')
    }
    lyshine
        25
    lyshine  
    OP
       2019-05-21 18:01:58 +08:00
    @nikandaoleshenme 这都被你发现了. 哈哈哈今天刚注册的
    lyshine
        26
    lyshine  
    OP
       2019-05-21 19:26:54 +08:00
    @zqx 你可以看 6 楼的, 他的实现就是扁平了结构
    lyshine
        27
    lyshine  
    OP
       2019-05-21 19:35:47 +08:00
    @zqx 错了 , 是 8 楼的实现
    aihimmel
        28
    aihimmel  
       2019-05-21 23:55:55 +08:00
    python 写的
    def iter_names(a, prefix=''):
    for i in a:
    if 'childs' in i:
    ite(i['childs'], prefix=prefix + i['name'] + '/')
    else:
    print prefix + i['name']
    brucewuio
        29
    brucewuio  
       2019-05-24 15:06:34 +08:00
    function retrievePath(phoneName,obj) {
    for (let i in obj) {
    if (obj[i]['childs']) {
    let returnStr = retrievePath(phoneName,obj[i]['childs'])
    if (returnStr !== '')
    return '/' + obj[i]['name'] + returnStr
    }else {
    if (phoneName === obj[i]['name']) {
    return '/' + obj[i]['name']
    }
    }
    }
    }
    takemyhate
        30
    takemyhate  
       316 天前
    function findPath(data, target) {
    let path = ""; // 用于存储路径

    function traverse(node, currentPath) {
    if (node.name === target) {
    path = currentPath; // 找到目标节点时更新路径
    return;
    }

    if (node.childs) {
    for (let i = 0; i < node.childs.length; i++) {
    const child = node.childs[i];
    const newPath = currentPath ? `${currentPath} / ${child.name}` : child.name;
    traverse(child, newPath); // 递归遍历子节点
    }
    }
    }

    traverse(data, "");

    return path;
    }

    // 测试
    var data = [
    {
    name: "手机",
    childs: [
    {
    name: "iPhone",
    childs: [
    { name: "iPhone X" },
    { name: "iPhone XR" },
    { name: "iPhone XS" },
    ],
    },
    {
    name: "HUAWEI",
    childs: [
    { name: "HUAWEI Mate 20" },
    { name: "HUAWEI Mate 20 X" },
    { name: "HUAWEI Mate 20 Pro" },
    ],
    },
    ],
    },
    ];

    console.log(findPath(data[0], "HUAWEI Mate 20")); // 输出 "手机 / HUAWEI / HUAWEI Mate 20"
    //findPath 函数接受两个参数:data 是树的根节点,target 是要查找的目标节点的名称。函数通过递归遍历树的节点,每次遍历时更新当前路径,并检查当前节点是否为目标节点,如果是则将路径存储到 path 变量中。最终返回得到的路径。这个可以适用于多层的数据结构,因为它通过递归方式遍历树的每个节点,不论树的深度有多大,都能正确地找到路径。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2826 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 31ms · UTC 13:16 · PVG 21:16 · LAX 06:16 · JFK 09:16
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.