建设博物馆网站/百度客服中心人工电话
本章汇总一下leetcode中的打家劫舍问题,使用经典动态规划算法求解。
1、梦开始的地方——打家劫舍(★)
本题关键点就是不能在相邻房屋偷东西。
采用常规动态规划做法:
- 根据题意设定dp数组,dp[i]的含义为:前i个房屋内,能偷的最高金额。
- 需要初始化dp[0]=0,dp[1]=nums[0]。
- 遍历dp数组,对应两种情况:偷或者不偷。 递推公式为:
-
dp[i] = Math.max(dp[i-1] , dp[i-2]+nums[i-1]);
-
-
最后返回dp数组最后一个数。
java代码如下:
class Solution {public int rob(int[] nums) {if(nums.length == 1) return nums[0];int[] dp = new int[nums.length+1]; //dp[i]:前i个房屋内,能偷的最高金额。dp[1] = nums[0];for(int i=2; i<=nums.length; i++){dp[i] = Math.max(dp[i-1] , dp[i-2]+nums[i-1]); //分别对应偷或者不偷}return dp[nums.length];}
}
2、打家劫舍II
本题是上一题的进阶版,区别在于收尾两个房屋也是相邻的,不能同时偷。 此时无非就两种情况:
- 不偷首房屋。
- 不偷尾房屋。
分别设两个dp数组对应以上两种情况即可,思路还是类似上一题。
java代码如下:
class Solution {public int rob(int[] nums) {if(nums.length == 1) return nums[0];int[] dp1 = new int[nums.length]; //不偷首房屋int[] dp2 = new int[nums.length]; //不偷尾房屋dp1[1] = nums[1];dp2[1] = nums[0];for(int i=2; i<nums.length; i++){dp1[i] = Math.max(dp1[i-1] , dp1[i-2]+nums[i]);dp2[i] = Math.max(dp2[i-1] , dp2[i-2]+nums[i-1]);}return dp1[nums.length-1] > dp2[nums.length-1] ? dp1[nums.length-1] : dp2[nums.length-1];}
}
3、打家劫舍III(★)
本题是从数组型dp转化为树形dp,由于父节点的状态需要从孩子节点的状态推出来,因此需要使用后序遍历。
首先需要定义一个递归函数dfs,参数为当前节点,返回值为长度为2的数组,即dp数组,dp[0]代表选当场节点,dp[1]代表不选当前节点。 如下:
int[] dfs(TreeNode node)
接下来确定终止条件:
if(node == null) return new int[] {0,0};
使用后序遍历递归遍历左右子树:
//递归左右子树
int[] left = dfs(node.left);
int[] right = dfs(node.right);
确定单层递归逻辑:
//分别对应偷与不偷的情况:
int rob = node.val + left[1] + right[1];
int no_rob = Math.max(left[0],left[1]) + Math.max(right[0],right[1]);
java代码如下:
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {public int rob(TreeNode root) {int[] ans = dfs(root);return Math.max(ans[0],ans[1]);}private int[] dfs(TreeNode node){if(node == null) return new int[] {0,0};//递归左右子树int[] left = dfs(node.left);int[] right = dfs(node.right);int rob = node.val + left[1] + right[1];int no_rob = Math.max(left[0],left[1]) + Math.max(right[0],right[1]);return new int[] {rob,no_rob};}
}
相关文章:

leetcode——打家劫舍问题汇总
本章汇总一下leetcode中的打家劫舍问题,使用经典动态规划算法求解。 1、梦开始的地方——打家劫舍(★) 本题关键点就是不能在相邻房屋偷东西。 采用常规动态规划做法: 根据题意设定dp数组,dp[i]的含义为:…...

Java经典框架之Spring MVC
Spring MVC Java 是第一大编程语言和开发平台。它有助于企业降低成本、缩短开发周期、推动创新以及改善应用服务。如今全球有数百万开发人员运行着超过 51 亿个 Java 虚拟机,Java 仍是企业和开发人员的首选开发平台。 课程内容的介绍 1. Spring MVC 入门案例 2. 基…...

Golang make vs new
文章目录 1.简介2.区别3.new 可以初始化 slice,map 和 channel 吗?4.make 可以初始化其他类型吗?5.小结参考文献 1.简介 在 Go 语言中,make 和 new 是两个用于创建对象的内建函数,但它们有着不同的用途和适用范围。 …...

Arthas
概述 Arthas(阿尔萨斯) 能为你做什么? Arthas 是Alibaba开源的Java诊断工具,深受开发者喜爱。 当你遇到以下类似问题而束手无策时,Arthas可以帮助你解决: 这个类从哪个 jar 包加载的?为什么会…...

IP代理科普| 共享IP还是独享IP?两者的区别与优势
通俗地讲,共享IP就像乘坐公共汽车一样,您可以到达目的地,但将与其他乘客共享旅程,座位很可能是没有的。独享IP就像坐出租车一样,您可以更快到达目的地,由于车上只有您一个人,座位是您一个人专用…...

龙芯loongarch64服务器编译安装tensorflow-io-gcs-filesystem
前言 安装TensorFlow的时候,会出现有些包找不到的情况,直接使用pip命令也无法安装,比如tensorflow-io-gcs-filesystem,安装的时候就会报错: 这个包需要自行编译,官方介绍有限,这里我讲解下 编译 准备 拉取源码:https://github.com/tensorflow/io.git 文章中…...

开源持续测试平台Linux MeterSphere本地部署与远程访问
文章目录 前言1. 安装MeterSphere2. 本地访问MeterSphere3. 安装 cpolar内网穿透软件4. 配置MeterSphere公网访问地址5. 公网远程访问MeterSphere6. 固定MeterSphere公网地址 前言 MeterSphere 是一站式开源持续测试平台, 涵盖测试跟踪、接口测试、UI 测试和性能测试等功能&am…...

Kubernetes(K8S)快速入门
概述 在本门课程中,我们将会学习K8S一些非常重要和核心概念,已经操作这些核心概念对应组件的相关命令和方式。比如Deploy部署,Pod容器,调度器,Service服务,Node集群节点,Helm包管理器等等。 在…...

将遗留系统分解为微服务:第 2 部分
在当今不断发展的技术环境中,从整体架构向微服务的转变对于许多企业来说都是一项战略举措。这在报销计算系统领域尤其重要。正如我在上一篇文章第 1 部分应用 Strangler 模式将遗留系统分解为微服务-CSDN博客中提到的,让我们探讨如何有效管理这种转变。 …...

RK3588平台开发系列讲解(AI 篇)RKNN-Toolkit2 模型的加载转换
文章目录 一、Caffe 模型加载接口二、TensorFlow 模型加载接口三、TensorFlowLite 模型加载接口四、ONNX 模型加载五、DarkNet 模型加载接口六、PyTorch 模型加载接口沉淀、分享、成长,让自己和他人都能有所收获!😄 📢 RKNN-Toolkit2 目前支持 Caffe、TensorFlow、Tensor…...

CNVD原创漏洞审核和处理流程
一、CNVD原创漏洞审核归档和发布主流程 (一)审核和归档流程 审核流程分为一级、二级、三级审核,其中一级审核主要对提交的漏洞信息完整性进行审核,漏洞符合可验证(通用型漏洞有验证代码信息或多个互联网实例、事件型…...

【java爬虫】基于springboot+jdbcTemplate+sqlite+OkHttp获取个股的详细数据
注:本文所用技术栈为:springbootjdbcTemplatesqliteOkHttp 前面的文章我们获取过沪深300指数的成分股所属行业以及权重数据,本文我们来获取个股的详细数据。 我们的数据源是某狐财经,接口的详细信息在下面的文章中,本…...

智能优化算法应用:基于人工兔算法3D无线传感器网络(WSN)覆盖优化 - 附代码
智能优化算法应用:基于人工兔算法3D无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用:基于人工兔算法3D无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.人工兔算法4.实验参数设定5.算法结果6.参考文…...

【ubuntu 22.04】安装vscode并配置正常访问应用商店
注意:要去vscode官网下载deb安装包,在软件商店下载的版本不支持输入中文 在ubuntu下用火狐浏览器无法访问vscode官网,此时可以手动进行DNS解析,打开DNS在线查询工具,解析以下主机地址(复制最后一个IP地址&a…...

K8s出现问题时,如何排查解决!
K8s问题的排查 1. POD启动异常、部分节点无法启动pod2. 审视集群状态3. 追踪事件日志4. 聚焦Pod状态5. 检查网络连通性6. 审视存储配置7. 研究容器日志8. K8S集群网络通信9. 问题:Service 是否通过 DNS 工作?10. 总结1、POD启动异常、部分节点无法启动p…...

2015年第四届数学建模国际赛小美赛B题南极洲的平均温度解题全过程文档及程序
2015年第四届数学建模国际赛小美赛 B题 南极洲的平均温度 原题再现: 地表平均温度是反映气候变化和全球变暖的重要指标。然而,在以前的估计中,在如何界定土地平均数方面存在一些方法上的差异。为简单起见,我们只考虑南极洲。请建…...

npm常见错误
三个方面 1. npm ERR! code ELIFECYCLE npm ERR! errno 1 npm ERR! code ELIFECYCLE npm ERR! errno 1 npm ERR! phantomjs-prebuilt2.1.15 install: node install.js npm ERR! Exit status 1 npm ERR! npm ERR! Failed at the phantomjs-prebuilt2.1.15 install script. np…...

JVM入门到入土-Java虚拟机寄存器指令集与栈指令集
JVM入门到入土-Java虚拟机寄存器指令集与栈指令集 HotSpot虚拟机中的任何操作都需要入栈和出栈的步骤。 由于跨平台性的设计,Java的指令都是根据栈来设计的。不同平台CPU架构不同,所以不能设计为基于寄存器的。优点是跨平台,指令集小&#x…...

MS2244模拟开关可Pin to Pin兼容NJM2244
MS2244 是一款集成的视频开关,实现三输入视频或音频信号的三选一。可Pin to Pin兼容NJM2244。 芯片集成了 75Ω驱动电路,可以直接驱动电视监控器。芯片工作电压 5V~12V,带宽 10MHz,抗串扰 70dB (4.43MHz)。另外芯片还集…...

PostgreSQL 可观测性最佳实践
简介 软件简述 PostgreSQL 是一种开源的关系型数据库管理系统 (RDBMS),它提供了许多可观测性选项,以确保数据库的稳定性和可靠性。 可观测性 可观测性(Observability)是指对数据库状态和操作进行监控和记录,以便在…...

51单片机相关寄存器
前言 单片机复习的时候对应寄存器的记忆感觉很混乱,这里进行一下整理,后面的单词是我用来辅助记忆的,可能并不是表示原本的含义。 P3口的第二功能 0RXD 串行数据输入口 1TXD串行数据输出口2INT0外部中断0输入3INT1外部中断1输入4T0定时器0外部计数输入…...

二叉树进阶题目(超详解)
文章目录 前言根据二叉树创建字符串题目分析写代码 二叉树的层序遍历题目分析 写代码二叉树的层序遍历II题目分析写代码 二叉树的最近公共祖先题目分析写代码时间复杂度 优化思路优化的代码 二叉搜索树与双向链表题目分析写代码 从前序与中序遍历序列构造二叉树题目分析写代码从…...

W6100-EVB-Pico评估版介绍
文章目录 1 简介2 硬件资源2.1 硬件规格2.2 引脚定义2.3 工作条件 3 参考资料3.1 Datasheet3.2 原理图3.3 尺寸图(尺寸:mm)3.4 参考例程 4 硬件协议栈优势 1 简介 W6100-EVB-Pico是一款基于树莓派RP2040和全硬件TCP/IP协议栈以太网芯片W6100的…...

嵌入式面试准备
题目都摘于网上 嵌入式系统中经常要用到无限循环,如何用C编写死循环 while(1){}或者for(;😉 内存分区 代码区,全局区(全局变量,静态变量,以及常量),栈区,堆区 const关键…...

在Linux Docker中部署RStudio Server,实现高效远程访问
🌈个人主页:聆风吟 🔥系列专栏:网络奇遇记、Cpolar杂谈 🔖少年有梦不应止于心动,更要付诸行动。 文章目录 📋前言一. 安装RStudio Server二. 本地访问三. Linux 安装cpolar四. 配置RStudio serv…...

EternalBlue【永恒之蓝】漏洞详解(复现、演示、远程、后门、入侵、防御)内容丰富-深入剖析漏洞原理-漏洞成因-以及报错解决方法-值得收藏!
漏洞背景: 1.何为永恒之蓝? 永恒之蓝(Eternal Blue)爆发于2017年4月14日晚,是一种利用Windows系统的SMB协议漏洞来获取系统的最高权限,以此来控制被入侵的计算机。甚至于2017年5月12日, 不法分子…...

长链接与在线文件
什么是在线文件 常见的聊天工具,比如。。。微信,你可以发送一个文件给对端,即使对端不在线,这个文件也可以暂存在服务器上面,直到接收端上线消费或者超时,这个叫离线文件。与之对应的,在线文件要…...

Python内置数据类型等入门语(句)法
内置数据类型 数字(Number)关键字: int 、float、complex字符串(String)关键字:单引号,双引号 三引号都可以表示,8 种内置类型都可转为字符串类型列表(List) 关键符号 […...

ElasticSearch之RestClient笔记
1. ElasticSearch 1.1 倒排索引 1.2 ElasticSearch和Mysql对比 1.3 RestClient操作 导入依赖 <dependency><groupId>org.elasticsearch.client</groupId><artifactId>elasticsearch-rest-high-level-client</artifactId><version>7.15.…...

饥荒Mod 开发(二二):显示物品信息
饥荒Mod 开发(二一):超大便携背包,超大物品栏,永久保鲜 饥荒Mod 开发(二三):显示物品栏详细信息 饥荒中的物品没有详细信息,基本上只有一个名字,所以很多物品的功能都不知道,比如浆果吃了也不知…...