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

一道面试题,求解

  •  
  •   lalala121 · 2018-04-02 22:53:25 +08:00 · 2481 次点击
    这是一个创建于 2186 天前的主题,其中的信息可能已经有所发展或是发生改变。

    已知有这么一个数组

    $a = array(
    	'a'      =>  1,
    	'b.b.c'  =>  2,
    	'b.b.d'  =>  3,
    	'b.b.e'  =>  4,
    	'f.g'    =>  5,
    );
    

    处理后变为

    $b = array(
        'a'    =>  1,
        'b'    =>   array(
            'b'     =>  array(
                'c' =>  2,
                'd' =>  3,
                'e' =>  4,
            ),
        ),
        'f'   =>    array(
            'g'     => 5,
        ),
    );
    

    请问该怎么处理,给点思路,谢谢

    10 条回复    2018-04-17 13:51:29 +08:00
    namedfish
        1
    namedfish  
       2018-04-03 00:05:13 +08:00 via iPhone
    这结构看起来就像前缀树
    johnhsm2333
        2
    johnhsm2333  
       2018-04-03 00:38:24 +08:00 via Android
    单词查找树
    blodside
        3
    blodside  
       2018-04-03 02:45:58 +08:00 via Android
    字典树啊
    4357
        4
    4357  
       2018-04-03 07:22:47 +08:00
    楼上的回答都不靠谱
    简单的做法,遍历原来的 map 的 key,用'.'切分成字符串数组,然后遍历这个数组,一层层建立 map
    shenqi
        5
    shenqi  
       2018-04-03 09:39:05 +08:00
    看不懂,为啥数组还给 key,如果是对象,直接用 lodash.set 算不算作弊。
    yunfeifan
        6
    yunfeifan  
       2018-04-03 09:45:39 +08:00
    姑且认为你给的是个 map 吧! 仅供参考一下!
    var test_arr = {
    'a': 1,
    'b.b.c': 2,
    'b.b.d': 3,
    'b.b.e': 4,
    'f.g': 5
    };


    expandArr = (arr) => {
    let res = {};
    let expand = (item, value) => {
    let paths = item.split('.');
    if (paths.length > 1) {
    setChild(res, paths, value);
    } else {
    res[paths[0]] = value;
    }
    }
    let setChild = (obj, paths, value) => {
    if (paths.length === 0) {
    return;
    }
    if (paths.length === 1) {
    obj[paths] = value;
    } else {
    if (!(paths[0] in obj)) {
    obj[paths[0]] = {};
    }
    setChild(obj[paths[0]], paths.slice(1,), value);
    }
    }
    for(let item of Object.keys(arr)){
    expand(item, arr[item]);
    }
    return res;
    }

    expandArr(test_arr)
    enenaaa
        7
    enenaaa  
       2018-04-03 11:13:05 +08:00
    直接写呗还能怎么处理
    shenhhd
        8
    shenhhd  
       2018-04-03 12:33:52 +08:00
    看语法有点像是 php 啊

    $a = array(
    'a' => 1,
    'b.b.c' => 2,
    'b.b.d' => 3,
    'b.b.e' => 4,
    'f.g' => 5,
    );



    $newarray=[];
    foreach($a as $k =>$value){
    $keys = explode('.',$k);
    $a=$value;
    $keys = array_reverse($keys);
    foreach($keys as $v){
    $a=[$v=>$a];
    }

    my_merge($newarray,$a);

    }



    function my_merge(&$a,$b){

    foreach($a as $key=>&$val){
    if(is_array($val) && array_key_exists($key, $b) && is_array($b[$key])){
    my_merge($val,$b[$key]);
    $val = $val + $b[$key];
    }else if(is_array($val) || (array_key_exists($key, $b) && is_array($b[$key]))){
    $val = is_array($val)?$val:$b[$key];
    }
    }
    $a = $a + $b;
    }



    print_r($newarray);
    dan2001go
        9
    dan2001go  
       2018-04-03 14:37:48 +08:00
    早上看了一下,本来想写的,结果时间来不及,要赶着去面试。。
    回来一看已经有人解答了,我写到一半,也贴出来吧,这个就是 PHP 了。
    思路都差不多,用递归的方式求解。这块水平好差。。有一次面试直接让我机试,心里紧张,磨了半天当场写不出来,估计别人觉得我水平太 LOW 了囧。


    <?php

    date_default_timezone_set('Asia/Shanghai');

    $a = array(
    'a' => 1,
    'b.b.c' => 2,
    'b.b.d' => 3,
    'b.b.e' => 4,
    'f.g' => 5,
    'b.q.e' => 6,
    );

    $obj = array();

    foreach($a as $k=>$v){
    $tree = explode('.',$k);
    if(count($tree)>1){
    $index = 1;
    if(!isset($obj[$tree[0]])){
    $obj[$tree[0]] = array();
    }
    loop($obj[$tree[0]],$tree,$index,$v);
    }else{
    $obj[$k] = $v;
    }
    }

    function loop(&$obj,$src,$index,$value){

    if($index == count($src)){
    return false;
    }
    if($index == count($src)-1){
    $tmp = $value;
    }else{
    $tmp = null;
    }
    $add = false;
    if(!is_null($obj)){
    if(array_key_exists($src[$index],$obj) === true){
    $add = true;
    }
    }

    if($add != true){
    $obj[$src[$index]] = $tmp;
    }

    $offset = $src[$index];
    $index++;
    loop($obj[$offset],$src,$index,$value);
    }

    var_dump($obj);
    JackZong
        10
    JackZong  
       2018-04-17 13:51:29 +08:00
    @shenqi PHP
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3265 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 14:15 · PVG 22:15 · LAX 07:15 · JFK 10:15
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.