当前位置: 首页 > 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…...

告别单打独斗!Apipost 8协作版数据迁移保姆级教程(含团队项目处理)

Apipost 8协作版数据迁移实战&#xff1a;从个人到团队的无缝衔接 第一次打开Apipost 8协作版时&#xff0c;我盯着那个"迁入项目"按钮犹豫了整整十分钟——作为独立开发者&#xff0c;我的旧版本里积累了237个接口文档和56个测试集合&#xff0c;它们就像我精心搭建…...

Mplus实战:如何用随机截距交叉滞后模型(RI-CLPM)分析心理学纵向数据?

Mplus实战&#xff1a;随机截距交叉滞后模型&#xff08;RI-CLPM&#xff09;在心理学纵向研究中的深度应用 心理学研究中&#xff0c;我们常常需要探索变量间的动态相互作用——比如焦虑和睡眠问题如何相互影响&#xff1f;传统交叉滞后模型&#xff08;CLPM&#xff09;虽然广…...

AI驱动关键词优化的SEO未来趋势与实际应用解析

本文旨在探讨AI在搜索引擎优化&#xff08;SEO&#xff09;&#xff0c;特别是关键词优化领域的重要角色。文章分析了AI技术如何通过数据分析和用户行为洞察&#xff0c;帮助企业制定更加有效的关键词策略。AI能够实时监测市场趋势&#xff0c;识别用户意图&#xff0c;并根据这…...

CREST:如何用5分钟开启分子构象探索之旅?

CREST&#xff1a;如何用5分钟开启分子构象探索之旅&#xff1f; 【免费下载链接】crest Conformer-Rotamer Ensemble Sampling Tool based on the xtb Semiempirical Extended Tight-Binding Program Package 项目地址: https://gitcode.com/gh_mirrors/crest/crest 在…...

小米智能家居集成终极指南:5分钟快速接入HomeAssistant

小米智能家居集成终极指南&#xff1a;5分钟快速接入HomeAssistant 【免费下载链接】hass-xiaomi-miot Automatic integrate all Xiaomi devices to HomeAssistant via miot-spec, support Wi-Fi, BLE, ZigBee devices. 小米米家智能家居设备接入Hass集成 项目地址: https://…...

多代理系统架构实战:Supervisor 与 Swarm 的选型与落地策略

1. 多代理系统架构的核心价值 想象一下你正在组织一场大型会议&#xff1a;需要预订场地、安排餐饮、发送邀请函、准备会议材料。如果让一个人完成所有工作&#xff0c;要么质量难以保证&#xff0c;要么时间拖得很长。这就是多代理系统要解决的问题——通过专业分工和高效协作…...

UniApp多主题开发避坑指南:为什么SCSS+Require比Vuex方案更优雅?

UniApp多主题开发实战&#xff1a;SCSS动态加载方案深度解析与性能优化 在移动应用开发领域&#xff0c;主题切换功能已成为提升用户体验的重要环节。UniApp作为跨平台开发框架&#xff0c;如何实现高效、灵活的主题管理一直是开发者关注的焦点。本文将深入探讨基于SCSS变量与动…...

基于春联生成模型的Python爬虫数据采集与内容生成系统

基于春联生成模型的Python爬虫数据采集与内容生成系统 用技术传承文化&#xff0c;让AI助力创作 1. 项目背景与价值 春节是中国人最重要的传统节日&#xff0c;而春联则是春节文化中不可或缺的一部分。每年春节&#xff0c;家家户户都会贴上新的春联&#xff0c;表达对新年的美…...

实战复盘-Redis连接数爆满引发的生产事故与优化策略

1. 事故背景&#xff1a;一场由促销活动引发的Redis雪崩 那天凌晨三点&#xff0c;我被一阵急促的电话铃声惊醒。电话那头是值班同事焦急的声音&#xff1a;"所有商品页面都打不开了&#xff0c;订单系统也瘫痪了&#xff01;"我瞬间清醒&#xff0c;抓起电脑就开始…...

zotero-style:提升文献管理效率的3个核心方案

zotero-style&#xff1a;提升文献管理效率的3个核心方案 【免费下载链接】zotero-style zotero-style - 一个 Zotero 插件&#xff0c;提供了一系列功能来增强 Zotero 的用户体验&#xff0c;如阅读进度可视化和标签管理&#xff0c;适合研究人员和学者。 项目地址: https:/…...