你是一个经验丰富的小偷,经过上次在街边和湖边得手后你准备挑战一次自己,你发现了一个结构如二叉树的小区,小区内每个房间都存有一定现金,你观察到除了小区入口的房间以外每个房间都有且仅有一个父房间和至多两个子房间。 问,给定一个二叉树结构的小区,如之前两次行动一样,你无法在不触动警报的情况下同时偷窃两个相邻的房间,在不触动警报的情况下最多的偷窃金额。 1.如果输入的二叉树为{2,1,2,#,2,#,1},那么形状结构如下: 小区入口的房间的值是2 ,偷窃第一层2 和第三层 2,1 是最优方案。 2.如果输入的二叉树为 {3,2,10},那么形状结构如下: 样例2:小区入口的房间的值是3 ,偷窃 第二层 2,10 是最优方案。 数据范围:二叉树节点数量满足 ,树上的值满足-笔试面试资料

这是qklbishe.com第19095 篇笔试面试资料
提供答案分析,通过本文《你是一个经验丰富的小偷,经过上次在街边和湖边得手后你准备挑战一次自己,你发现了一个结构如二叉树的小区,小区内每个房间都存有一定现金,你观察到除了小区入口的房间以外每个房间都有且仅有一个父房间和至多两个子房间。 问,给定一个二叉树结构的小区,如之前两次行动一样,你无法在不触动警报的情况下同时偷窃两个相邻的房间,在不触动警报的情况下最多的偷窃金额。
1.如果输入的二叉树为{2,1,2,#,2,#,1},那么形状结构如下:

小区入口的房间的值是2 ,偷窃第一层2 和第三层 2,1 是最优方案。

2.如果输入的二叉树为 {3,2,10},那么形状结构如下:
样例2:小区入口的房间的值是3 ,偷窃 第二层 2,10 是最优方案。

数据范围:二叉树节点数量满足 ,树上的值满足-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。

答案:

你是一个经验丰富的小偷,经过上次在街边和湖边得手后你准备挑战一次自己,你发现了一个结构如二叉树的小区,小区内每个房间都存有一定现金,你观察到除了小区入口的房间以外每个房间都有且仅有一个父房间和至多两个子房间。
问,给定一个二叉树结构的小区,如之前两次行动一样,你无法在不触动警报的情况下同时偷窃两个相邻的房间,在不触动警报的情况下最多的偷窃金额。
1.如果输入的二叉树为{2,1,2,#,2,#,1},那么形状结构如下:
你是一个经验丰富的小偷,经过上次在街边和湖边得手后你准备挑战一次自己,你发现了一个结构如二叉树的小区,小区内每个房间都存有一定现金,你观察到除了小区入口的房间以外每个房间都有且仅有一个父房间和至多两个子房间。    问,给定一个二叉树结构的小区,如之前两次行动一样,你无法在不触动警报的情况下同时偷窃两个相邻的房间,在不触动警报的情况下最多的偷窃金额。            1.如果输入的二叉树为{2,1,2,#,2,#,1},那么形状结构如下:                      小区入口的房间的值是2 ,偷窃第一层2 和第三层 2,1 是最优方案。                              2.如果输入的二叉树为 {3,2,10},那么形状结构如下:           样例2:小区入口的房间的值是3 ,偷窃 第二层 2,10 是最优方案。             数据范围:二叉树节点数量满足  ,树上的值满足
小区入口的房间的值是2 ,偷窃第一层2和第三层 2,1 是最优方案。

2.如果输入的二叉树为{3,2,10},那么形状结构如下:
你是一个经验丰富的小偷,经过上次在街边和湖边得手后你准备挑战一次自己,你发现了一个结构如二叉树的小区,小区内每个房间都存有一定现金,你观察到除了小区入口的房间以外每个房间都有且仅有一个父房间和至多两个子房间。    问,给定一个二叉树结构的小区,如之前两次行动一样,你无法在不触动警报的情况下同时偷窃两个相邻的房间,在不触动警报的情况下最多的偷窃金额。            1.如果输入的二叉树为{2,1,2,#,2,#,1},那么形状结构如下:                      小区入口的房间的值是2 ,偷窃第一层2 和第三层 2,1 是最优方案。                              2.如果输入的二叉树为 {3,2,10},那么形状结构如下:           样例2:小区入口的房间的值是3 ,偷窃 第二层 2,10 是最优方案。             数据范围:二叉树节点数量满足  ,树上的值满足
样例2:小区入口的房间的值是3 ,偷窃第二层 2,10 是最优方案。
数据范围:二叉树节点数量满足 你是一个经验丰富的小偷,经过上次在街边和湖边得手后你准备挑战一次自己,你发现了一个结构如二叉树的小区,小区内每个房间都存有一定现金,你观察到除了小区入口的房间以外每个房间都有且仅有一个父房间和至多两个子房间。    问,给定一个二叉树结构的小区,如之前两次行动一样,你无法在不触动警报的情况下同时偷窃两个相邻的房间,在不触动警报的情况下最多的偷窃金额。            1.如果输入的二叉树为{2,1,2,#,2,#,1},那么形状结构如下:                      小区入口的房间的值是2 ,偷窃第一层2 和第三层 2,1 是最优方案。                              2.如果输入的二叉树为 {3,2,10},那么形状结构如下:           样例2:小区入口的房间的值是3 ,偷窃 第二层 2,10 是最优方案。             数据范围:二叉树节点数量满足  ,树上的值满足 ,树上的值满足 你是一个经验丰富的小偷,经过上次在街边和湖边得手后你准备挑战一次自己,你发现了一个结构如二叉树的小区,小区内每个房间都存有一定现金,你观察到除了小区入口的房间以外每个房间都有且仅有一个父房间和至多两个子房间。    问,给定一个二叉树结构的小区,如之前两次行动一样,你无法在不触动警报的情况下同时偷窃两个相邻的房间,在不触动警报的情况下最多的偷窃金额。            1.如果输入的二叉树为{2,1,2,#,2,#,1},那么形状结构如下:                      小区入口的房间的值是2 ,偷窃第一层2 和第三层 2,1 是最优方案。                              2.如果输入的二叉树为 {3,2,10},那么形状结构如下:           样例2:小区入口的房间的值是3 ,偷窃 第二层 2,10 是最优方案。             数据范围:二叉树节点数量满足  ,树上的值满足
Java

你是一个经验丰富的小偷,经过上次在街边和湖边得手后你准备挑战一次自己,你发现了一个结构如二叉树的小区,小区内每个房间都存有一定现金,你观察到除了小区入口的房间以外每个房间都有且仅有一个父房间和至多两个子房间。    问,给定一个二叉树结构的小区,如之前两次行动一样,你无法在不触动警报的情况下同时偷窃两个相邻的房间,在不触动警报的情况下最多的偷窃金额。            1.如果输入的二叉树为{2,1,2,#,2,#,1},那么形状结构如下:                      小区入口的房间的值是2 ,偷窃第一层2 和第三层 2,1 是最优方案。                              2.如果输入的二叉树为 {3,2,10},那么形状结构如下:           样例2:小区入口的房间的值是3 ,偷窃 第二层 2,10 是最优方案。             数据范围:二叉树节点数量满足  ,树上的值满足 零葬

这一系列打家劫舍问题出得真好,循序渐进:线性DP->考虑环形的DP->树型DP。本题是一个非常明显的树型DP问题,对于每一个节点,在决定是否偷窃这个节点房间的财物时,我们还需要向左右孩子的房间索要两个信息:
  1. 偷窃孩子节点房间的财物时,得到的最大收益steal
  2. 不偷窃孩子节点房间的财物时,得到的最大收益noSteal

构建包含这两个信息的结构体Info,然后深度优先搜索,自底向上累加收益,当根节点得到信息体时,返回偷与不偷根节点房间的两个方案中,更大的那个收益就可以了。

import java.util.*;  /*  * public class TreeNode {  *   int val = 0;  *   TreeNode left = null;  *   TreeNode right = null;  *   public TreeNode(int val) {  *     this.val = val;  *   }  * }  */  class Info {     public int steal;     public int noSteal;     public Info(int steal, int noSteal) {         this.steal = steal;         this.noSteal = noSteal;     } }  public class Solution {     /**      * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可      *      *       * @param root TreeNode类       * @return int整型      */     public int rob (TreeNode root) {         // write code here         Info info = process(root);         return Math.max(info.steal, info.noSteal);     }          private Info process(TreeNode root) {         if(root == null){             return new Info(0, 0);         }         Info leftInfo = process(root.left);         Info rightInfo = process(root.right);         // 这一间偷,下面相邻的就不能偷         int steal = root.val + leftInfo.noSteal + rightInfo.noSteal;         // 这一间不偷,那下面相邻的可以偷可以不偷,选择收益大的方案         int noSteal = Math.max(             Math.max(leftInfo.steal + rightInfo.steal,                       leftInfo.noSteal + rightInfo.noSteal),              Math.max(leftInfo.steal + rightInfo.noSteal,                       leftInfo.noSteal + rightInfo.steal)         );         return new Info(steal, noSteal);     } }

今天 22:03:03 回复(0)

文章部分来自互联网,侵权联系删除
www.qklbishe.com

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 你是一个经验丰富的小偷,经过上次在街边和湖边得手后你准备挑战一次自己,你发现了一个结构如二叉树的小区,小区内每个房间都存有一定现金,你观察到除了小区入口的房间以外每个房间都有且仅有一个父房间和至多两个子房间。 问,给定一个二叉树结构的小区,如之前两次行动一样,你无法在不触动警报的情况下同时偷窃两个相邻的房间,在不触动警报的情况下最多的偷窃金额。 1.如果输入的二叉树为{2,1,2,#,2,#,1},那么形状结构如下: 小区入口的房间的值是2 ,偷窃第一层2 和第三层 2,1 是最优方案。 2.如果输入的二叉树为 {3,2,10},那么形状结构如下: 样例2:小区入口的房间的值是3 ,偷窃 第二层 2,10 是最优方案。 数据范围:二叉树节点数量满足 ,树上的值满足-笔试面试资料

提供最优质的资源集合

立即查看 了解详情