Leetcode day4:打家劫舍III_hit1180300517的博客-程序员秘密

技术标签: 算法  java  Leetcode刷题  leetcode  动态规划  

原题:

在上次打劫完一条街道之后和一圈房屋后,小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为“根”。 除了“根”之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫,房屋将自动报警。

计算在不触动警报的情况下,小偷一晚能够盗取的最高金额。
(话说这个小偷这么聪明为什么不去当程序员)
示例 1:
在这里插入图片描述
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.
示例 2:
在这里插入图片描述
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.
这里的TreeNode:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int val) { this.val = val;
 *  	}
 *  }
 * }
 */

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/house-robber-iii

思路和代码:

先分享一个错误思路,虽然是错误的,但是对层序遍历还是一个很好的方法,也即计算出奇数和偶数层分别的和再求最大值。
大概的思路就是利用队列进行层序遍历,然后再利用curLevel和nextLevel分别记录当前和下一层的节点数。
当当前的层有节点出队列时,curLevel–,当有下一层节点入队列时,nextLevel++。当curLevel==0时,将nextLevel赋给curLevel,nextLevel置0。
顺带说一句,curLevel初始值为1(因为第一层已经确定有根节点),nextLevel初始值为0。

层序遍历代码(与题意不符):
 public int rob(TreeNode root) {
    
	        int odd = 0;
	        int even = 0;
	        int loft = 0;
	        int curLevel = 1;
	        int nextLevel = 0;
	        TreeNode now = root;
	        Queue<TreeNode> q = new LinkedList<TreeNode>();
	        q.offer(now);
	        if(now==null)return 0;
	        while(!q.isEmpty()){
    
	        	now = q.poll();
	        	curLevel--;
	        	
	        	if(loft%2==0) {
    
	        		even += now.val;
	        	}
	        	else{
    
	        		odd += now.val;
	        	}
	        	
	        	if(now.left!=null) {
    
	        		q.offer(now.left);
	        		nextLevel++;
	        	}
	        	if(now.right!=null) {
    
        			q.offer(now.right);
        			nextLevel++;
        		}
	        	if(curLevel==0) {
    
	        		curLevel = nextLevel;
	        		nextLevel = 0;
	        		loft++;
	        	}
	        }
	
	        return Math.max(odd,even);
	    }

为什么说与题意不符呢,因为当出现:
在这里插入图片描述
这样的情况时,9可以是:4+5,也可以是:5+3+1(第三层的3和第一个1)所以并不一定是简单的隔层相加。应该用递归和动态规划来做。

简单递归思路:

很简单的代码,就像白话一样,不解释了,直接上代码。

简单递归代码:
class Solution {
    
   	   public int rob(TreeNode root) {
    
         if(root == null)return 0;
         if(root.left == null&&root.right == null){
    
             return root.val;
         }
         int left = 0,right = 0,valleft = 0,valright = 0;
         left = rob(root.left);
         right = rob(root.right);
         if(root.left!=null) {
    
        	 valleft = rob(root.left.left) + rob(root.left.right);
         }
         else valleft = 0;
         if(root.right!=null) {
    
        	 valright = rob(root.right.left) + rob(root.right.right);
         }
         else valright = 0;
         return Math.max(root.val+valleft+valright,left+right);
    }
}
动态规划思路:

优化子结构和子问题的重复性就不证了,一目了然。简单来说就是用一个Map把算过的值存储起来,需要的时候直接从map里取就可以了。

动态规划代码:
public class Solution {
    
	 public int rob(TreeNode root) {
    
		 Map<TreeNode,Integer> m = new HashMap<>();
		 return new_rob(root,m);
    }
	 int new_rob(TreeNode root,Map<TreeNode,Integer> m) {
    
		
	        int left = 0,right = 0,valleft = 0,valright = 0,result = 0;
	        if(root == null)return 0;
	        if(root.left == null&&root.right == null) {
    
	        	return root.val;
	        }
	        if(m.containsKey(root)) {
    
	        	return m.get(root);
	        }
	       
	     
	        right = new_rob(root.right,m);
	        left = new_rob(root.left,m);
	        
	      if(root.right!=null) {
    
	    		 valright = new_rob(root.right.left,m) + new_rob(root.right.right,m);
	      	}
	      else valright = 0;
	      if(root.left!=null) {
    
	    		 valleft = new_rob(root.left.left,m) + new_rob(root.left.right,m);
	      	}
	      else valleft = 0;
	      result = Math.max(root.val+valleft+valright,left+right);
	      m.put(root, result);
	      return result;
	 }

}

其实这个方法还有优化的空间,就是因为这两种解法都用到了孙子节点,即使是在有记忆化的情况下还是会有损耗,所以这就是优化的突破口。

优化思路:

(这一部分是借鉴大佬的)
换一种办法来定义此问题
每个节点可选择偷或者不偷两种状态,根据题目意思,相连节点不能一起偷
当前节点选择偷时,那么两个孩子节点就不能选择偷了
当前节点选择不偷时,两个孩子节点只需要拿最多的钱出来就行(两个孩子节点偷不偷没关系)
我们使用一个大小为 2 的数组来表示 int[] res = new int[2] 0 代表不偷,1 代表偷。
所以计算公式就是:
root[0] = Math.max(rob(root.left)[0], rob(root.left)[1]) + Math.max(rob(root.right)[0], rob(root.right)[1])
root[1] = rob(root.left)[0] + rob(root.right)[0] + root.val;
这样就可以避开计算算子节点了。
附代码:

public int rob(TreeNode root) {
    
    int[] result = robInternal(root);
    return Math.max(result[0], result[1]);
}

public int[] robInternal(TreeNode root) {
    
    if (root == null) return new int[2];
    int[] result = new int[2];

    int[] left = robInternal(root.left);
    int[] right = robInternal(root.right);

    result[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
    result[1] = left[0] + right[0] + root.val;

    return result;
}

作者:reals
链接:https://leetcode-cn.com/problems/house-robber-iii/solution/san-chong-fang-fa-jie-jue-shu-xing-dong-tai-gui-hu/
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_43464400/article/details/107859653

智能推荐

opencv、VINS-mono在Ubuntu 20.04上安装过程中遇到的问题总结_乘凉~的博客-程序员秘密

因为需要在Ubuntu 20.04上安装运行港科大的VINS-mono,所以必须先安装opencv 3.3.1、Eigen xxx 以及ceres xxx,现记录安装过程中遇到的问题。此贴专门用来记录安装过程中遇到的问题及解决方法,至于opencv、Eigen、ceres以及VINS-mono的安装过程请参考另一篇博客:链接:1、编译opencv遇到的问题错误1:宏未定义错误描述:In file included from /home/acl/111/opencv-3.3.1/modules/vid

TCP/IP学习笔记-UDP协议_Jingo_Cat的博客-程序员秘密

写在前面:仅供学习使用UDP的简介 UDP(User Datagram Protocol,用户数据报协议),提供面向无连接的不可靠传输服务。属于OSI参考模型中的传输层协议。UDP的正式规范是IETF RFC768。UDP在IP报文的协议号是17。 UDP协议不提供拥塞控制、流量控制、差错纠正机制。 UDP的特征 不可靠、无连接、不分片、速度快、实时性 不可靠 通俗点讲就是不靠谱,数据包在传输过程中丢失的话是不会重传的。 无连接 通俗点讲就是一个无协

安装微型计算机(pc机),微型计算机安装调试与维修_摸鱼肥宅的博客-程序员秘密

微型计算机安装调试与维修出版时间:2010年09月定  价:34.00I S B N :9787533746377所属分类: 考试&amp;nbsp考试&gt;计算机考试&amp;nbsp标  签:其他考试计算机考试《微型计算机安装调试与维修》根据本职业的工作特点,以掌握实用操作技能和能力培养为根本出发点,围绕相应的鉴定标准和考试大纲编写而成。全书分为两篇:上篇为基础知识,共9...

程序员代码面试指南刷题--第八章.转圈打印矩阵_一年而已的博客-程序员秘密

题目描述给定一个整型矩阵matrix,请按照顺时针转圈的方式打印它。输入描述:输入包含多行,第一行两个整数n和m,代表矩阵的行数和列数,接下来n行,每行m个整数,代表矩阵matrix。输出描述:输出包含一行,n*m个整数,代表顺时针转圈输出的矩阵matrix。示例1输入4 41 2 3 45 6 7 89 10 11 1213 14 15 16输出1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10解法一:设置两个夹角import java.i

开发心得_shenqi67的博客-程序员秘密

开发过程需求分析:做什么、为什么、合入版本、涉及软硬件、交付时间点、周边影响、风险识别等,分析完输出设计文档。用例表单:分析完成后要输出用例表单,考虑各种场景,用例表单未完成不可写代码。需求澄清:开发SE、测试SE、开发MDE、开发人员必须到场。开发人员就设计文档针对每个修改点和SE对齐,并提供开发的用例表单;测试人员提供测试用例表单。需求澄清完成后开发方案和测试方案应该达成一致。方案确定

基于依存句法分析的开放式中文实体关系抽取_CopperDong的博客-程序员秘密_开放式实体关系抽取

 这一段时间一直在做知识图谱,卡在实体关系抽取这里几个月了,在github上面看到有人使用卷积神经网络训练模型进行抽取,自己也尝试了一下,但是一直苦于没有像样数据去训练,而标注训练集又太费时间了,我不太愿意干体力活。所以采用了一个低档次的方法,基于依存句法分析的实体关系抽取,记录一下心得,方便日后忘记可以再找回来。    本方法参考了github上面的项目和一篇论文,在文章末尾给出,使用的分词...

随便推点

window.URL.createObjectURL 的使用_baidu_38558076的博客-程序员秘密_createobjecturl

window.URL.createObjectURL    可以用于在浏览器上预览本地图片或者视频预览视频代码&amp;lt;!DOCTYPE html&amp;gt;&amp;lt;html&amp;gt;&amp;lt;head&amp;gt; &amp;lt;title&amp;gt;&amp;lt;/title&amp;gt;&amp;lt;/head&amp;gt;&amp;lt;body&amp;gt;&amp;lt;script type=&quot;text/javascript&quot;

keil5程序Bulid后出现Error: L6405E: No .ANY selector matches(没有任何选择器匹配)的解决方法_Demon dai的博客-程序员秘密

一、 在程序编码过程中,不小心删除了一些全局变量的东西。导致不知道为何出现这种情况。二、选择C/C++,将Execute-only Code的打勾去掉(只执行代码)三、效果图:

个人博客作业Week2_didangheng5472的博客-程序员秘密

一、是否需要有代码规范这些规范都是官僚制度下产生的浪费大家的编程时间、影响人们开发效率, 浪费时间的东西.我反驳这个观点,这些规范是成千上万的程序员在开发程序中总结出来的代码规范,他有助于我们的开发,也方便他人阅读我们的代码。即使在开发的过程中编码的速度会比你自己的规范要慢,但是从调试以及团队开发来看,这些规范能够大大提高程序的调试以及维护的效率,而且更加适合团队开发。我是个...

java调用kotlin的内联函数_Kotlin内联函数_weixin_39842617的博客-程序员秘密

上一章学了下高阶函数,我们可以用Lambda表达式很好的使用高阶函数,现在来看看高阶函数的原理,要知道Kotlin文件最终都是被编译成Java字节码的,但是Java中并没有高阶函数这个概念,其实Kotlin的编译器会将这些高阶函数的语法转换成Java支持的那种,比如上次我们写的计算两个数的和和差的函数:fun main() {val result = calculate(1, 2) { num1,...

[转载]深度学习应用到图像超分辨率重建1_vbskj的博客-程序员秘密

超分辨率技术(Super-Resolution)是指从观测到的低分辨率图像重建出相应的高分辨率图像,在监控设备、卫星图像和医学影像等领域都有重要的应用价值。SR可分为两类:从多张低分辨率图像重建出高分辨率图像和从单张低分辨率图像重建出高分辨率图像。基于深度学习的SR,主要是基于单张低分辨率的重建方法,即Single Image Super-Resolution (SISR)。--------...

tinyxml的使用以及示例_aa838260772的博客-程序员秘密

1.下载xml源代码:github上面 clone地址:https://github.com/aughey/tinyxml/2.下来以后自己make一下主要的就几个头文件和源文件3.测试案例4.编译成静态库: ar rv libxml.a  *.o5. 测试案例运行: g++ -o test test.o -L./ -lxml6.问题:对于main程序,先编译成目标文件,最

推荐文章

热门文章

相关标签