当前位置:网站首页>337. 打家劫舍 III
337. 打家劫舍 III
2022-08-09 03:54:00 【ZNineSun】
打卡!!!每日一题
今天给大家带来一道经典的动态规划题目:打家劫舍系列。
题目描述:337. 打家劫舍 III
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为 root 。
除了 root 之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ,房屋将自动报警。
给定二叉树的 root 。返回 在不触动警报的情况下 ,小偷能够盗取的最高金额 。
示例:
这道题,我们首先要找到一个突破口,如果我们从根节点来出发,那么到底要不要偷根节点,我们无从判断,因为其受制于子节点,所以我们需要找一个不受制于任何一个结点的结点来下手,很明显,叶子节点最适合不过了,因为从叶子开始,其后继结点为空。
同时我们用一个数组来保存每一个结点的盗窃情况[select,notSelect],即偷和不偷对应的金额。
如果想先遍历叶子节点,在遍历根节点,很明显后序遍历在合适不过了。
对于每个节点来说,都有两种情况:偷和不偷,我们只需要每次取最大值即可。
int[]left=dfs(root.left);
int[]right=dfs(root.right);
对于我们遍历到的结点,也是如此,也是偷和不偷两种可能
- 偷的话,那么对应的子节点只有不偷一种可能性,所以是l[1],r[1]
- 不偷的话,对于其子节点就没有限制了,可以偷也可以不偷,我们只需要做好判断,每个都确保是最大值即可。
int select = root.val + l[1] + r[1];//偷
int noSelect = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);//不偷
从上面这个过程我们也很容易看出,为何要采用后序遍历,因为根节点的状态完全依赖于其子节点。
完整代码如下:
public class 打家劫舍III_337 {
public int rob(TreeNode root) {
int[] money = dfs(root);
return Math.max(money[0], money[1]);
}
public int[] dfs(TreeNode root) {
if (root == null) {
return new int[]{
0, 0};
}
int[] l = dfs(root.left);
int[] r = dfs(root.right);
int select = root.val + l[1] + r[1];
int noSelect = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);
return new int[]{
select, noSelect};
}
}
边栏推荐
猜你喜欢
Error detected while processing /home/test/.vim/plugin/visualmark.vim
【Redis底层解析】字典类型
Mysql表打不开
别了,IE浏览器
服务端修改Cookie——跨域cookie发送机——通信加密——异或加密
理性预测,未来音视频开发前景将是这般光景
Embedded system driver advanced [2] - platform bus driver development _ basic framework
【Redis底层解析】跳跃表
leetcode 5705. 判断国际象棋棋盘中一个格子的颜色
月报总结|Moonbeam 7月份大事一览
随机推荐
机器人工程师入门知识框架(思维导图)
松柏集(浮窗思)
Win11一键重装系统后如何使用自带的故障检测修复功能
Session、cookie、token有什么区别?
月报总结|Moonbeam 7月份大事一览
旭日图更好地呈现数据的层次结构,细致划分各项数据
技术分享 | 使用 cURL 发送请求
5. Index optimization practice
Mysql表打不开
宝塔实测-在线药店商城源码带WAP版
『HarmonyOS』Page与AbilitySlice的生命周期
VS2019 compiles boost_1_79, generates 32-bit and 64-bit static libraries
rk3399 PCIe rc设备枚举之设备资源识别分析
33 基本统计知识——单项非参数检验
盘点检索任务中的损失函数
【21 基础纹理(二、凹凸映射的理论)】
06 Dynamic memory
VsCode如何使用国内镜像下载
了解CV和RoboMaster视觉组(五)滤波器、观测器和预测方法
手把手教你实现buffer(三)——接口及自动扩容