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

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

  •  
  •   lyshine · 150 天前 · 3274 次点击
    这是一个创建于 150 天前的主题,其中的信息可能已经有所发展或是发生改变。

    题目是:

    给一个数据结构如下
    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 层的话函数仍然可以适用. 
    
    这个题目的其实就是一个树的遍历, 然后返回这个遍历路径. 但是想了半天没想到如何写
    
    29 回复  |  直到 2019-05-24 15:06:34 +08:00
        1
    zakarycode   150 天前
    递归考虑下
        2
    Chrisssss   150 天前
    递归,把当前的路径传下去就行了。
        3
    geehero   150 天前 via iPhone
    To iterate is human, to recurse divine.
        4
    lyshine   150 天前
    递归我试了, 往下传路径的时候似乎有问题, 各位答主最好能给个可以运行的代码
        5
    voidbit   150 天前 via iPhone   ♥ 1
    用栈吖,回溯法
        6
    asukanoir   150 天前
    @lyshine 虽然好多年不写代码了。。。给个愚见:利用栈的思路,执行递归,先深度再广度,然后返回的时候上层调用函数自然会保留父节点路径,按说没有你说的这种问题吧。
        7
    wly19960911   150 天前   ♥ 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], '');

    实现上可能复杂了点,但是我感觉没必要用栈就是。还得维护状态,直接用基础类型参数连状态都不用管
        8
    noviceiOS   150 天前   ♥ 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"));
        9
    lyshine   150 天前
    @wly19960911 首先感谢你的回答. 我感觉这个 result 很关键. 这个我就没想到. 我当时就没想到如何在递归中摒弃不需要的路径
        10
    noviceiOS   150 天前
    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"));
        11
    lyshine   150 天前
    @noviceiOS 谢谢, 很棒的回答, 我需要慢慢看下
        12
    shyling   150 天前
    为什么不直接预处理一下 { name: a, childs: [b,c,d] } 转成 { b: 'a/b', ... }
        13
    Laumm   150 天前
    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
        14
    Laumm   150 天前
    query(data[0],"name")
        15
    Aliennnnnn   150 天前
    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, '');
        16
    geelaw   150 天前 via iPhone
    先 preprocess 把结构 flatten,每次询问时进行路径压缩。

    但是这个数据结构品位很差,因为 child 的复数是一 children。
        17
    Sapp   150 天前
    ```
    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"]

    ```

    没做任何优化,还是挺好懂得吧
        18
    jjwjiang   150 天前
    这不就是最纯粹的递归吗?怎么看楼上一堆还传 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");
        19
    zqx   150 天前 via Android
    有人考虑过把结构压扁,然后用字符串操作吗
        20
    panshao   150 天前
    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', ''));
        21
    poisedflw   150 天前
    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"));

    加个标志,可以少一层循环。
        22
    nikandaoleshenme   150 天前
    @lyshine 竟然从这跑去 sf 了
        23
    redbuck   150 天前
    递归就完了
    ```
    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)
    }
    ```
        24
    redbuck   150 天前
    @redbuck

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

    function name2path(list, name, path) {
    return list.reduce((prev, item) => {
    // ...
    }, '')
    }
        25
    lyshine   150 天前
    @nikandaoleshenme 这都被你发现了. 哈哈哈今天刚注册的
        26
    lyshine   150 天前
    @zqx 你可以看 6 楼的, 他的实现就是扁平了结构
        27
    lyshine   150 天前
    @zqx 错了 , 是 8 楼的实现
        28
    aihimmel   150 天前
    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']
        29
    brucewuio   147 天前
    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']
    }
    }
    }
    }
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   1984 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 25ms · UTC 16:02 · PVG 00:02 · LAX 09:02 · JFK 12:02
    ♥ Do have faith in what you're doing.