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

代码随想录算法训练营Day48 || ● 198.打家劫舍 ● 213.打家劫舍II ● 337.打家劫舍III

问题1:198. 打家劫舍 - 力扣(LeetCode)

你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警

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

思路:该题逻辑关系较为简单,dp[j]表示到j点时的最大值,代码如下:

class Solution {
public:int rob(vector<int>& nums) {if(nums.size()==1) return nums[0];if(nums.size()==2) return (nums[0]<nums[1] ? nums[1] : nums[0]);vector<int> dp(nums.size()+1,0);dp[0] = nums[0];dp[1] = nums[1];for(int i=2;i<nums.size();i++){if(i >= 3) dp[i] = max(max(dp[i-1],nums[i]+dp[i-2]),nums[i]+nums[i-3]);else dp[i] = max(dp[i-1],nums[i]+dp[i-2]);}return dp[nums.size()-1];}
};

问题2:213. 打家劫舍 II - 力扣(LeetCode)

思路:该题多了一个要求,即将其看为一个闭环,则首尾不能连在一起,即定义两个result,一个记录首在尾不在,一个记录尾在首不在,然后返回最大的。代码如下:

class Solution {
public:int robRange(vector<int>& nums,int start,int end){if(start == end) return nums[start];vector<int> dp(nums.size(),0);dp[start] = nums[start];dp[start+1] = max(nums[start+1],nums[start]);  for(int i=start+2;i<=end;i++){dp[i] = max(dp[i-1],dp[i-2]+nums[i]);}     return dp[end];}int rob(vector<int>& nums) {if(nums.size() == 1) return nums[0];if(nums.size() == 2) return nums[0]<nums[1] ? nums[1] : nums[0];int result1 = robRange(nums,0,nums.size()-2);int result2 = robRange(nums,1,nums.size()-1);return max(result1,result2);}
};

问题3:337. 打家劫舍 III - 力扣(LeetCode)

思路:这个题用的是对树的递归,代码如下:

class Solution {
public:int rob(TreeNode* root) {vector<int> result = robTree(root);return max(result[0], result[1]);}vector<int> robTree(TreeNode* cur) {if (cur == NULL) return vector<int>{0, 0};vector<int> left = robTree(cur->left);vector<int> right = robTree(cur->right);int val1 = cur->val + left[0] + right[0];int val2 = max(left[0], left[1]) + max(right[0], right[1]);return {val2, val1};}
};

相关文章:

代码随想录算法训练营Day48 || ● 198.打家劫舍 ● 213.打家劫舍II ● 337.打家劫舍III

问题1&#xff1a;198. 打家劫舍 - 力扣&#xff08;LeetCode&#xff09; 你是一个专业的小偷&#xff0c;计划偷窃沿街的房屋。每间房内都藏有一定的现金&#xff0c;影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统&#xff0c;如果两间相邻的房屋在同一晚上…...

高通面临难题,Oryon核心存在问题,高通8cx Gen 4芯片将推迟发布

"高通公司面临难题&#xff0c;可能会导致骁龙8cx Gen 4的发布时间推迟"&#xff0c;关于骁龙8cx Gen 4处理器&#xff0c;还有一些其他值得关注的特点和功能。首先&#xff0c;据悉&#xff0c;骁龙8cx Gen 4采用了高通自家研发的Oryon核心架构&#xff0c;这是一项…...

安卓手机如何使用邮箱客户端收发邮件

安卓手机品牌较多&#xff0c;设置界面都不太相同&#xff0c;部分手机常见的如vivo、小米手机都是直接填写邮箱用户名和密码&#xff0c;软件自动设置&#xff0c;即可登录邮箱&#xff0c;其他安卓手机或者第三方安卓手机软件有时候需要手动设置&#xff0c;此处以安卓手机的…...

对java中的List进行深拷贝,并进行删除测试

List<String> list new ArrayList<>(); // 需要拷贝的原始List list.add("aaa"); list.add("bbb"); list.add("ccc"); List<String> listNew new ArrayList<>(); // 新List // 将原始List的值赋值给新List Co…...

springboot服务注册到Eureka,端口总是默认8080,自己配置端口不生效

这段时间接手了一个公司的老项目&#xff0c;用的是SpringCloud&#xff0c;在我用的时候突然发现有一个服务&#xff0c;注册到Eureka后&#xff0c;界面显示的端口和实际Ribbon调用的实例端口是不一致的&#xff0c;后来我自己写了个端口获取了一下所有的实例信息&#xff0c…...

LeetCode第11~15题解

CONTENTS LeetCode 11. 盛最多水的容器&#xff08;中等&#xff09;LeetCode 12. 整数转罗马数字&#xff08;中等&#xff09;LeetCode 13. 罗马数字转整数&#xff08;简单&#xff09; LeetCode 11. 盛最多水的容器&#xff08;中等&#xff09; 【题目描述】 给定一个长…...

如何编译打包OpenSSH 9.4并实现批量升级

1 介绍 openssh 9.4版本已于8月10号发布&#xff0c;安全团队又催着要赶紧升级环境里的ssh版本&#xff0c;本文主要介绍Centos5、Centos6、Centos7下openssh 9.4源码编译rpm包以及批量升级服务器openssh版本的方法。关注公众号后台回复ssh可获取本文相关源码文件。 https://w…...

AcWing 898. 数字三角形 (每日一题)

大家好 我是寸铁 希望这篇题解对你有用&#xff0c;麻烦动动手指点个赞或关注&#xff0c;感谢您的关注 注意 像数组下标出现i-1的&#xff0c;在循环的时候从i1开始。 关于0x3f3f3f3f和Integer.MAX_VALUE 0x3f3f3f3f:1061109567 Integer.MAX_VALUE:2147483647 在选用Integ…...

深度学习中,batchsize的大小对训练结果有什么影响,如何正确使用

一、影响&#xff1a; Batch size在深度学习训练中起着非常重要的作用&#xff0c;它对训练速度、模型性能、以及模型的泛化能力都有影响。以下是一些主要的影响&#xff1a; 训练速度&#xff1a;较大的batch size可以更充分地利用硬件并行性&#xff0c;从而加快单个epoch的…...

Squaretest 1.8.3 安装激活

1. 插件下载 2. 离线安装 3. 插件激活...

P21~22 第六章 储能元件——电容存储电场能,电感存储磁场能

1、电容元件 a定义 b线性时不变电容元件 c电容的电压与电流关系 i有限则u有限 注意理解面积 d电容的功率和储能 e例一 跃变就是指物体的物理量从有限值变为无限值的过程。 分析上图例题&#xff1a;对于电源波形要吃负无穷到正无穷去刻画。即时间轴要铺满。 有有图控制电…...

常见API架构介绍

常见API架构介绍 两个服务间进行接口调用&#xff0c;通过调用API的形式进行交互&#xff0c;这是常见CS架构实现的模式&#xff0c;客户端通过调用API即可使用服务端提供的服务。相较于SPI这种模式&#xff0c;就是服务端只规定服务接口&#xff0c;但具体实现交由第三方或者自…...

Vue全局组件与局部组件(详解)

当使用 Vue.js 构建应用时&#xff0c;组件是其核心概念之一。Vue 组件允许你将用户界面分割成独立、可复用的部分。这里我会更详细地解释 Vue 的全局组件和局部组件&#xff0c;包括它们的定义、使用方式以及适用场景。 Vue 全局组件&#xff1a; 全局组件是在整个 Vue 应用…...

对标 GPT-4?科大讯飞刘庆峰:华为GPU技术能力已与英伟达持平

科大讯飞创始人、董事长刘庆峰在亚布力中国企业家论坛第十九届夏季高峰会上透露了关于自家大模型进展的一些新内容。刘庆峰认为&#xff0c;中国在人工智能领域的算法并没有问题&#xff0c;但是算力方面似乎一直被英伟达所限制。 以往的“百模大战”中&#xff0c;训练大型模型…...

pytorch中torch.gather()简单理解

1.作用 从输入张量中按照指定维度进行索引采集操作&#xff0c;返回值是一个新的张量&#xff0c;形状与 index 张量相同&#xff0c;根据指定的索引从输入张量中采集对应的元素。 2.问题 该函数的主要问题主要在dim维度上&#xff0c;dim0 表示沿着第一个维度&#xff08;行…...

计算机网络安全的背景

虽然传统的计算机发展和当今的电子商务不同&#xff0c;但是不可否认网络已经成 为非常重要的信息和数据互换交换的平台。但是随着网络不断发展渗透到人们的日 常生活、手机终端、交易支付等环节时&#xff0c;网络安全已经成为一个焦点和不可逾越的 发展鸿沟。尽管目前网上…...

Linux(实操篇一)

Linux实操篇 Linux(实操篇一)1. 常用基本命令1.1 帮助命令1.1.1 man获得帮助信息1.1.2 help获得shell内置命令的帮助信息1.1.3 常用快捷键 1.2 文件目录类1.2.1 pwd显示当前 工作目录的绝对路径1.2.2 ls列出目录的内容1.2.3 cd切换目录1.2.4 mkdir创建一个新的目录1.2.5 rmdir删…...

如何做一个学术裁缝

水刊&#xff1a;SCI四区&#xff0c;部分三区 顶刊、顶会要看&#xff0c;但是别看多了&#xff0c;知道好的东西长什么样就行了 去水刊&#xff0c;多去看水刊论文&#xff0c;能发现新大陆 一个论文需要多个数据集&#xff08;两个&#xff09;&#xff0c;绝大多数水刊只用…...

微服务系统面经之二: 以秒杀系统为例

16 微服务与集群部署 16.1 一个微服务一般会采用集群部署吗&#xff1f; 对于一个微服务是否采用集群部署&#xff0c;这完全取决于具体的业务需求和系统规模。如果一个微服务的访问压力较大&#xff0c;或者需要提供高可用性&#xff0c;那么采用集群部署是一种常见的策略。…...

73 # 发布自己的 http-server 到 npm

1、添加 .npmignore 文件&#xff0c;忽略不需要的文件 public2、去官网https://www.npmjs.com/检查自己的包名是否被占用 3、切换到官方源&#xff0c;然后检查确认 nrm use npm nrm ls4、登录 npm 账号 npm login5、发布 npm publish6、查看发布情况&#xff0c;发布成功…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...

有限自动机到正规文法转换器v1.0

1 项目简介 这是一个功能强大的有限自动机&#xff08;Finite Automaton, FA&#xff09;到正规文法&#xff08;Regular Grammar&#xff09;转换器&#xff0c;它配备了一个直观且完整的图形用户界面&#xff0c;使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...

云原生安全实战:API网关Kong的鉴权与限流详解

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关&#xff08;API Gateway&#xff09; API网关是微服务架构中的核心组件&#xff0c;负责统一管理所有API的流量入口。它像一座…...

stm32wle5 lpuart DMA数据不接收

配置波特率9600时&#xff0c;需要使用外部低速晶振...

车载诊断架构 --- ZEVonUDS(J1979-3)简介第一篇

我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 做到欲望极简,了解自己的真实欲望,不受外在潮流的影响,不盲从,不跟风。把自己的精力全部用在自己。一是去掉多余,凡事找规律,基础是诚信;二是…...

leetcode73-矩阵置零

leetcode 73 思路 记录 0 元素的位置&#xff1a;遍历整个矩阵&#xff0c;找出所有值为 0 的元素&#xff0c;并将它们的坐标记录在数组zeroPosition中置零操作&#xff1a;遍历记录的所有 0 元素位置&#xff0c;将每个位置对应的行和列的所有元素置为 0 具体步骤 初始化…...

java 局域网 rtsp 取流 WebSocket 推送到前端显示 低延迟

众所周知 摄像头取流推流显示前端延迟大 传统方法是服务器取摄像头的rtsp流 然后客户端连服务器 中转多了&#xff0c;延迟一定不小。 假设相机没有专网 公网 1相机自带推流 直接推送到云服务器 然后客户端拉去 2相机只有rtsp &#xff0c;边缘服务器拉流推送到云服务器 …...