当前位置: 首页 > news >正文

leetcode——打家劫舍问题汇总

        本章汇总一下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中的打家劫舍问题&#xff0c;使用经典动态规划算法求解。 1、梦开始的地方——打家劫舍&#xff08;★&#xff09; 本题关键点就是不能在相邻房屋偷东西。 采用常规动态规划做法&#xff1a; 根据题意设定dp数组&#xff0c;dp[i]的含义为&#xff1a…...

Java经典框架之Spring MVC

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

Golang make vs new

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

Arthas

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

IP代理科普| 共享IP还是独享IP?两者的区别与优势

通俗地讲&#xff0c;共享IP就像乘坐公共汽车一样&#xff0c;您可以到达目的地&#xff0c;但将与其他乘客共享旅程&#xff0c;座位很可能是没有的。独享IP就像坐出租车一样&#xff0c;您可以更快到达目的地&#xff0c;由于车上只有您一个人&#xff0c;座位是您一个人专用…...

龙芯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)快速入门

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

将遗留系统分解为微服务:第 2 部分

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

RK3588平台开发系列讲解(AI 篇)RKNN-Toolkit2 模型的加载转换

文章目录 一、Caffe 模型加载接口二、TensorFlow 模型加载接口三、TensorFlowLite 模型加载接口四、ONNX 模型加载五、DarkNet 模型加载接口六、PyTorch 模型加载接口沉淀、分享、成长,让自己和他人都能有所收获!😄 📢 RKNN-Toolkit2 目前支持 Caffe、TensorFlow、Tensor…...

CNVD原创漏洞审核和处理流程

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

【java爬虫】基于springboot+jdbcTemplate+sqlite+OkHttp获取个股的详细数据

注&#xff1a;本文所用技术栈为&#xff1a;springbootjdbcTemplatesqliteOkHttp 前面的文章我们获取过沪深300指数的成分股所属行业以及权重数据&#xff0c;本文我们来获取个股的详细数据。 我们的数据源是某狐财经&#xff0c;接口的详细信息在下面的文章中&#xff0c;本…...

智能优化算法应用:基于人工兔算法3D无线传感器网络(WSN)覆盖优化 - 附代码

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

【ubuntu 22.04】安装vscode并配置正常访问应用商店

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

K8s出现问题时,如何排查解决!

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

2015年第四届数学建模国际赛小美赛B题南极洲的平均温度解题全过程文档及程序

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

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虚拟机中的任何操作都需要入栈和出栈的步骤。 由于跨平台性的设计&#xff0c;Java的指令都是根据栈来设计的。不同平台CPU架构不同&#xff0c;所以不能设计为基于寄存器的。优点是跨平台&#xff0c;指令集小&#x…...

MS2244模拟开关可Pin to Pin兼容NJM2244

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

PostgreSQL 可观测性最佳实践

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

51单片机相关寄存器

前言 单片机复习的时候对应寄存器的记忆感觉很混乱&#xff0c;这里进行一下整理,后面的单词是我用来辅助记忆的&#xff0c;可能并不是表示原本的含义。 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 尺寸图&#xff08;尺寸&#xff1a;mm&#xff09;3.4 参考例程 4 硬件协议栈优势 1 简介 W6100-EVB-Pico是一款基于树莓派RP2040和全硬件TCP/IP协议栈以太网芯片W6100的…...

嵌入式面试准备

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

在Linux Docker中部署RStudio Server,实现高效远程访问

&#x1f308;个人主页&#xff1a;聆风吟 &#x1f525;系列专栏&#xff1a;网络奇遇记、Cpolar杂谈 &#x1f516;少年有梦不应止于心动&#xff0c;更要付诸行动。 文章目录 &#x1f4cb;前言一. 安装RStudio Server二. 本地访问三. Linux 安装cpolar四. 配置RStudio serv…...

EternalBlue【永恒之蓝】漏洞详解(复现、演示、远程、后门、入侵、防御)内容丰富-深入剖析漏洞原理-漏洞成因-以及报错解决方法-值得收藏!

漏洞背景&#xff1a; 1.何为永恒之蓝&#xff1f; 永恒之蓝&#xff08;Eternal Blue&#xff09;爆发于2017年4月14日晚&#xff0c;是一种利用Windows系统的SMB协议漏洞来获取系统的最高权限&#xff0c;以此来控制被入侵的计算机。甚至于2017年5月12日&#xff0c; 不法分子…...

长链接与在线文件

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

Python内置数据类型等入门语(句)法

内置数据类型 数字&#xff08;Number&#xff09;关键字: int 、float、complex字符串&#xff08;String&#xff09;关键字&#xff1a;单引号&#xff0c;双引号 三引号都可以表示&#xff0c;8 种内置类型都可转为字符串类型列表&#xff08;List&#xff09; 关键符号 […...

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 开发(二一)&#xff1a;超大便携背包&#xff0c;超大物品栏&#xff0c;永久保鲜 饥荒Mod 开发(二三)&#xff1a;显示物品栏详细信息 饥荒中的物品没有详细信息&#xff0c;基本上只有一个名字&#xff0c;所以很多物品的功能都不知道&#xff0c;比如浆果吃了也不知…...

Microsoft Edge使用方法和心得

Microsoft Edge使用方法和心得 大家好&#xff0c;我是豪哥&#xff0c;一名来自杭州的Java程序员&#xff0c;今天我想分享一下我对Microsoft Edge的使用方法和心得。作为一名热爱编程的程序员&#xff0c;我发现一个高效的浏览器对于我们的工作和学习至关重要。而Microsoft …...

Kafka操作指令笔记

查堆积用命令查&#xff1a; ./kafka-consumer-groups.sh --bootstrap-server {kafka集群地址} --describe --group {消费组名称}bin/kafka-consumer-groups.sh --bootstrap-server localhost:9092 --describe --all-groups #查看所有组别的积压情况可以通过grep、awk或其他文…...

WAVE SUMMIT+ 2023倒计时2天,传文心一言将曝最新进展!

传文心一言将曝最新进展&#xff01; 亮点一&#xff1a;趋势引领&#xff0c;“扛把子”文心一言将曝新进展亮点二&#xff1a;干货十足&#xff0c;硬核低门槛开发秘籍大放送亮点三&#xff1a;蓄势待发&#xff0c;大模型赋能产业正当时亮点四&#xff1a;群星闪耀&#xff…...

Crow:Middlewares 庖丁解牛5 context

Crow:Middlewares 庖丁解牛4 partial_context-CSDN博客 基于partial_context再来解释context namespace detail {template<typename... Middlewares>struct partial_context : public pop_back<Middlewares...>::template rebind<partial_context>, public…...

CentOS 7 设置网络

CentOS 7 设置网络 正常情况 ①登陆进去之后使用下面的命令修改文件 echo ONBOOTyes >> /etc/sysconfig/network-scripts/ifcfg-ens33②如果是虚拟机重启后使用如下命令进行查看IP地址 ip addr注&#xff1a;到这里如果显示有两部分&#xff0c;则代表网络设置成功&a…...

装饰器模式(Decorator)

装饰器模式(Decorator Pattern)是一种结构型设计模式,用于动态地给一个对象添加额外的职责。装饰器提供了一个灵活的替代扩展功能的方案,相比继承更加灵活。 在Java中,装饰器模式通常涉及以下几个部分: 组件(Component):定义一个对象接口,可以给这些对象动态添加职责…...

关于“Python”的核心知识点整理大全34

目录 第&#xff11;3 章 外星人 13.1 回顾项目 game_functions.py 13.2 创建第一个外星人 13.2.1 创建 Alien 类 alien.py 13.2.2 创建 Alien 实例 alien_invasion.py 13.2.3 让外星人出现在屏幕上 game_functions.py 13.3 创建一群外星人 13.3.1 确定一行可容纳…...

设计模式--抽象工厂模式

实验4&#xff1a;抽象工厂模式 本次实验属于模仿型实验&#xff0c;通过本次实验学生将掌握以下内容&#xff1a; 1、理解抽象工厂模式的动机&#xff0c;掌握该模式的结构&#xff1b; 2、能够利用抽象工厂模式解决实际问题。 [实验任务]&#xff1a;人与肤色 使用抽象…...

浅析海博深造

文章目录 深造作用 留学种类 选专业 择校 申请流程 申请方式 深造作用 1、个人能力提升&#xff08;学术专业、语言、新文化或新生活方式&#xff09; 2、更好的职业发展&#xff08;起点更高、结交新朋友或扩大社交圈&#xff09; 3、北京上海落户优惠 4、海外居留福…...

【Hive_05】企业调优1(资源配置、explain、join优化)

1、 计算资源配置1.1 Yarn资源配置1.2 MapReduce资源配置 2、 Explain查看执行计划&#xff08;重点&#xff09;2.1 Explain执行计划概述2.2 基本语法2.3 案例实操 3、分组聚合优化3.1 优化说明&#xff08;1&#xff09;map-side 聚合相关的参数 3.2 优化案例 4、join优化4.1…...

synchronized

⭐ 作者&#xff1a;小胡_不糊涂 &#x1f331; 作者主页&#xff1a;小胡_不糊涂的个人主页 &#x1f4c0; 收录专栏&#xff1a;JavaEE &#x1f496; 持续更文&#xff0c;关注博主少走弯路&#xff0c;谢谢大家支持 &#x1f496; synchronized 1. 特性1.1 互斥1.2 可重入 …...

Vue在页面上添加水印

第一步&#xff1a;在自己的项目里创建一个js文件&#xff1b;如图所示我在在watermark文件中创建了一个名为waterMark.js文件。 waterMark.js /** 水印添加方法 */ let setWatermark (str1, str2) > {let id 1.23452384164.123412415if (document.getElementById(id) …...

SQL server 数据库练习题及答案(练习2)

使用你的名字创建一个数据库 创建表&#xff1a; 数据库中有三张表&#xff0c;分别为student,course,SC&#xff08;即学生表&#xff0c;课程表&#xff0c;选课表&#xff09; 问题&#xff1a; --1.分别查询学生表和学生修课表中的全部数据。--2.查询成绩在70到80分之间…...

minicube搭建golang容器服务

引言 最近在自己电脑上搭建一个小型k8s环境&#xff0c;以学习云原生相关内容。这里我主要分为三部分记录&#xff1a; 容器及容器编排理论环境安装相关rpcx服务实战 还在调试中&#xff0c;先总结整理下&#xff0c;这里后续补充上我的github工程链接。 一、容器及容器编排理…...

图片批量处理:图片批量缩放,高效调整尺寸的技巧

在数字媒体时代&#xff0c;图片处理已是日常生活和工作中不可或缺的一部分。有时候要批量处理图片&#xff0c;如缩放图片尺寸&#xff0c;以满足不同的应用需求。现在一起来看看办公提效式具如何高效的将图片批量处理方法&#xff0c;快速、准确地批量调整图片尺寸操作。 下…...

直接插入排序【从0-1学数据结构】

文章目录 &#x1f497; 直接插入排序Java代码C代码JavaScript代码稳定性时间复杂度空间复杂度 我们先来学习 直接插入排序, 直接排序算是所有排序中最简单的了,代码也非常好实现,尽管直接插入排序很简单,但是我们依旧不可以上来就直接写代码,一定要分析之后才开始写,这样可以提…...

C++/CLI——1简介

C/CLI——1简介 如果你是.net程序员&#xff0c;不免会用到C/C写的库。对于简单的调用&#xff0c;可以直接使用DllImport来完成就可以&#xff0c;详情可参考C#调用C/C从零深入讲解。但是对于复杂的C类和对象&#xff0c;尤其是类似于OCC的大型C项目&#xff0c;DllImport可能…...

C#实现串口通讯

1、官网下载Launch Virtual Serial Port Driver Virtual Serial Port Driver - create and emulate virtual COM port&#xff0c;开个虚拟串口&#xff1a; Pair模式&#xff08;一对&#xff0c;成双成对的意思&#xff0c;就是COM1向COM2传或者COM2向COM1,好比两台机器的CO…...

NLP论文阅读记录 - 以大语言模型为参考学习总结

文章目录 前言0、论文摘要一、Introduction1.1目标问题1.2相关的尝试1.3本文贡献 二.相关工作2.1文本生成模型的训练方法2.2 基于LLM的自动评估2.3 LLM 蒸馏和基于 LLM 的数据增强 三.本文方法3.1 Summarize as Large Language Models3.1.1 前提3.1.2 大型语言模型作为参考具有…...

前端---资源路径

当我们使用img标签显示图片的时候&#xff0c;需要指定图片的资源路径&#xff0c;比如: <img src"images/logo.png">这里的src属性就是设置图片的资源路径的&#xff0c;资源路径可以分为相对路径和绝对路径。 1. 相对路径 从当前操作 html 的文档所在目录算…...