php面试题

Question

$a = [  
 '张三' => [  
    '李四' => [  
       '王五' => null,  
       '二六' => null  
     ],  
    '王峰' => [  
      '王芳' => null  
     ]  
 ],  
 '王麻子' => [  
     '小二' => null,  
     '小明' => [  
        '小灰' => null  
      ]  
 ]  
];  

要求写一个函数，输出这样的内容：
张三:李四 王峰 王五 二六  王芳
李四: 王五 二六
王峰:王芳
王麻子:小二 小明 小灰
小明:小灰

Answer 1

<?php

$arr = [
    '张三' => [
        '李四' => [
            '王五' => null,
            '二六' => null
        ],
        '王峰' => [
            '王芳' => null
        ]
    ],
    '王麻子' => [
        '小二' => null,
        '小明' => [
            '小灰' => null
        ]
    ]
];

function mergeArr($nodes, $parent = '')
{
    static $root;
    // 首栈调用时把最初的根节点存起来，后面要销毁的
    array_count_values(array_column(debug_backtrace(), 'function'))[__FUNCTION__] === 1 && $root = $parent;
    // 静态化结果集
    static $result;

    foreach ($nodes as $k => $v) {
        if (is_array($v)) {
            $result[$parent][] = $k;
            // 递归调用
            (__FUNCTION__)($v, $k);
        } else {
            // 最终节点
            is_null($v) && $result[$parent][] = $k;
            // 注意，这里就没有递归的，也就是第一个节点完成了就会跑到下面去了，所以下面需要判断调用栈
        }
    }
    /**
     * 输出递归的栈，如果递归的栈大于 1 则说明第一层还没有循环完成
     * 如果这时候让他去跑下面的内容的话，就会导致重复了，还会导致重复的执行无用的内容
     */
    if (array_count_values(array_column(debug_backtrace(), 'function'))[__FUNCTION__] !== 1) {
        return $result;
    }
    // 移除根节点
    unset($result[$root]);
    foreach ($result as $m => &$n) {
        foreach ($n as $g) {
            // 把它的子节点合并进来
            $n = array_merge($n, $result[$g] ?? []);
        }
    }
    // 取消引用
    unset($n);
    // 格式输出效果
    return array_map(function ($v) {
        return implode(',', $v);
    }, $result);
}

var_dump(mergeArr($arr, 'root'));

Answer 2

代码分别递归收集结果集的键，及对应值部的键值归拢，代码清晰易解 如下

// 1.重构源数据，确保键有序
function rebuild($arr)
{
    $l = [];
    if (is_array($arr)) {
        $keys = array_keys($arr);
        for ($i=0;$i<count($keys);$i++) {
            if (is_null($arr[$keys[$i]])) {
                continue;
            }
            $l[$keys[$i]]=$arr[$keys[$i]];
            $l=array_merge($l, rebuild($l[$keys[$i]]));
        }
    }
    return $l;
}


// 2.递归收集值中的键
function recursive_keys($input)
{
    $output =  array_keys($input);
    foreach ($input as $v) {
        if (is_array($v)) {
            $output = array_merge($output, recursive_keys($v));
        }
    }
    return $output ;
}

// 3. 合并重组
function merge($arr)
{
    $rs = [];
    foreach(rebuild($arr) as $k => $v){
        $rs[$k] = recursive_keys($v);
        echo $k," : ",implode(" ", $rs[$k]),"\n";
    }
    return $rs;
}

merge($a);

效果如下

D:\code-base\algorithm\php>php "d:\code-base\algorithm\php\array\interview.php"
张三 : 李四 王峰 王五 二六 王芳
李四 : 王五 二六
王峰 : 王芳
王麻子 : 小二 小明 小灰
小明 : 小灰