注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

微软、Google等面试题

剑指Offer:名企面试官精讲典型编程题

 
 
 

日志

 
 

程序员面试题精选100题(69)-聪明的小偷[算法]  

2018-01-30 06:01:02|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
问题:当某小偷到达一个小区准备偷窃的时候,他发现这里只有一栋房子位于叫做“根”的入口,除了这个根之外的其他房子有且只有一个父房子。这个精通算法的小偷在这个小区转了一圈之后意识到这些房子构成一个二叉树,而且如果直接相连的两栋房子被盗就会自动报警请问这个小偷在小区最多能偷得多少财物而不惊动警察?

例如,在下图二叉树所示的小区里,小偷最多能够偷得价值为9的财物(被偷的房子的价值用红色字体标识)。

程序员面试题精选100题(69)-聪明的小偷[算法] - 何海涛 - 微软、Google等面试题

分析:这是LeetCode的第337题。


当这个小偷站在位于入口的根节点时,他会考虑是不是要到这栋房子里偷盗。他自然想偷得最多的财物,所以他会仔细权衡如下两个选择:


第一个选择是他偷这栋房子的东西,此时他不能去该房子的两个子节点房子偷(不能到两栋直接相连的房子里偷),但可以到它们的子节点房子(孙子节点房子)。按照这个选择他可以偷得价值为8的财物(被偷得的房子的财物价值在上图中用黑色字体标识)。


第二个选择他不到这栋房子里偷,此时他可以到该房子的两个子节点房子偷。按照这个选择他可以偷得价值为9的财物(被偷得的房子的财物价值在上图中用红色字体标识)。


因此小偷的权衡过程就是比较如下两个选项并选择较大值:(1)到当前节点偷,此时可能偷得的最大值为当前房子的财物价值加上在所有孙子节点房子可能偷得的财物价值总和;(2)略过当前的节点的房子,此时他可能偷得的最大值是到两个子节点房子可能偷得的财物价值总和。


上述过程是从位于根节点的房子开始权衡,很容易用递归函数实现。但由于位于子节点的房子可能需要重复计算多次,时间复杂度很大


我们可以换一下顺序,从位于下面的子节点开始,计算到达每个节点能够偷得的财物的最大价值,然后逐次向上计算父节点直至到达根节点。在二叉树中,先遍历叶子节点再遍历根节点,是典型的后续遍历。


在用后续遍历的顺序计算了到达左、右子节点时能够偷得的最大值之后,我们回到它们的父节点计算能够偷得的最大值。根据我们前面分析的规律,小偷还需要知道在该父节点的孙子节点上能够偷得的财物最大值才能做决定,因此从左、右子节点回到它们的父节点时,我们还要把在左、右子节点的子节点能够偷得的最大值传给它们的父节点。


上述思路的Java代码如下所示:

程序员面试题精选100题(69)-聪明的小偷[算法] - 何海涛 - 微软、Google等面试题

在上述代码的第二个rob函数(private函数)中,变量left和right分别是在节点root的左、右子节点能够偷得的最大值。变量skip-Left和skip-Right都是长度为2的数组。数组skip-Left存储在root的左子节点的左、右子节点能够偷得的最大值,而数组skip-Right存储在root的右子节点的左、右子节点能够偷得的最大值。


如果二叉树中有n个节点,上述解法的时间复杂度是O(n),空间复杂度是O(logn)。


本文转载自微信公众号青云算法扫描下面的二维码,关注“青云算法”微信公众号,学习更多高频算法面试题的解法。

程序员面试题精选100题(65)-每天的温度[算法] - 何海涛 - 微软、Google等面试题

  评论这张
 
阅读(401)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018