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

LeetCode 0213. 打家劫舍 II:动动态规划

【LetMeFly】213.打家劫舍 II:动动态规划

力扣题目链接:https://leetcode.cn/problems/house-robber-ii/

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

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

 

示例 1:

输入:nums = [2,3,2]
输出:3
解释:你不能先偷窃 1 号房屋(金额 = 2),然后偷窃 3 号房屋(金额 = 2), 因为他们是相邻的。

示例 2:

输入:nums = [1,2,3,1]
输出:4
解释:你可以先偷窃 1 号房屋(金额 = 1),然后偷窃 3 号房屋(金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。

示例 3:

输入:nums = [1,2,3]
输出:3

 

提示:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 1000

方法一:动态规划

假设不考虑“环形”,那么我们应该怎么做?

很简单,遍历数组,使用两个变量lastRoblastNot分别代表上次是否打劫了。

  • 如果上次打劫了,那么这次就不能打劫( t h i s N o t = max ⁡ ( l a s t R o b , l a s t N o t ) thisNot = \max(lastRob, lastNot) thisNot=max(lastRob,lastNot)
  • 如果上次没打劫,那么这次就打劫( t h i s R o b = l a s t N o t + n u m s [ i ] thisRob = lastNot + nums[i] thisRob=lastNot+nums[i]

然后更新lastRob和lastNot为thisRob和thisNot。

最终返回lastRob和lastNot的最大值即为答案。

加上环形这一限制,应怎么处理?

很简单,环形的唯一限制就是:打劫第一家的话不能打劫最后一家,打劫最后一家的话不能打劫第一家。

因此,在 [ 0 , l e n ( n u m s ) − 1 ] [0, len(nums) - 1] [0,len(nums)1] [ 1 , l e n ( n u m s ) ] [1, len(nums)] [1,len(nums)]中分别求一次,取最大即可。

  • 时间复杂度 O ( l e n ( n u m s ) ) O(len(nums)) O(len(nums))
  • 空间复杂度 O ( 1 ) O(1) O(1)

AC代码

C++
class Solution {
private:int realRob(vector<int>& nums, int l, int r) {int lastRob = nums[l], lastNot = 0;for (int i = l + 1; i < r; i++) {int newRob = lastNot + nums[i], newNot = max(lastRob, lastNot);lastRob = newRob, lastNot = newNot;}return max(lastRob, lastNot);}
public:int rob(vector<int>& nums) {if (nums.size() == 1) {return nums[0];}return max(realRob(nums, 0, nums.size() - 1), realRob(nums, 1, nums.size()));}
};
Python
# from typing import Listclass Solution:def realRob(self, nums: List[int], l: int, r: int) -> int:lastRob, lastNot = nums[l], 0for i in range(l + 1, r):lastRob, lastNot = lastNot + nums[i], max(lastNot, lastRob)return max(lastRob, lastNot)def rob(self, nums: List[int]) -> int:if len(nums) == 1:return nums[0]return max(self.realRob(nums, 0, len(nums) - 1), self.realRob(nums, 1, len(nums)))

同步发文于CSDN,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/132945449

相关文章:

LeetCode 0213. 打家劫舍 II:动动态规划

【LetMeFly】213.打家劫舍 II&#xff1a;动动态规划 力扣题目链接&#xff1a;https://leetcode.cn/problems/house-robber-ii/ 你是一个专业的小偷&#xff0c;计划偷窃沿街的房屋&#xff0c;每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 &#xff0c;这意味…...

VMware17 不可恢复错误mks解决方案

用的虚拟机VMware17版本&#xff0c;然后运行带HDR的unity程序&#xff0c;结果报错 网上找了很多解决方案&#xff0c;都没用。毕竟需要在不放弃虚拟机3D加速的情况下运行。 最终皇天不负有心人&#xff0c;亲测有效的方法&#xff1a; 在虚拟机名字.vmx文件里添加以下2行&a…...

【深度学习】 Python 和 NumPy 系列教程(廿五):Matplotlib详解:3、多子图和布局:subplot()函数

目录 一、前言 二、实验环境 三、Matplotlib详解 1、2d绘图类型 2、3d绘图类型 3、多子图和布局 1. subplot()函数 简单示例 一、前言 Python是一种高级编程语言&#xff0c;由Guido van Rossum于1991年创建。它以简洁、易读的语法而闻名&#xff0c;并且具有强大的功能…...

计算机网络知识补充(1)

计算机网络:是一个将分散的&#xff0c;具有独立功能的计算机系统&#xff0c;通过通信设备和线路进行连接起来&#xff0c;由功能完善的软件实现资源共享和信息共享的系统&#xff0c;计算机网络是互连的&#xff0c;自治的计算机集合 互连:通过通信链路来进行互联互通 自治:没…...

C# Onnx Yolov8 Pose 姿态识别

效果 项目 代码 using Microsoft.ML.OnnxRuntime; using Microsoft.ML.OnnxRuntime.Tensors; using OpenCvSharp; using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Linq; using System…...

7.algorithm2e中while怎么使用

algorithm2e中while怎么使用 在 algorithm2e 宏包中&#xff0c;要使用 while 循环&#xff0c;您可以使用 \While 和 \EndWhile 命令来定义循环的开始和结束。以下是如何使用 while 循环的示例&#xff1a; \documentclass{article} \usepackage[linesnumbered,boxed]{algorit…...

Flask狼书笔记 | 08_个人博客(下)

文章目录 8 个人博客8.4 初始化博客8.5 使用Flask-Login管理用户认证8.6 CSRFProtect实现CSRF保护8.7 编写博客后台小结 8 个人博客 8.4 初始化博客 1、安全存储密码 密码不要以明文的形式直接存储在数据库中&#xff0c;以防被攻击者盗取、泄露。一般的做法是&#xff0c;不…...

机器学习第十课--提升树

一.Bagging与Boosting的区别 在上一章里我们学习了一个集成模型叫作随机森林&#xff0c;而且也了解到随机森林属于Bagging的成员。本节我们重点来学习一下另外一种集成模型叫作Boosting。首先回顾一下什么叫Bagging? 比如在随机森林里&#xff0c;针对于样本数据&#xff0c;…...

react scss.modules中使用iconfont

全局引入详见全局引入scss 全局的scss文件中引入iconfont.css use "../font/iconfont.css"; 然后就可以正常使用啦...

使用Jmeter+ant进行接口自动化测试(数据驱动)

最近在做接口测试&#xff0c;因为公司有使用jmeter做接口测试的相关培训资料&#xff0c;所以还是先选择使用jmeter来批量管理接口&#xff0c;进行自动化测试。话不多说&#xff0c;进入正题&#xff1a; 1.使用csv文件保存接口测试用例&#xff0c;方便后期对接口进行维护&…...

可视化图表组件之股票数据分析应用

股市是市场经济的必然产物&#xff0c;在一个国家的金融领域之中有着举足轻重的地位。在过去&#xff0c;人们对于市场走势的把握主要依赖于经验和直觉&#xff0c;往往容易受到主观因素的影响&#xff0c;导致决策上出现偏差。如今&#xff0c;通过数据可视化呈现&#xff0c;…...

STM32 ~ GPIO不同模式之间的区别与实现原理

GPIO全称General Purpose Input Output &#xff0c;即通用输入/输出。其实GPIO的本质就是芯片的一个引脚&#xff0c;通常在ARM中所有的I/O都是通用的。不过&#xff0c;由于每个开发板上都会设计不同的外围电路&#xff0c;这就造成了GPIO的功能可能有所不同。大部分GPIO都是…...

dvwa靶场通关(十二)

第十二关&#xff1a;Stored Cross Site Scripting (XSS)&#xff08;存储型xss&#xff09; low 这一关没有任何防护&#xff0c;直接输入弹窗代码 弹窗成功 medium 先试试上面的代码看看&#xff0c;有没有什么防护 发现我们的script标签不见了&#xff0c;应该是被过滤掉…...

【shell学习】企业运维工作中常用的shell脚本

本站以分享各种运维经验和运维所需要的技能为主 《python零基础入门》&#xff1a;python零基础入门学习 《python运维脚本》&#xff1a; python运维脚本实践 《shell》&#xff1a;shell学习 《terraform》持续更新中&#xff1a;terraform_Aws学习零基础入门到最佳实战 《k8…...

对权限的理解和使用

目录 一&#xff1a;用户权限&#xff1a; ★su命令 ★sudo命令 二&#xff1a;文件权限 ★文件的类型权限 ★文件夹的权限的使用 ▲文件夹的可读权限&#xff1a; ▲文件夹的可写权限&#xff1a; ▲文件夹的可执行权限&#xff1a; ★权限的修改操作 ▲chmod命令 ★对于文件的…...

MySQL 5.7 通过数据库idb文件快速导入至另一台数据库

前言 数据库有一张表里有1000万条数据&#xff0c;通过sql导入会非常缓慢&#xff0c;如果数据库版本相同&#xff0c;迁移表可以通过复制表idb文件实现快速迁移。 一、系统环境 原服务器系统&#xff1a;centos7.4 原服务器数据库版本&#xff1a;MySQL5.7.21 新服务器系统…...

第一章 计算机网络基础

目录 1.1 网络体系结构 1.1.1 OSI/RM七层参考模型 1.1.2 OSI/RM和TCP/IP模型的比较 1.1.3 五层协议的体系结构 1.1.4 计算机1向计算机2发送数据过程 1.1.5 TCP/IP体系结构的具体实现 1.2 网络设备概述 1.2.1 互联设备与OSI的对应关系 1.2.2 集线器(HUB) 1.2.3 网桥(B…...

本地电脑搭建SFTP服务器,并实现公网访问

本地电脑搭建SFTP服务器&#xff0c;并实现公网访问 文章目录 本地电脑搭建SFTP服务器&#xff0c;并实现公网访问1. 搭建SFTP服务器1.1 下载 freesshd 服务器软件1.3 启动SFTP服务1.4 添加用户1.5 保存所有配置 2. 安装SFTP客户端FileZilla测试2.1 配置一个本地SFTP站点2.2 内…...

易基因直播预告|细菌微生物基因表达调控表观研究易基因科技

大家好&#xff0c;这里是专注表观组学十余年&#xff0c;领跑多组学科研服务的易基因。 DNA甲基化是在半个多世纪前在细菌中发现的。DNA碱基可以作为一个表观遗传调节因子——也就是说&#xff0c;它可以赋予相同的基因序列不同的和可逆的调控状态。在真核生物中&#xff0c;…...

Flask在线部署ChatGLM2大模型

1、 拉取镜像 docker pull swr.cn-central-221.ovaijisuan.com/mindformers/mindformers_dev_mindspore_2_0:mindformers_0.6.0dev_20230616_py39_372、 新建docker.sh -p 8000:8000 是宿主机映射到镜像8000端口 如果添加–ipchost --nethost 会和-p冲突 # --device用于控制…...

浅谈Vue3——父子组件传值

引言 Vue.js是一款流行的JavaScript框架&#xff0c;用于构建用户界面。它提供了一种简洁、灵活的方式来管理和渲染数据。在Vue3中&#xff0c;父子组件之间的数据传递是一个常见的需求。本文将介绍如何在Vue3中传递对象&#xff0c;并且在子组件中访问和修改父组件对象中的属…...

Wolfram语言之父:ChatGPT到底能做什么? | 阿Q送书第六期

文章目录 那么&#xff0c;ChatGPT到底在做什么&#xff1f;它为什么能做到这些&#xff1f;前方的路为ChatGPT赋予“思想”留言提前获赠书 人类语言及其背后的思维模式在结构上比我们想象的更简单、更“符合规律”。 ChatGPT大火&#xff0c;甚至已经开始改变人类的工作和思考…...

antd a-list 添加分页

会分为三部分 template <a-list item-layout"horizontal" :data-source"localData" :pagination"{...paginationProps,current:currentPage}"><a-list-item slot"renderItem" slot-scope"item"><a-list-ite…...

MySQL注入绕安全狗脚本 -- MySQLByPassForSafeDog,以及端口爆破工具 -- PortBrute配置使用

工具介绍 此Tamper仅仅适用于MySQL数据库&#xff0c;在SQLMap使用过程中添加参数–tamperMySQLByPassForSafeDog。 安装与使用 1、安装网站安全狗Apache最新版 2、启用安全狗&#xff0c;不加MySQLByPassForSafeDog绕狗Tamper: python sqlmap.py -u "http://192.168.…...

R语言绘制热图

1、初步绘图 rm(listls())#clear Global Environment setwd(D:/Desktop/0000/code-main/热图)#设置工作路径#加载R包 library (pheatmap) #读取数据 df <- read.table(file"data.txt",sep"\t",row.names 1, headerT,check.namesFALSE) #查看前3行 hea…...

jmeter线程组 bzm - Concurrency Thread Group 阶梯式压测

简介 bzm - Concurrency Thread Group 不是JMeter的官方插件&#xff0c;而是一种由Blazemeter提供的高级线程组插件&#xff0c;它提供了更灵活的并发性能测试设置。它可以在不同的时间内并发执行不同数量的线程&#xff0c;模拟不同的负载场景。 插件下载地址&#xff08;jme…...

计算即时订单比例-首单使用开窗函数row_number()

1 需求 即时订单和计划订单 订单配送中&#xff0c;如果期望配送日期和下单日期相同&#xff0c;称为即时订单&#xff0c;如果期望配送日期和下单日期不同&#xff0c;称为计划订单。 请从配送信息表&#xff08;delivery_info&#xff09;中求出每个用户的首单&#xff08;用…...

flink集群与资源@k8s源码分析-集群

0 介绍 本文是flink集群与资源@k8s源码分析系列的第二篇-集群 1 场景 下面详细分析各用例 2 启动k8s集群 k8s集群支持session和application模式,job模式将会被废弃,本文分析session模式集群 Configuration作为配置容器,几乎所有的构建需要从配置类获取配置项,这里不显示…...

商城开发:商城系统的哪些功能值得企业去关注?

电子商务行业的快速发展&#xff0c;企业们越来越重视建设自己的在线商城。选择一个功能强大的商城系统对于企业的成功至关重要。那么&#xff0c;有哪些商城系统的功能值得企业去关注呢&#xff1f; 一、用户体验提升 ①. 响应式设计 移动设备的普及&#xff0c;大部分用户通…...

calibre和cpolar搭建一个私有的网络书库

Kindle中国电子书店停运不要慌&#xff0c;十分钟搭建自己的在线书库随时随地看小说&#xff01; 文章目录 Kindle中国电子书店停运不要慌&#xff0c;十分钟搭建自己的在线书库随时随地看小说&#xff01;1.网络书库软件下载安装2.网络书库服务器设置3.内网穿透工具设置4.公网…...

网站开发用了哪些知识要点/软文广告经典案例300

注会1401一、基本操作 (只有3有答案)1.修改\职工考勤表\表\照片\字段的数据类型为\对象\&#xff0c;将\职工编号\的字段名称改为\工号\&#xff1b;2.设置\职工考勤表\表中\工号\和\职务代码\字段为主键&#xff1b;设置\出生日期\字段的默认值为当前日期&#xff1b;(提示&am…...

学网站建设 去哪里/站外推广方式

https://www.cnblogs.com/williamjie/p/9502560.html 1、老写法 keys crm*2、 scan 0 count 10 match crm*会返回两个数组&#xff0c;第一个数组是第二次 scan 开始的游标 &#xff0c;第二个数组为元素 count用于设置每次查找多少个&#xff0c;match用于模糊匹配...

e建网/杭州seo公司排名

保障 SAP HANA 系统平衡运转深入了解 SAP HANA 实施的健康状况和性能&#xff0c;并执行快速的故障排除以免影响用户。跟踪 CPU、内存和磁盘使用情况监控 SAP HANA 数据库的可用性状态以及最重要的系统指标&#xff0c;如 CPU 使用率、内存使用量和磁盘利用率。了解主机所用的内…...

南昌网站建设方案/网站 软件

论文地址&#xff1a;https://www.rose-hulman.edu/class/se/csse461/handouts/Day37/nister_d_146.pdf 摘要 我们展示了一个系统可以评估运动的一个立体头或者一个移动相机基于视频输入。这个系统运行在实时低时延以及运动评估使用航行目的。前端系统是一个特征跟踪器。点特征…...

可不可以免费创建网站/建筑设计网站

JAVA问题总结13-从键盘输入并输出&#xff0c;加从键盘输入三个数&#xff0c;输出并按从大到小排序。 package java2; /*** 这是一个从键盘输入并输出的一个test* author xubo601450868* time 2015.8.26* version v1.0* */ import java.util.Scanner; public class test4 {pub…...

做lol数据的网站/营业推广策略有哪些

时间过得真快。一转眼时间&#xff0c;我们有进入到了第二阶段的学习。让我感到欣慰的是&#xff0c;传说中的jquery开始学习了。还有就是我们的导师也换了&#xff01; 两天的学习让我感觉还是挺轻松的。感觉jquery和JS比起来&#xff0c;真的是天壤之别&#xff01;而学习起来…...