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

LeetCode算法 打家劫舍 和 打家劫舍II C++

目录

  • 题目 打家劫舍
  • 参考答案
  • 题目 打家劫舍II
  • 参考答案

题目 打家劫舍

你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。

示例 1:

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

示例 2:
输入:[2,7,9,3,1]
输出:12
解释:偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9),接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
提示:

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

参考答案

class Solution {
public:int rob(vector<int>& nums) {if (nums.empty()) {return 0;}int size = nums.size();if (size == 1) {return nums[0];}int first = nums[0], second = max(nums[0], nums[1]);for (int i = 2; i < size; i++) {int temp = second;second = max(first + nums[i], second);first = temp;}return second;}
};

题目 打家劫舍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 = [0]
输出:0

提示:

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

参考答案

class Solution {
public:int robRange(vector<int>& nums, int start, int end) {int first = nums[start], second = max(nums[start], nums[start + 1]);for (int i = start + 2; i <= end; i++) {int temp = second;second = max(first + nums[i], second);first = temp;}return second;}int rob(vector<int>& nums) {int length = nums.size();if (length == 1) {return nums[0];} else if (length == 2) {return max(nums[0], nums[1]);}return max(robRange(nums, 0, length - 2), robRange(nums, 1, length - 1));}
};

相关文章:

LeetCode算法 打家劫舍 和 打家劫舍II C++

目录题目 打家劫舍参考答案题目 打家劫舍II参考答案题目 打家劫舍 你是一个专业的小偷&#xff0c;计划偷窃沿街的房屋。每间房内都藏有一定的现金&#xff0c;影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统&#xff0c;如果两间相邻的房屋在同一晚上被小偷闯…...

蓝桥杯刷题冲刺 | 倒计时10天

作者&#xff1a;指针不指南吗 专栏&#xff1a;蓝桥杯倒计时冲刺 &#x1f43e;马上就要蓝桥杯了&#xff0c;最后的这几天尤为重要&#xff0c;不可懈怠哦&#x1f43e; 文章目录1.有边数限制的最短路2.九进制转十进制1.有边数限制的最短路 题目 链接&#xff1a; 853. 有边数…...

个人练习-Leetcode-剑指 Offer II 109. 开密码锁

题目链接&#xff1a;https://leetcode.cn/problems/zlDJc7/ 题目大意&#xff1a;给出一个四位数字的密码锁&#xff0c;初始状态是0000&#xff0c;目标是targer。每一次转动只能让一个位的轮盘转动一下&#xff08;0往后转是9&#xff09;。有一个vector<string> dea…...

四个常见的Linux面试问题

四个常见的Linux面试问题。 刚毕业要找工作了&#xff0c;只要是你找工作就会有面试这个环节&#xff0c;那么在面试环节中&#xff0c;有哪些注意事项值得我的关注呢&#xff1f;特别是专业技术岗位&#xff0c;这样的岗位询问一般都是在职的工程师&#xff0c;如何在面试环节…...

15、接口(C#)

15.1 什么是接口 接口是指定一组函数成员而不实现它们的引用类型。所以只能类和结构实现接口。 15.2 声明接口 接口声明不能包含以下成员 数据成员静态成员 接口声明只能包含以下类型的费静态成员函数声明&#xff1a; 方法事件索引器属性 这些函数成员的声明不能包含任何实…...

C++中常见的容器类使用方法举例(vector、deque、map、set)

cpp中常见的容器类有vector、list、deque、map、set、unordered_map和unordered_set。 下面将举例直接说明各个容器的使用方法。 文章目录综合示例1. vector&#xff1a;动态数组&#xff0c;支持随机访问2. list&#xff1a;双向链表&#xff0c;支持双向遍历和插入删除3. de…...

什么是强缓存和协商缓存

什么是缓存 浏览器缓存就是把一个已经请求过的Web资源&#xff08;如html页面&#xff0c;图片&#xff0c;js&#xff0c;数据等&#xff09;拷贝一份副本储存在浏览器中。缓存会根据进来的请求保存输出内容的副本。当下一个请求来到的时候&#xff0c;如果是相同的URL&#…...

算法刷题之堆

1. heapq 堆 Python 中只有最小堆&#xff1a; import heapqa [] heapq.heappush(a, 3) # 添加元素 heapq.heappush(a, 2) heapq.heappush(a, 1) while len(a): # 判断堆的长度print(heapq.heappop(a)) # 弹出堆顶元素# 将列表转换为最小堆 nums [2, 3, 1, 4, 5, 6] hea…...

javaweb导师选择系统

本文以JSP为开发技术&#xff0c;实现了一个导师选择系统。导师选择系统分为三大模块&#xff0c;包括管理员&#xff1a;学员信息管理、导师信息管理、导师选择管理、导师分布图、公告信息管理、系统管理&#xff0c;学生&#xff1a;个人资料管理、导师选择管理、导师分布图管…...

LeetCode150 逆波兰表达式求值

题目&#xff1a; 给你一个字符串数组 tokens &#xff0c;表示一个根据 逆波兰表示法 表示的算术表达式。请你计算该表达式。返回一个表示表达式值的整数。 注意&#xff1a; 有效的算符为 ‘’、‘-’、‘*’ 和 ‘/’ 。每个操作数&#xff08;运算对象&#xff09;都可以…...

【Node.js】项目开发实战(中)

开发用户的注册和登录接口步骤1&#xff0c;打开MySQL Workbench&#xff0c;打开自己的数据库进入创建用户信息表新建 ev_users表安装并配置mysql模块安装mysql模块新建db文件夹下index.js,导入并配置mysql模块安装bcryptjs对密码进行加密处理新建/router_handler/user.js中&a…...

记录一次 New Bing 英语陪练

记录一次 New Bing 英语陪练 Now I start to speak english to chat with you . Help me find the mistake in my word and help me improve my english I’m glad you want to practice your English with me. I can help you find the mistakes in your words and help you i…...

【Python】照片居然能变素描?不会画画但是咱会代码

文章目录前言一、准备二、下载预训练模型总结前言 Photo-Sketching 一个能将照片的轮廓识别出来并将其转化为“速写”型图像的开源模块。 比如&#xff0c;这只小狗&#xff1a; 经过模型的转化&#xff0c;会变成卡通版的小狗&#xff1a; 非常秀&#xff0c;这很人工智能…...

已解决正确配置git环境变量

已解决git没有配置环境变量&#xff0c;抛出异常ERROR: Cannot find command ‘git’- do you have ‘git’ installed and in your PATH?&#xff0c;附上正确配置git环境变量的教程 文章目录报错问题报错翻译报错原因解决方法《100天精通Python》专栏推荐白嫖80g Python全栈…...

【逐步剖C】-第十章-自定义类型之结构体、枚举、联合

一、结构体 前言&#xff1a;有关结构体的声明、定义、初始化以及结构体的传参等结构体的基本使用在文章【逐步剖C】-第六章-结构体初阶中已进行了详细的介绍&#xff0c;需要的朋友们可以看看。这里主要讲解的是有关结构体的内存问题。 1. 结构体的内存对齐 &#xff08;1&…...

Windows Server 2016 中文版、英文版下载 (updated Mar 2023)

Windows Server 2016 Version 1607&#xff0c;2023 年 3 月更新 请访问原文链接&#xff1a;https://sysin.org/blog/windows-server-2016/&#xff0c;查看最新版。原创作品&#xff0c;转载请保留出处。 作者主页&#xff1a;sysin.org 本站将不定期发布官方原版风格月度更…...

Linux 4G 通信实验

目录4G 网络连接简介高新兴ME3630 4G 模块实验ME3630 4G 模块简介ME3630 4G 模块驱动修改ME3630 4G 模块ppp 联网测试前面我们学习了如何在Linux 中使用有线网络或者WIFI&#xff0c;但是使用有线网络或者WIFI 有 很多限制&#xff0c;因为要布线&#xff0c;即使是WIFI 你也得…...

华为OSPF技术详细介绍,保姆级,谁都能看懂(一)

目录 1、简介 2、OSPF基本原理 3、OSPF的特点 4、OSPF区域 5、路由器的类型 6、OSPF5种报文 7、后半部分内容 1、简介 OSPF&#xff08;Open Shortest Path First&#xff0c;开放最短路径优先&#xff09;是一个基于链路状态的内部网关协 议。目前针对IPv4协议使用的是OS…...

行人车辆检测与计数系统(Python+YOLOv5深度学习模型+清新界面)

摘要&#xff1a;行人车辆检测与计数系统用于交通路口行人及车辆检测计数&#xff0c;道路人流量、车流量智能监测&#xff0c;方便记录、显示、查看和保存检测结果。本文详细介绍行人车辆检测&#xff0c;在介绍算法原理的同时&#xff0c;给出Python的实现代码、PyQt的UI界面…...

SM3哈希算法的FPGA实现 I

SM3哈希算法的FPGA实现 I SM3哈希算法的FPGA实现 I一、什么是SM3哈希算法&#xff1f;二、SM3哈希算法的具体内容1、填充2、迭代与压缩3、计算拼凑值三、参考文档语言 &#xff1a;verilog 仿真工具&#xff1a; Modelsim EDA工具&#xff1a;quartus II 一、什么是SM3哈希算法…...

2026.5.12:三台服务器,一台fastapi的websocket服务接口,一台代理fastapi服务的nginx,一台代理上一个nginx,能穿透websocket吗?

三台服务器,一台fastapi的websocket服务接口,一台代理fastapi服务的nginx,一台代理上一个nginx,能穿透websocket吗? 环境: - 三台服务器 1. 一台fastapi中有websocket接口的服务器:43.226.44.50 2. 一台代理上面1里面的fastapi服务的nginx:43.226.44.184 3. 一台代…...

CanFestival回调函数避坑指南:为什么你的RPDO参数修改了却没生效?

CanFestival回调函数深度解析&#xff1a;RPDO参数修改失效的五大隐蔽原因与实战解决方案 在工业自动化领域&#xff0c;CanFestival作为开源的CANopen协议栈&#xff0c;被广泛应用于各类嵌入式设备中。然而&#xff0c;许多开发者在配置RPDO&#xff08;接收过程数据对象&…...

可编程逻辑器件(PLD/CPLD/FPGA)核心原理、选型指南与EDA设计实战

1. 项目概述&#xff1a;从怀旧到硬核&#xff0c;聊聊可编程逻辑的“前世今生”那天在网上闲逛&#xff0c;本想找点微马赛克艺术&#xff08;Micromosaic&#xff09;的制作视频&#xff0c;结果算法一个拐弯&#xff0c;把我带回了上世纪七八十年代的《大青蛙布偶秀》&#…...

现代差旅电力管理实战:从充电安全到设备续航全攻略

1. 一次久违的飞行&#xff1a;无处不在的电力焦虑与科技依赖距离上一次飞行已经过去了整整十七个月。当我上周踏入纽约拉瓜迪亚机场&#xff0c;准备开启后疫情时代的首次旅程时&#xff0c;感觉像是进入了另一个维度。在我缺席的这段时间里&#xff0c;LGA完成了一场彻底的蜕…...

从等待到掌控:构建个人化网盘下载工作流的3个关键步骤

从等待到掌控&#xff1a;构建个人化网盘下载工作流的3个关键步骤 【免费下载链接】Online-disk-direct-link-download-assistant 一个基于 JavaScript 的网盘文件下载地址获取工具。基于【网盘直链下载助手】修改 &#xff0c;支持 百度网盘 / 阿里云盘 / 中国移动云盘 / 天翼…...

从极坐标栅格到地面点云:一种基于坡度与邻域一致性的分割实践

1. 极坐标栅格构建&#xff1a;自动驾驶的"地面扫描仪" 想象你正在玩一款赛车游戏&#xff0c;车辆需要自动识别哪些是能开的平坦路面&#xff0c;哪些是必须绕开的障碍物。现实中自动驾驶车辆面临同样的挑战&#xff0c;而极坐标栅格就是它的"地面扫描仪"…...

构建AI助手持久记忆系统:Rekall项目实践与MCP协议应用

1. 项目概述&#xff1a;为你的AI助手构建一个“第二大脑”如果你和我一样&#xff0c;日常重度依赖 Claude Code、Cursor 这类AI编程助手&#xff0c;那你一定遇到过这个痛点&#xff1a;每次开启一个新的会话&#xff0c;AI助手就像得了“健忘症”&#xff0c;对之前讨论过的…...

LVGL图片资源全解析:从C数组到图标字体的高效集成方案

1. LVGL图片资源方案概述 在嵌入式GUI开发中&#xff0c;图片资源的管理直接影响产品性能和开发效率。LVGL作为轻量级图形库&#xff0c;提供了三种主流的图片集成方案&#xff1a;内部C数组、外部文件系统图片和图标字体。每种方案都有其独特的适用场景和实现方式&#xff0c;…...

常见的 17 种 RAG 方案解析

近年来&#xff0c;随着大语言模型&#xff08;LLM&#xff09;的广泛应用&#xff0c;检索增强生成&#xff08;Retrieval-Augmented Generation&#xff0c;RAG&#xff09;系统逐渐成为连接私有知识库与智能问答的核心架构。RAG 不仅弥补了大模型在实时性与事实性上的不足&a…...

企业微信打卡数据API实战:用Java+FastJSON手把手教你拉取员工考勤记录

企业微信考勤数据集成实战&#xff1a;JavaFastJSON构建高可用API对接方案 考勤数据作为企业管理的重要基础数据&#xff0c;其自动化采集与处理能力直接影响人力资源管理的效率。企业微信作为国内主流的企业级通讯工具&#xff0c;其开放的打卡数据API为开发者提供了便捷的集成…...