分享一个数据结构算法的机试题

前几天的一个机试题,记忆有点模糊了,可能有点不一样,但是大概就是这样的:

原有的数据结构:

$array = array(
    'a' => array(
        'a1' => array(
            'a1_1' => array(
                array('a1_1_1')
            ),
            'a1_2' => array()
        ),
        'a2' => array(
            array('a2_1'),
            array('a2_2'),
            array('a2_3')
        )
    ),
    'b' => array()//...n+1
    );

要求是这样的:

写出一个函数,将上述数据结构,改变为下面要求的数据结构。

  • a$arr 数组当中,表示有多个这样的数据结构需要统计。
  • a 下面有 2 个直接下级,分别是a1 ,a2
  • a1 下面有两个直接下级分别是a1_1 ,a1_2
  • a1_1 下面有 1 个下级,为a1_1_1
  • a2 下面有三个下级分别是a2_1 ,a2_2 ,a2_3
  • 现要求,a 显示直接下级数为 2,间接下级数为 6,合计下级数为 8。
  • a1 显示直接下级数为 2,间接下级数为 1 ,合计下级数为 3 ...以此类推。
  • a2 直接下级为 3,间接下级为 0,合计下级数 3。

最后的数据结构是这样的:

$result = array(
                'a' => array(
                'direct_num' => 2,
                'indirect_num' => 6,
                'count_num' => 8,
                'a1' => array(
                    'direct_num' => 2,
                    'indirect_num' => 1,
                    'count_num' => 3,
                    'a1_1' => array(
                        'direct_num' => 1,
                        'indirect_num' => 0,
                        'count_num' => 1,
                        array(
                            'direct_num' => 0,
                            'indirect_num' => 0,
                            'count_num' => 0,
                            'a1_1_1',
                        )
                    ),
                    'a1_2' => array()
                ),
                'a2' => array(
                    'direct_num' => 3,
                    'indirect_num' => 0,
                    'count_num' => 3,
                    array('a2_1'),//省略
                    array('a2_2'),//省略
                    array('a2_3')//省略
                )
            ),
            'b' => array()//...n+1
        );

提示为 递归

php
《L01 基础入门》
我们将带你从零开发一个项目并部署到线上,本课程教授 Web 开发中专业、实用的技能,如 Git 工作流、Laravel Mix 前端工作流等。
《L02 从零构建论坛系统》
以构建论坛项目 LaraBBS 为线索,展开对 Laravel 框架的全面学习。应用程序架构思路贴近 Laravel 框架的设计哲学。
讨论数量: 4
巴啦啦

@altwei 是的,深度不确定,我也试了引用,技术菜了没做出来。

5年前 评论

@仰望 我感觉你的原数据是错的,我改了下


$array = array(
    'a' => array(
        'a1' => array(
            'a1_1' => array(
                'a1_1_1' => array(),
            ),
            'a1_2' => array(),
        ),
        'a2' => array(
            'a2_1' => array(),
            'a2_2' => array(),
            'a2_3' => array(),
        )
    ),
    'b' => array(),//...n+1
);
//print_r($array);

function fuck($data = array(), &$indirect_num = 0)
{
    foreach ($data as $key => $item) {
        if (is_array($item) && !empty($item)) {

            $item = fuck($item, $indirect_num);

            $indirect_num += $item['_direct_num'];
        }
        $data[$key] = $item;
    }
    //直接下级
    $data['_direct_num'] = $direct_num = count($data);
    //间接下级
    $data['_indirect_num'] = $indirect_num;
    //所有下级
    $data['_count_num'] = $direct_num + $indirect_num;
    //排序
    ksort($data);
    return $data;
}
print_r(fuck($array));
5年前 评论

@仰望 最后结果


Array
(
    [_count_num] => 10
    [_direct_num] => 2
    [_indirect_num] => 8
    [a] => Array
        (
            [_count_num] => 8
            [_direct_num] => 2
            [_indirect_num] => 6
            [a1] => Array
                (
                    [_count_num] => 3
                    [_direct_num] => 2
                    [_indirect_num] => 1
                    [a1_1] => Array
                        (
                            [_count_num] => 1
                            [_direct_num] => 1
                            [_indirect_num] => 0
                            [a1_1_1] => Array
                                (
                                )

                        )

                    [a1_2] => Array
                        (
                        )

                )

            [a2] => Array
                (
                    [_count_num] => 6
                    [_direct_num] => 3
                    [_indirect_num] => 3
                    [a2_1] => Array
                        (
                        )

                    [a2_2] => Array
                        (
                        )

                    [a2_3] => Array
                        (
                        )

                )

        )

    [b] => Array
        (
        )

)

5年前 评论

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!