一个很有意思的问题,一个社区,所有的房子构成一棵二叉树,每个房子里有一定价值的财物,这棵二叉树有一个根节点root。如果相邻的两座房子同时被进入,就会触发警报。一个小偷,最初只能访问root节点,并可以通过二叉树的边访问房子(注:访问不意味着进入),请问不触发警报的前提下他能偷到的财物的最大价值是多少?
以下面这棵二叉树为例,最多能偷走3+3+1=7的财物
3
/ \
2 3
\ \
3 1
分析:
这个问题乍一看上去可能没什么思路,但是如果是用递归,可以很优雅的解决这个问题,这需要读者对递归有比较深刻的理解。下面给出解决这个问题的java代码:
package houseRobberIII;
import java.util.HashMap;
import java.util.Map;
import common.TreeNode;
public class Solution {
//使用一个cache 缓存以每个节点为根节点的rob方法返回值,减少计算量
Map<TreeNode, Integer> cache = new HashMap<TreeNode, Integer>();
public int rob(TreeNode root) {
//如果当前节点为空 直接返回0
if(null == root){
return 0;
}
//首先查看缓存中有没有这个节点的rob方法返回值
if(null != cache.get(root)){
return cache.get(root);
}
//计算当前节点左孩子的rob方法返回值
int maxLeft = rob(root.left);
//计算当前节点右孩子的rob方法返回值
int maxRight = rob(root.right);
int maxLeftLeft = 0;
int maxLeftRight = 0;
//如果当前节点有左孩子
if(null != root.left){
//计算其左孩子的左孩子的rob值
maxLeftLeft = rob(root.left.left);
//计算其左孩子的右孩子的rob值
maxLeftRight = rob(root.left.right);
}
int maxRightLeft = 0;
int maxRightRight = 0;
//如果当前节点有右孩子
if(null != root.right){
//计算其右孩子的左孩子的rob值
maxRightLeft = rob(root.right.left);
//计算其右孩子的右孩子的rob值
maxRightRight = rob(root.right.right);
}
//不偷当前节点能偷到的财物的最大值
int notIncludeCurrentNodeMax = maxLeft + maxRight;
//偷当前节点能偷到的财物的最大值
int includeCurrentNodeMax = maxLeftLeft + maxLeftRight + maxRightLeft + maxRightRight + root.val;
//以其中的较大值作为当前节点的rob方法返回值
int res = notIncludeCurrentNodeMax > includeCurrentNodeMax ? notIncludeCurrentNodeMax : includeCurrentNodeMax;
//缓存当前节点的rob方法返回值
cache.put(root, res);
return res;
}
}
package common;
/**
* 二叉树节点类
* @author xuguanglv
*
*/
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
这个解法中比较重要的一点是使用了cache进行动态规划,使整个算法的时间复杂度为O(V+E),其中V为二叉树的节点的数量,E为二叉树的边的数量;如果不使用cache来缓存每一个节点的rob方法返回值,每次访问某个节点,都要重复计算一次rob值,最后的时间复杂度将会是指数级的,显然不可接受的。
分享到:
相关推荐
含word文档,运行结果,c++源代码。项目功能包括输入一个二维数组A,自定义...求从A[0][0]开始的互不相邻的各元素之和;当数组的行数和列数相等(m=n)时,分别求两条对角线上的数据元素之和,否则打印出m!=n的信息。
C语言程序设计-编写程序。...⑴求出这8个数据的和、最大值、最小值及平均值。 ⑵求这8个数据的正数之和、负数之和(或正数与负数的个数); ⑶求这8个数据的奇数之和、偶数之和(或奇数与偶数的个数)。
设n是一个正整数。现在要求将n分解为若干互不相同的自然数的和,且使这些自然数的乘积最大。
, xn,求这n 个数在实轴上相邻2 个数之间的最大差值。假设对任何实数的下取整函数耗时O(1),设计解最大间隙问题的线性时间算法。 编程任务:对于给定的n 个实数x1, x2,...,xn,编程计算它们的最大间隙。 Input ...
研究了最大度顶点互不相邻的高度图的全色数.得到:设图G的最大度顶点是互不相邻的,且δ(G)≥34|V(G)|,则xT(G)=Δ(G)+1。
用这个种方法可以在任意一个随机范围内抽取你所需要的互不相等的你想要的多少个数
有1、2、3、4个数字,能组成多少个互不相同且无重复数字的三位数?都是多少?
数组a中已存有互不相同的10个整数从键盘输入一个整数,找出与该值相同的数组元素下标。 (如果没找到,输出“没找到”).c
二叉树的层次遍历及宽度,哈夫曼树,将L中的整数序列循环左移p个位置,将表L中所有值为x 的元素删除,判断链表中是否存在环,删除单链表L(L中元素值各不相同)的最大值所对应的结点,并返回该值,树的孩子兄弟表示...
生成互不相同的随机数,随机数可以选择范围。
xp 多用户远程登录 互不影响, 按照说明操作,并把注册表导入即可 windows xp 多用户远程登录 互不影响 完美 简单 易操作
NULL 博文链接:https://zhelong111.iteye.com/blog/1772291
经典填字游戏:在3*3个方格的方阵中要填入数字1到N(N>=10)内的某9个数字,每个方格填一个整数,使得所有相邻两个方格内的两个整数之和为质数。试求出所有满足这个要求的各种数字填法。 //我们可以通过改变N的值来...
小程序分类页面(仿京东,左走滑动互不影响)希望多多支持
问题描述:设n是一个正整数,将n分解为若干互不相同的自然数之和,且使这些自然数的乘积最大。 本讲义提供该问题的正确算法的自然语言描述及其严格证明。
设n是一个正整数,现在要将n分解为若干个互不相同的自然数的和,且使这些数的乘积最大。
小程序使用for循环点击按钮 view+1,for循环内使用下拉框,互不影响,可单独选择。
题目:有1、2、3、4个数字,能组成多少个互不相同且无重复数字的三位数?都是多少? 程序分析:可填在百位、十位、个位的数字都是1、2、3、4。组成所有的排列后再去掉不满足条件的排列。 程序源代码: main() { ...
设有一棵二叉树,其节点值为字符型并假设各值互不相等,采用二叉链表存储表示。现输入其扩展二叉树的前序遍历序列,要求建立该二叉树,并求其节点个数。
设法生成10个互不相同的从a到z的字母,然后对这10个字母按从小到大的方式排序。输出排序前和排序后的字母序列。