【PHP】面试题精讲—无限级分类/无限分类的递归算法和非递归算法-带源码建议收藏
【摘要】
日拱一卒无有尽，功不唐捐终入海 💋
经典问题-无限级分类
无限级分类，也被称为无限分类，如下图所示，他是一个非常经典的问题。
最经典的应用场景就是后台系统的菜单，包括但是不仅限于
省...
日拱一卒无有尽，功不唐捐终入海 💋
经典问题-无限级分类
无限级分类，也被称为无限分类，如下图所示，他是一个非常经典的问题。
最经典的应用场景就是后台系统的菜单，包括但是不仅限于
- 省市区直辖市下拉菜单
- 信息系统后台管理的菜单管理
- 实际工作业务中的组织层级管理
那么无限级分类为什么经典呢？原因有三：
- 了解面试者是否会用递归算法
- 观察面试者处理实际问题的解决思路
- 根据实际代码看面试者对语言(PHP)的熟练程度
接下来，让我带你一层一层的分析问题，从中通过深度思考，学到更多的东西，这样不仅对于面试，并且对于以后的工作学习也是有帮助的。
问题描述
给出如下数组结构，输出返回层级菜单。
输入
$arr = [
['id'=>1,'pid'=>0,'name'=>'内容管理'],
['id'=>2,'pid'=>1,'name'=>'内容管理1'],
['id'=>3,'pid'=>1,'name'=>'内容管理2'],
['id'=>4,'pid'=>3,'name'=>'内容管理22'],
['id'=>5,'pid'=>0,'name'=>'附件管理'],
['id'=>6,'pid'=>5,'name'=>'内容管理'],
['id'=>7,'pid'=>6,'name'=>'内容管理1'],
['id'=>8,'pid'=>7,'name'=>'模块1'],
['id'=>9,'pid'=>8,'name'=>'模块11'],
['id'=>10,'pid'=>9,'name'=>'模块111'],
];
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
输出结果为按层级的数组
问题分析-为什么他是一个高频问题？
原因是通过这个问题的考察，他能够看到你解决问题的思路。
可以通过递归解决，通过递归的写法，面试官就能看出来你对递归条件的判断，什么时候跳出递归的界限是否清晰，函数调用是否合理。
解决问题
1.递归方法
递归，就是在运行的过程中调用自己。
递归可以说是分而治之的思想的体现，将一个问题分解成一个小问题，并且在判断范围内调用自己来解决一个问题，直到这个问题不再适用于自己的解决范围。
用最快的方式理解递归，只需要记住这几点
- 递归的界限在哪里结束
- 递归的调用在哪里执行
- 维护的结果是如何传递的
public function makeTree($array, $pid =0, $level = 0) //传递结果
{
static $list = [];
foreach ($array as $key => $value) {
if ($value['pid'] == $pid) { //递归的界限
$value['level'] = $level;
$value['name'] = str_repeat('-',$level).$value['name'];
$list[] = $value;
unset($array[$key]);
$this->makeTree($array, $value['id'], $level + 1); //递归的调用
}
}
return $list;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
输出结果是一个按层级排列的一维数组，name已经按层级增加了前缀，这样的数组可以直接给下拉菜单使用。
array (
0 =>
array (
'id' => 1,
'pid' => 0,
'name' => '内容管理',
'level' => 0,
),
1 =>
array (
'id' => 2,
'pid' => 1,
'name' => '-内容管理1',
'level' => 1,
),
2 =>
array (
'id' => 3,
'pid' => 2,
'name' => '--内容管理2',
'level' => 2,
),
3 =>
array (
'id' => 7,
'pid' => 3,
'name' => '---内容管理22',
'level' => 3,
),
4 =>
array (
'id' => 4,
'pid' => 7,
'name' => '----模块1',
'level' => 4,
),
5 =>
array (
'id' => 8,
'pid' => 0,
'name' => '附件管理',
'level' => 0,
),
6 =>
array (
'id' => 5,
'pid' => 8,
'name' => '-模块11',
'level' => 1,
),
7 =>
array (
'id' => 9,
'pid' => 5,
'name' => '--内容管理',
'level' => 2,
),
8 =>
array (
'id' => 6,
'pid' => 9,
'name' => '---模块111',
'level' => 3,
),
9 =>
array (
'id' => 10,
'pid' => 6,
'name' => '----内容管理1',
'level' => 4,
),
)
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
那么这个非常经典的递归方法，我们如何分析其中的问题呢？
这个调用的结束点在，找不到下一级为止，即当前元素的pid和下一次循环的pid都不一致。
通过增加变量times可以发现，10个元素下函数调用次数为11次。
通过前后执行函数memory_get_usage(),得出内存使用: 5.367188 kb
2.非递归方法
递归方法的缺点在于比较消耗资源，那么不用递归也是能解决这个问题的。
先给出源码
function makeTree($arr)
{
$pid = $arr[0]['pid'];
$arr_assert = [];
$arr_new = [];
foreach ($arr as $value) {
$arr_new[$value['id']] = $value;
if (!isset($arr_assert[$value['pid']])) {
$arr_assert[$value['pid']]['start'] = 0;
$arr_assert[$value['pid']]['end'] = 0;
}
$arr_assert[$value['pid']][] = $value['id'];
++$arr_assert[$value['pid']]['end'];
}
$result = [];
$count = count($arr_new);
$offset = 0;
while ($offset < $count) {
if (isset($arr_assert[$pid]) && $arr_assert[$pid]['start'] < $arr_assert[$pid]['end']) {
$id = $arr_assert[$pid]['start'];
++$arr_assert[$pid]['start'];
$pid = $arr_assert[$pid][$id];
$result[] = $arr_new[$pid];
++$offset;
} else
$pid = $arr_new[$pid]['pid'];
}
return $result;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
这一步得出的结构是树形的结构
array (
0 =>
array (
'id' => 1,
'pid' => 0,
'name' => '内容管理',
),
1 =>
array (
'id' => 2,
'pid' => 1,
'name' => '内容管理1',
),
2 =>
array (
'id' => 3,
'pid' => 2,
'name' => '内容管理2',
),
3 =>
array (
'id' => 7,
'pid' => 3,
'name' => '内容管理22',
),
4 =>
array (
'id' => 4,
'pid' => 7,
'name' => '模块1',
),
5 =>
array (
'id' => 8,
'pid' => 0,
'name' => '附件管理',
),
6 =>
array (
'id' => 5,
'pid' => 8,
'name' => '模块11',
),
7 =>
array (
'id' => 9,
'pid' => 5,
'name' => '内容管理',
),
8 =>
array (
'id' => 6,
'pid' => 9,
'name' => '模块111',
),
9 =>
array (
'id' => 10,
'pid' => 6,
'name' => '内容管理1',
),
)
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
总结
对于无限级分类这个问题，由于在实际项目应用非常广泛，所以这是一个概率非常大会出现的面试题。
文章来源: coderfix.blog.csdn.net，作者：小雨青年，版权归原作者所有，如需转载，请联系作者。
原文链接：coderfix.blog.csdn.net/article/details/118381607
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）