当前位置: 澳门新濠3559 > 编程 > 正文

其中跟节点为0=&gt,id 为上级节点的

时间:2019-12-08 22:39来源:编程
结果造成了如下结果 4. 结果分析 到这里,对于如何为失明者设计一个产品的问题,我们已经总结为一系列需求。 以上这类产品经理面试题,从题目逐渐分析直至得出结论的思维过程,

结果造成了如下结果

图片 1

4. 结果分析

到这里,对于如何为失明者设计一个产品的问题,我们已经总结为一系列需求。

以上这类产品经理面试题,从题目逐渐分析直至得出结论的思维过程,也就是本题的考察重点所在。

回过头看上述思路,如果将原问题视为树的根节点,具体的功能点视为树的最底层节点,我们的每一次发散思维都在产生更多节点、每一次向本质分析都在增加树的深度,当我们找出当前并列的很多分析角度(也就是树的当层所有节点)之后,都会从第一个节点向下分析(深度优先搜索),直至其不符合我们的想法,便将其剔除(剪枝),一个节点及其所有子节点处理完后再分析同层次的下一个节点及其子节点。

在常规的广度优先搜索的分析方式中,每一层次都在无限发散而产生大量可能性、重要性不同的分析角度都需要一并发散,产生大量无用功(比如我们甚至要分析指针闹钟拨指针时的盲文怎么设计等等),直至可能性众多庞杂使我们无法继续向下层分析。

相比较而言,我们可以发现,深度优先搜索+剪枝这样一边发散、一边精简可能性、并将结论反馈到同层下一个分析角度的分析问题的思维方法,能避免无用功、帮助收拢发散的思路、维持分析问题逻辑的一致性。

PHP 函数实现如下:

由于本人脑子笨,仔细想了之后,发现算法的漏洞:当遍历第三级节点(学期)的时候,如果不属于其上级节点,依旧会进行遍历其子节点(课时),会重复对学期节点的子节点进行添加,造成子节点的重复

3. 2. 第二点,产品的本质,分析产品定位的分类。

闹钟可以分为:

  • 家用闹钟、随身闹钟
  • 电子闹钟、指针闹钟
  • 实体闹钟、软件闹钟
  • 电池闹钟、充电闹钟
  • 等等
    • 失明者在外出时如果有获取时间等需求,可以借助外人的帮助;
    • 用于手机的软件闹钟对于失明者的不友好程度可能比有按键旋钮的实体闹钟更高;
    • 指针闹钟如果采用触摸指针的方式获取时间,因为反复触摸可能影响耐用性,而且指针闹钟的初衷是采用可视化反馈大部分信息,电子闹钟在应对失明者的特殊需求上更为灵活;
    • 至于还是指针闹钟至于是电池闹钟还是充电闹钟,我们可以先继续向后思考。

'.$row['name'].'

结果正常!

图片 2

3. 3. 第三点,产品应用场景,分析产品被使用的场景分类。

闹钟可以用于:

  • 叫醒
  • 提醒办事(吃药等)
  • 倒计时
  • 获取时间
  • 等等
    这些都是可能会用到的场景。

复制代码 代码如下:SELECT * FROM tree WHERE lft BETWEEN 2 AND 11;

所以进行了简单的修复:遍历到非其子类节点时跳过

图片 3

 

2. 什么是剪枝

树的节点有一些额外属性,在遍历树的过程中,同时判断节点的属性,并删除不符合属性要求的分支节点,称为剪枝。比如我们设置一个属性为“在广度优先遍历中的顺序”,即途中节点中的数字,我们要找出上面那颗二叉树中所有满足“广度优先顺序小于5”的节点,那么先序遍历过程为:1 -> 2 -> 4 -> 5(删) -> 3 -> 6(删),先序遍历最终结果为:1 -> 2 -> 4 -> 3。

我们要显示树,PHP 代码也可以很直观,代码如下:复制代码 代码如下:' . $row['name'] . '';// 递归调用当前函数,显示再下一级的子节点show_children($row['id'], $level + 1);}}?>

工作中遇到的小问题,进行一下反思,记录下来,希望下次避免这样的问题,也希望可以帮到一些.

 

3. 1. 第一点,产品所服务的对象,分析失明者人群具体如何分类。

失明者可以分为:

  • 先天失明和后天失明
  • 不完全失明和完全失明
  • 儿童、成人和长者
  • 等等

想到这里,我们可以和面试官尝试沟通并表达如下看法,争取获得他的认可:

    • 先天失明与后天失明的区别在于失明者是否能“脑补”出一些画面,不是主要矛盾;
    • 还尚存能看清闹钟的视力的失明者也不是我们产品服务的对象;
    • 儿童和长者在面对闹钟时与成年人并无本质区别。

因此在大部分情况下,我们面对的是完全失明的成人。

显示树和路径都没问题了,现在需要了解一下如何插入一个节点。插入新节点之前,首先要给这个节点腾出空位来,假设我们现在要在“ORACLE 9i”这个节点右边增加一个“ORACLE 10”,则腾位的 SQL 语句如下:

遍历多叉树的时候,如果遍历到非节点下的子节点,一定要及时打住!!!否则不仅增加O(),而且易造成子节点重复增加

3. 一道产品面试题:为失明者设计一个闹钟

拿到这道题之后,首先考虑四要素:

  • WHO it works for——失明者
  • WHAT it exactly is——闹钟
  • WHEN&WHERE it should be used——日常家用
  • WHY it's necessary——常规闹钟对失明者而言存在使用困难

主要依赖于一个 parent 字段,用于指向上级节点,将相邻的上下级节点连接起来,id 为自动递增自动,parent_id 为上级节点的 id。一目了然,“Java”是“Language”的子节点。

如下是自己写的小逻辑,其中跟节点为0=>所有组,之后所属关系为  培训班=>学期=>课时

图片 4

3. 4. 第四点,产品需求点,结合常规闹钟的基本功能,综述分析产品可能的潜在需求所在。

基本需求:

  • 增加盲文说明及按键文字
  • 获取现在的时间
  • 提醒将来的时间
  • 开关机
  • 是否低电量
  • 关闭当前闹钟
    • 盲文对于失明者的使用是基本需求;
    • 采用语音报时满足失明者获取时间的需求;
    • 还有一些视觉反馈的非0即1功能,比如开关机、是否低电量、是否已设置闹钟、关闭当前闹钟等也需要设置触觉或者听觉反馈。

高级需求:

  • 倒计时

  • 整点报时

  • 闹钟重复

  • 语音备注闹钟

  • 已有闹钟播报

  • 小睡模式

  • 震动提醒

  • 无线充电

    • 失明者无法使用一些电器的倒计时功能,比如煮饭、微波炉热菜等;
    • 失明者在设置时可以语音备注“吃XX药”“做午饭”,闹钟到时提醒会一并播报语音备注;
    • 闹钟重复功能可对某一定点提醒设置重复规则,比如每天重复、每周重复等;
    • 失明者可以通过已有闹钟播报来查看当前设置的所有闹钟;
    • 闹钟提醒后,启动小睡模式推迟5分钟再次提醒;
    • 失明者因为担心闹钟吵到同居其他人等原因可设置为震动提醒;
    • 闹钟如果不采用电池供电而是充电模式,在低电提醒响起后,失明者将闹钟放置在无线充电器周围,闹钟开始充电并发出反馈。

想要显示整个树结构,调用 show_children()。想要显示“Database”子树,则调用 show_children,因为“Database”的 id 是 2。

1. 什么是深度优先搜索算法

深度优先搜索(Depth-first Search)对应于广度优先搜索(Breadth-first Search),是一种可应用于树的遍历的算法,常见的深度优先遍历方式分为先序遍历中序遍历后序遍历
以上定义对于从未接触树这种数据结构的人而言实在是生僻难懂,所以一图胜千言。
假设有如下一颗二叉树:

一颗二叉树

假设去掉以上1至6的数字,让你数这棵树有多少节点,一般思路是从第一行开始,然后第二行,第三行,每一行都从左至右数一遍,直至最后一行。这种思路就是广度优先搜索,如果将数节点的过程排序,则我们数节点的顺序正好对应着图中的1至6的数字。
现在我们换一个思路,每个节点左下角和右下角的连线节点我们称为左子节点和右子节点,对于左子、右子和自身三者在“被我们数”的过程中的优先级顺序可以有A(3,3) = 6种,但是我们对于左右子仍然是按照先左后右,所以A(3,3) / 2 = 3种。即:

  1. 自身 > 左子 > 右子(先序遍历,此处“先”对应自身的优先级)
  2. 左子 > 自身 > 右子(中序遍历)
  3. 左子 > 右子 > 自身 (后序遍历)

对于1,遍历顺序为 1 -> 2 -> 4 -> 5 -> 3 -> 6;
对于2,遍历顺序为 4 -> 2 -> 5 -> 1 -> 3 -> 6;
对于3,遍历顺序为 4 -> 5 -> 2 -> 6 -> 3 -> 1;

从以上的三种思路中可以看出,与广度优先搜索的一层层向下访问的逻辑不同,这里每次我们都要一直沿着某一条路径访问到二叉树的最底层、直至没有左右子节点,才会返回上层再继续下一优先级的访问,这是我们称之深度优先搜索的原因。

领接表方式的优点在于容易理解,代码也比较简单明了。缺点则是递归中的 SQL 查询会导致负载变大,特别是需要处理比较大型的树状结构的时候,查询语句会随着层级的增加而增加,WEB 应用的瓶颈基本都在数据库方面,所以这是一个比较致命的缺点,直接导致树结构的扩展困难重重。

排序遍历树方式

  1. 预排序遍历树方式;

我们经常需要在关系型数据库中保存一些树状结构数据,比如分类、菜单、论坛帖子树状回复等。常用的方法有两种:

SQL 语句是简单了,但我们所希望的缩进显示却是个问题。什么时候应该显示缩进?缩进多少单位?解决这个问题,需要使用堆栈,即后进先出,每到一个节点,将其右边的数字压入堆栈中。我们知道,所有节点右边的值都比其父节点右边的值小,那么将当前节点右边的值和堆栈最上边的右边值进行比较,如果当前节点比堆栈最上边的值小,表示当前堆栈里边剩下的都是父节点了,这时可以显示缩进,堆栈的元素数量即是缩进深度。PHP 代码实现如下:复制代码 代码如下: $stack[count {array_pop;} //while 循环结束之后,堆栈里边只剩下当前节点的父节点了}// 现在可以显示缩进了echo '

调用 show_tree() 看看结果对不对 具体的 PHP 实现代码这里就不写了。

位置空出来了,开始插入新节点吧:复制代码 代码如下:INSERT INTO tree SET lft=10, rgt=11, name='ORACLE 10';

还有一个经常用到的功能是获取节点路径,即给出一个节点,返回从根节点到当前节点的路径。用函数实现如下:复制代码 代码如下:

复制代码 代码如下:UPDATE tree SET rgt=rgt+2 WHERE rgt>9;UPDATE tree SET lft=lft+2 WHERE lft>9;

获取整个树调用 show_tree(),获取“Database”子树调用show_tree。在这个函数中,我们总算不需要用到递归了,呵呵。

想要获取“MySQL 5.0”的路径,调用 get_path,4 即是这个节点的 id。

复制代码 代码如下:= '.$row['rgt'].' ORDER BY lft ASC');$path = array();while ($row = mysql_fetch_array {$path[] = $row['name'];}return $path;}?>

现在我们来聊聊第二种方式─预排序遍历树方式(即通常所说的 MPTT,Modified Preorder Tree Traversal)。此算法是在第一种方式的基础之上,给每个节点增加一个左、右数字,用于标识节点的遍历顺序,如下图所示:

接下来看看显示树/子树是多么简单,只需要一条 SQL 语句即可,比如显示“Database”子树,则需要获取到“Database”的左右数字,左为 2,右为 11,那么 SQL 语句是:

现在总结一下预排序遍历树方式的优缺点。缺点是算法比较抽象,不容易理解,增加节点的时候虽然只用了几条 SQL 语句,但可能会需要更新很多记录,从而造成阻塞。优点是树的构造,路径获取方面性能都比领接表方式好很多。也就是说,这个算法牺牲了一些写的性能来换取读的性能,在 WEB 应用中,读数据库的比例远大于写数据库的比例,所以预排序遍历树方式比领接表方式更加受欢迎,更加实用,很多应用中都能看到 MPTT 的影子,通常所用的表里都有字段 lft 和 rgt。

';// 将当前的节点压入堆栈里边,为循环后边的节点缩进显示做好准备array_push;}}?>

接下来是显示从根节点到某节点的路径,这比起领接表方式来说也简单了很多,只需要一句 SQL 就行,不用递归 比如获取“ORACLE”这个节点的路径,其左右值分别是 7 和 10,则 SQL 语句为:复制代码 代码如下:SELECT name FROM tree WHERE lft <= 7 AND rgt >= 10 ORDER BY lft ASC;

领接表方式

从根节点开始左边为 1,然后下一个节点的左边为 2,以此类推,到最低层节点之后,最低层节点的右边为其左边的数字加 1。顺着这些节点,我们可以很容易地遍历完整个树。根据上图,我们对数据表做一些改变,增加两个字段,lft 和 rgt 用于存储左右数字(由于 left 和 right 是 MySQL 的保留字,所以我们改用简写)。表中各行的内容也就变成了:

编辑:编程 本文来源:其中跟节点为0=&gt,id 为上级节点的

关键词: