Leetcode 213 打家劫舍 II

题意理解

        你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组,计算你 在不触动警报装置的情况下 ,今晚能够偷窃到的最高金额。

        

        假设从A点开始偷,若小偷偷了A,则根据规则,不能偷E

        若小偷没有投A,则可以偷E

        A B C D E的循环将其进行分情况讨论:

        (1)不考虑首位   BCD

        (2)不考虑尾  ABCD

        (3)不考虑头 BCDE

        可以发现题目的完整情况其实时2+3的综合,第一种情况在2,3里面都包含了

        所以我们分两种情况考虑,初次之外,该问题还是一个简单的打家劫舍问题。

解题思路

1.解题

 public int rob(int[] nums) {if (nums.length==0) return 0;if(nums.length==1) return nums[0];if(nums.length==2) return Math.max(nums[0],nums[1]);int[] dp_start=new int[nums.length-1];int[] dp_end=new int[nums.length-1];Arrays.fill(dp_start,0);Arrays.fill(dp_end,0);dp_start[0]=nums[0];dp_start[1]=Math.max(nums[0],nums[1]);dp_end[0]=nums[1];dp_end[1]=Math.max(nums[1],nums[2]);for(int i=2;i<nums.length-1;i++){dp_start[i]=Math.max(dp_start[i-1],dp_start[i-2]+nums[i]);dp_end[i]=Math.max(dp_end[i-1],dp_end[i-2]+nums[i+1]);}return Math.max(dp_start[nums.length-2],dp_end[nums.length-2]);}

2.分析

时间复杂度:O(n)

空间复杂度:O(2n)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/254875.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

three.js 向量方向(归一化.normalize)

效果&#xff1a; <template><div><el-container><el-main><div class"box-card-left"><div id"threejs" style"border: 1px solid red"></div><div><p><el-button type"primary…

Web后端开发:事务与AOP

事务管理 在学习数据库时&#xff0c;讲到&#xff1a;事务是一组操作的集合&#xff0c;它是一个不可分割的工作单位。事务会把所有的操作作为一个整体&#xff0c;一起向数据库提交或者是撤销操作请求&#xff0c;要么同时成功&#xff0c;要么同时失败。 事务的操作主要有三…

传输频宽是啥?对网速影响有多大?

频宽&#xff0c;即WIFI频道宽度&#xff0c;又称为WIFI信道宽度&#xff0c;是WiFi Channel width的缩写。从科学的定义来说&#xff0c;Wi-Fi频道宽度&#xff0c;是指Wi-Fi无线信号在频谱上所占用的带宽大小。它决定了Wi-Fi网络的数据传输速率和稳定性&#xff0c;一般有20M…

Flink Checkpoint过程

Checkpoint 使用了 Chandy-Lamport 算法 流程 1. 正常流式处理&#xff08;尚未Checkpoint&#xff09; 如下图&#xff0c;Topic 有两个分区&#xff0c;并行度也为 2&#xff0c;根据奇偶数 我们假设任务从 Kafka 的某个 Topic 中读取数据&#xff0c;该Topic 有 2 个 Pa…

SpringCloud-搭建Nacos服务中心

Nacos 是一个开源的动态服务发现、配置管理和服务管理平台。它支持多种服务发现协议&#xff0c;包括基于 DNS 和 HTTP 的服务发现。Nacos 提供了强大的配置管理和服务发现功能&#xff0c;使得在微服务架构中轻松实现服务注册、发现和配置管理成为可能。在本篇博客中&#xff…

“极简壁纸“爬虫JS逆向·实战

文章目录 声明目标分析确定目标目标检索 代码补全完整代码 爬虫逻辑完整代码 运行结果 声明 本教程只用于交流学习&#xff0c;不可用于商业用途&#xff0c;不可对目标网站进行破坏性请求&#xff0c;请遵守相关法律法规。 目标分析 确定目标 获取图片下载链接 目标检索…

Excel+VBA处理高斯光束

文章目录 1 图片导入与裁剪2 获取图片数据3 数据拟合 1 图片导入与裁剪 插入图片没什么好说的&#xff0c;新建Excel&#xff0c;【插入】->【图片】。 由于图像比较大&#xff0c;所以要对数据进行截取&#xff0c;选中图片之后&#xff0c;点击选项卡右端的【图片格式】…

排序算法---归并排序

原创不易&#xff0c;转载请注明出处。欢迎点赞收藏~ 归并排序是一种常见的排序算法&#xff0c;它采用了分治的思想。它将一个待排序的数组递归地分成两个子数组&#xff0c;分别对两个子数组进行排序&#xff0c;然后将排好序的子数组合并成一个有序数组。 具体的归并排序过…

MQTT 服务器(emqx)搭建及使用

推荐阅读&#xff1a; MQTT 服务器(emqx)搭建及使用 - 哔哩哔哩 (bilibili.com) 一、EMQX 服务器搭建 1、下载EMQX https://www.emqx.com/zh/try?productbroker 官方中文手册&#xff1a; EMQX Docs 2、安装使用 1、该软件为绿色免安装版本&#xff0c;解压缩后即安装完…

【精选】java继承进阶,子类继承父类(内存图、内存分析工具)

&#x1f36c; 博主介绍&#x1f468;‍&#x1f393; 博主介绍&#xff1a;大家好&#xff0c;我是 hacker-routing &#xff0c;很高兴认识大家~ ✨主攻领域&#xff1a;【渗透领域】【应急响应】 【python】 【VulnHub靶场复现】【面试分析】 &#x1f389;点赞➕评论➕收藏…

hexo 博客搭建以及踩雷总结

搭建时的坑 文章置顶 安装一下这个依赖 npm install hexo-generator-topindex --save然后再文章的上面设置 top: number&#xff0c;数字越大&#xff0c;权重越大&#xff0c;也就是越靠顶部 hexo 每次推送 nginx 都访问不到 宝塔自带的 nginx 的 config 里默认的角色是 …

详细关于如何解决mfc140.dll丢失的步骤,有效修复mfc140.dll文件丢失的问题。

mfc140.dll文件是Microsoft Visual Studio 2015程序集之一&#xff0c;它包含用于支持多种功能的代码和库。当这个mfc140.dll文件丢失时&#xff0c;可能会导致相关程序运行出错甚至无法运行。很多用户可能会遇到mfc140.dll丢失的问题&#xff0c;但是这并不是不可解决的困难。…

【微机原理与单片机接口技术】MCS-51单片机的引脚功能介绍

前言 MCS-51是指由美国Intel公司生产的一系列单片机的总称。MCS-51系列单片机型号有很多&#xff0c;按功能分位基本型和增强型两大类&#xff0c;分别称为8051系列单片机和8052系列单片机&#xff0c;两者以芯片型号中的末位数字区分&#xff0c;1为基本型&#xff0c;2为增强…

[职场] 如何通过运营面试_1 #笔记#媒体#经验分享

如何通过运营面试 盈利是公司的事情&#xff0c;而用户就是你运营的事情。你需要彻底建立一个庞大而有效的用户群&#xff0c;这样才能让你们的公司想盈利就盈利&#xff0c;想战略就战略&#xff0c;想融资就融资。 一般从事运营的人有着强大的自信心&#xff0c;后台数据分析…

PlantUML绘制UML图教程

UML&#xff08;Unified Modeling Language&#xff09;是一种通用的建模语言&#xff0c;广泛用于软件开发中对系统进行可视化建模。PlantUML是一款强大的工具&#xff0c;通过简单的文本描述&#xff0c;能够生成UML图&#xff0c;包括类图、时序图、用例图等。PlantUML是一款…

C++ 贪心 区间问题 最大不相交区间数

给定 N 个闭区间 [ai,bi] &#xff0c;请你在数轴上选择若干区间&#xff0c;使得选中的区间之间互不相交&#xff08;包括端点&#xff09;。 输出可选取区间的最大数量。 输入格式 第一行包含整数 N &#xff0c;表示区间数。 接下来 N 行&#xff0c;每行包含两个整数 ai…

Transformer的PyTorch实现之若干问题探讨(二)

在《Transformer的PyTorch实现之若干问题探讨&#xff08;一&#xff09;》中探讨了Transformer的训练整体流程&#xff0c;本文进一步探讨Transformer训练过程中teacher forcing的实现原理。 1.Transformer中decoder的流程 在论文《Attention is all you need》中&#xff0…

阿里云游戏服务器多少钱一个月?

阿里云游戏服务器租用价格表&#xff1a;4核16G服务器26元1个月、146元半年&#xff0c;游戏专业服务器8核32G配置90元一个月、271元3个月&#xff0c;阿里云服务器网aliyunfuwuqi.com分享阿里云游戏专用服务器详细配置和精准报价&#xff1a; 阿里云游戏服务器租用价格表 阿…

【QT+QGIS跨平台编译】之三十一:【FreeXL+Qt跨平台编译】(一套代码、一套框架,跨平台编译)

文章目录 一、FreeXL介绍二、文件下载三、文件分析四、pro文件五、编译实践一、FreeXL介绍 【FreeXL跨平台编译】:Windows环境下编译成果(支撑QGIS跨平台编译,以及二次研发) 【FreeXL跨平台编译】:Linux环境下编译成果(支撑QGIS跨平台编译,以及二次研发) 【FreeXL跨平台…

Linux基础-配置网络

Linux配置网络的方式 1.图形界面 右上角-wired-配置 点加号-新建网络配置文件2.NetworkManager工具 2.1用图形终端nmtui 1.新建网络配置文件add 1.指定网络设备的类型Ethernet 2.配置网络配置文件的名称&#xff0c;名称可以有空格 3.配置网络配置文件对应的物理网络设备的…