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

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)

相关文章:

Leetcode 213 打家劫舍 II

题意理解&#xff1a; 你是一个专业的小偷&#xff0c;计划偷窃沿街的房屋&#xff0c;每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 &#xff0c;这意味着第一个房屋和最后一个房屋是紧挨着的。同时&#xff0c;相邻的房屋装有相互连通的防盗系统&#xff0c;如果…...

【C语言】三子棋游戏实现代码

目录 1.三子棋代码功能介绍 2.三子棋游戏实现步骤 ①打印菜单栏 ②判断是否进入三子棋游戏 ③三子棋游戏基本函数实现 &#xff08;1&#xff09;清空&#xff08;初始化&#xff09;棋盘函数实现 &#xff08;2&#xff09;打印棋盘函数实现 &#xff08;3&#xff0…...

docker常用10条容器操作命令

Docker 中一些常用的容器操作命令&#xff0c;我们可以根据需要使用这些命令来管理和操作 Docker 容器。我们这次以Hell-world这个镜像为例来说明&#xff1a; 1. docker pull hello-world #拉取hell-world镜像 2. docker images # 查看本地拉取的镜像 或者可以用 docker im…...

《MySQL 简易速速上手小册》第2章:数据库设计最佳实践(2024 最新版)

文章目录 2.1 规划高效的数据库架构2.1.1 基础知识2.1.2 重点案例&#xff1a;在线电商平台2.1.3 拓展案例 1&#xff1a;博客系统2.1.4 拓展案例 2&#xff1a;库存管理系统 2.2 数据类型和表设计2.2.1 基础知识2.2.2 重点案例&#xff1a;个人健康记录应用2.2.3 拓展案例 1&a…...

利用YOLOv8 pose estimation 进行 人的 头部等马赛克

文章大纲 马赛克几种OpenCV 实现马赛克的方法高斯模糊pose estimation 定位并模糊:三角形的外接圆与膨胀系数实现实现代码实现效果参考文献与学习路径之前写过一个文章记录,怎么对人进行目标检测后打码,但是人脸识别有个问题是,很多人的背影,或者侧面无法识别出来人脸,那…...

【Python 千题 —— 基础篇】查找年龄

Python 千题持续更新中 …… 脑图地址 👉:⭐https://twilight-fanyi.gitee.io/mind-map/Python千题.html⭐ 题目描述 题目描述 班级中有 Tom、Alan、Bob、Candy、Sandy 五个人,他们组成字典 {Tom: 23, Alan: 24, Bob: 21, Candy: 22, Sandy: 21},字典的键是姓名,字典的…...

前后端通讯:前端调用后端接口的五种方式,优劣势和场景

Hi&#xff0c;我是贝格前端工场&#xff0c;专注前端开发8年了&#xff0c;前端始终绕不开的一个话题就是如何和后端交换数据&#xff08;通讯&#xff09;&#xff0c;本文先从最基础的通讯方式讲起。 一、什么是前后端通讯 前后端通讯&#xff08;Frontend-Backend Commun…...

Mysql大表添加字段失败解决方案

背景 最近遇到一个问题&#xff0c;需要在user用户表千万级别数据中添加两个字段&#xff0c;发现老是加不上去&#xff0c;一直卡死。表数据量不仅大&#xff0c;而且是一个热点表&#xff0c;访问频率特别高&#xff0c;而且该表的访问是在一个大事务中。加字段的时候一直在…...

(52)只出现一次的数字III

文章目录 每日一言题目解题思路代码结语 每日一言 十年磨一剑&#xff0c;风雨未曾阻挡;愿你乘风破浪&#xff0c;不负韶华时光。 题目 题目链接&#xff1a;只出现一次的数字 给你一个整数数组 nums&#xff0c;其中恰好有两个元素只出现一次&#xff0c;其余所有元素均出现…...

Linux增删ip

Linux手动增删IP by: 铁乐猫 日期&#xff1a;2022.03.17 这里主要是记录手动临时添加和删除ip。 ifconfig方式 例&#xff0c;添加&#xff1a; ifconfig eth0:1 192.168.0.101/24移除 ifconfig eth0:1 downip addr方式 添加 ip addr add 192.168.0.102/24 dev eth0 …...

【计算机网络】时延,丢包,吞吐量(分组交换网络

时延 结点处理时延(nodal processing delay&#xff09; dproc 排队时延&#xff08;queuing delay&#xff09; dqueue 传输时延&#xff08;transmission delay&#xff09; dtrans 路由器将分组推出所需要的时间&#xff0c;是分组长度和链路传输速率的函数 传播时…...

张楠辞任抖音集团CEO;东方甄选将开服饰号;小红书新增“附近”一级入口;华为分红770亿元

今日精选 • 张楠辞任抖音集团CEO&#xff0c;未来将聚焦剪映发展• 东方甄选将开服饰号 主打自营服饰• 小红书新增“附近”一级入口• 华为分红770亿元 大厂人事变动 • 上村健一出任中国U-16国家男子足球队主教练 投融资与企业动态 • 阿里大模型「通义千问」推出春节新…...

ES监控方法以及核心指标

文章目录 1. 监控指标采集1.1 部署elasticsearch_exporter1.2 prometheus采集elasticsearch_exporter的暴露指标1.3 promethues配置告警规则或者配置grafana大盘 2. 核心告警指标2.1 es核心指标2.2 es容量模型建议 3. 参考文章 探讨es的监控数据采集方式以及需要关注的核心指标…...

无人机应用场景和发展趋势,无人机技术的未来发展趋势分析

随着科技的不断发展&#xff0c;无人机技术也逐渐走进了人们的生活和工作中。无人机被广泛应用于很多领域&#xff0c;例如遥感、民用、军事等等。本文将围绕无人机技术的应用场景和发展趋势&#xff0c;从多角度展开分析。 无人机技术的应用场景 无人机在遥感方面的应用&…...

JavaGuide

JavaGuide&#xff08;Java学习&面试指南&#xff09; | JavaGuide JavaGuide 是一个面向 Java 开发者的知识整合平台&#xff0c;它提供了 Java 相关的学习资源、面试题、开发工具、框架和库等内容。JavaGuide 的目标是帮助 Java 开发者更好地学习和应用 Java 技术。 Ja…...

IDEA创建SpringBoot+Mybatis-Plus项目

IDEA创建SpringBootMybatis-Plus项目 一、配置Maven apache-maven-3.6.3的下载与安装&#xff08;详细教程&#xff09; 二、创建SpringBoot项目 在菜单栏选择File->new->project->Spring Initializr&#xff0c;然后修改Server URL为start.aliyun.com&#xff0c…...

第9章 SpringBoot综合项目实战——个人博客系统

学习目标 了解博客系统的系统功能和文件组织结构 熟悉博客系统数据库相关表及字段的设计 熟悉系统环境搭建的步骤及相关配置 掌握前后台管理模块功能的实现 掌握用户登录,定时邮件发送功能的实现 通过前面章节的学习,读者应该已经掌握了SpringBoot框架的基本知识,并学会了与…...

怎么理解 Redis 事务

背景 在面试中经常会被问到&#xff0c;redis支持事务吗&#xff1f;事务是怎么实现的&#xff1f;事务会回滚吗&#xff1f;又是一键三连&#xff0c;我下面分析下&#xff0c;看看能不能吊打面试官 什么是Redis事务 事务是一个单独的隔离操作&#xff1a;事务中的所有命令…...

react中的diff算法

diff算法 对于React团队发现在日常开发中对于更新组件的频率&#xff0c;会比新增和删除的频率更高&#xff0c;所以在diff算法里&#xff0c;判断更新的优先级会更高。对于Vue2的diff算法使用了双指针&#xff0c;React的diff算法没有使用双指针&#xff0c;是因为更新的jsx对…...

【医学大模型 尘肺病】PneumoLLM:少样本大模型诊断尘肺病新方法

PneumoLLM&#xff1a;少样本大模型诊断尘肺病新方法 提出背景PneumoLLM 框架效果 提出背景 论文&#xff1a;https://arxiv.org/pdf/2312.03490.pdf 代码&#xff1a;https://github.com/CodeMonsterPHD/PneumoLLM/tree/main 历史问题及其背景&#xff1a; 数据稀缺性问题&a…...

如何5分钟构建专业级黑苹果EFI?OpCore Simplify让复杂配置一键搞定

如何5分钟构建专业级黑苹果EFI&#xff1f;OpCore Simplify让复杂配置一键搞定 【免费下载链接】OpCore-Simplify A tool designed to simplify the creation of OpenCore EFI 项目地址: https://gitcode.com/GitHub_Trending/op/OpCore-Simplify 副标题&#xff1a;告别…...

微信小程序身份证检测实战:从createVKSession版本兼容到真机调试全解析

1. 微信小程序身份证检测功能开发概述 最近在开发一个需要身份证识别功能的小程序时&#xff0c;遇到了一个让人头疼的问题&#xff1a;在开发者工具中运行正常&#xff0c;但真机调试时却报错"createVKSession:fail The current device does not support version v1&quo…...

VScode 高效开发 Springboot 应用的完整指南

1. 环境准备与项目创建 第一次用VScode开发Springboot项目时&#xff0c;我对着空白编辑器发呆了半小时。后来发现只要装对插件&#xff0c;效率能翻倍。先打开VScode的扩展商店&#xff0c;这三个插件是必装的&#xff1a; Java Extension Pack&#xff1a;包含语言支持、调…...

OpenClaw硬件监控:nanobot定时报告系统资源使用情况

OpenClaw硬件监控&#xff1a;nanobot定时报告系统资源使用情况 1. 为什么需要自动化硬件监控 去年夏天&#xff0c;我的开发机因为内存泄漏问题突然宕机&#xff0c;导致一个重要的线上演示被迫推迟。当时我就意识到&#xff0c;手动检查系统资源的方式既不及时也不可靠。直…...

告别SIFT/ORB!用LoFTR+Transformer搞定低纹理场景的图片匹配(附Python实战代码)

低纹理场景图像匹配实战&#xff1a;LoFTR与Transformer的革新应用 在计算机视觉领域&#xff0c;图像特征匹配一直是三维重建、视觉定位等任务的基础环节。传统方法如SIFT、ORB依赖于特征检测器提取关键点&#xff0c;但在低纹理、重复图案或运动模糊场景中表现往往不尽如人意…...

# 发散创新:边缘容器中的轻量级服务部署实战与优化策略在云计算向边缘计算演进的浪潮中,**边缘容器技术**正成

发散创新&#xff1a;边缘容器中的轻量级服务部署实战与优化策略 在云计算向边缘计算演进的浪潮中&#xff0c;边缘容器技术正成为构建低延迟、高可用应用的核心基础设施。相比传统云端Kubernetes集群&#xff0c;边缘容器更强调资源受限环境下的高效调度、快速启动和故障自愈能…...

WSABuilds系统调用:Windows与Android内核交互机制解析

WSABuilds系统调用&#xff1a;Windows与Android内核交互机制解析 【免费下载链接】WSABuilds Run Windows Subsystem For Android on your Windows 10 and Windows 11 PC using prebuilt binaries with Google Play Store (MindTheGapps) and/or Magisk or KernelSU (root sol…...

告别手动修改!用Env文件管理器一键配置Allegro SKILL加载路径(支持16.6/17.4)

告别手动修改&#xff01;用Env文件管理器一键配置Allegro SKILL加载路径&#xff08;支持16.6/17.4&#xff09; 在PCB设计领域&#xff0c;Allegro作为行业标杆工具&#xff0c;其强大的可扩展性离不开SKILL脚本的支持。然而&#xff0c;随着项目复杂度提升&#xff0c;SKILL…...

深入OpenBMC构建系统:Yocto项目与BitBake实战解析(以Romulus平台为例)

深入OpenBMC构建系统&#xff1a;Yocto项目与BitBake实战解析&#xff08;以Romulus平台为例&#xff09; 在服务器硬件管理领域&#xff0c;OpenBMC作为开源基板管理控制器固件堆栈&#xff0c;正逐渐成为企业级设备的标准配置。不同于简单的固件烧录&#xff0c;OpenBMC的构建…...

Step3-VL-10B部署案例:金融APP界面自动化测试,覆盖85%人工回归用例

Step3-VL-10B部署案例&#xff1a;金融APP界面自动化测试&#xff0c;覆盖85%人工回归用例 1. 项目背景与痛点 金融APP的每一次版本更新&#xff0c;都伴随着一场紧张的回归测试。测试团队需要反复验证登录、转账、理财购买、账单查询等几十个核心功能&#xff0c;确保新代码…...