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

代码随想录day39 动态规划7

打家劫舍

题目:198.打家劫舍  213.打家劫舍II   337.打家劫舍III

需要重做:全部

198.打家劫舍

思路:第i个房子偷与不偷,取决于第i-2个房子和第i-1个房子

注意:注意下标的一致性。现在的下标含义是房子的下标,而不是第几个房子。(也可以更改)

五部:

1.dp[i]:在第i个房子时,最多的钱

2.dp[i]=max(dp[i-2]+nums[i],dp[i-1]);

3.由递推式,知道要初始化dp0和dp1

4.从前到后遍历。

代码:

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

213.打家劫舍II

思路:在上题基础上,增加了环形。所以分成三种情况:

1.不含首尾元素;

2.可能包含首元素不含尾元素

3.可能包含尾元素不含首元素

利用198的函数即可

注意:其中,情况2 和情况3 都包含了情况1,所以情况1在计算中可以忽略

代码:

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

337.打家劫舍III    --树形dp

思路:就是从树根节点出发,决定每个节点是偷还是不偷。结合了树的遍历和动规。因为需要左右 的值来决定中间的值,所以选择后序遍历。

注意:

树的分析:

1.参数,返回值:应该return一个两个元素的数组,分别代表偷当前节点和不偷当前节点的值。参数为树节点

2.终止条件:遇到空节点return(0,0),遇到叶子返回(叶子val,0)

3.遍历顺序:后序遍历,因为需要左右的值。且需要记录左右的值

vector<int>left=rob(root->left) 

4.单层逻辑:val1=cur->val+left(1)+right(1):偷该节点

val2=max(left[0],left[1])+max(right[0].right[1]);不偷该节点(可以选择左右孩子偷还是不偷,选最大 的)

最后return(val1,val2)

代码:

class Solution {
public:int rob(TreeNode* root) {vector<int>res=robTree(root);return max(res[0],res[1]);}vector<int>robTree(TreeNode*cur){if(cur==nullptr)return {0,0};//(偷该节点,不偷该节点)if(cur->left==nullptr&&cur->right==nullptr)return{cur->val,0};vector<int>left=robTree(cur->left);vector<int>right=robTree(cur->right);int val1=cur->val+left[1]+right[1];int val2=max(left[0],left[1])+max(right[0],right[1]);return {val1,val2};}
};

相关文章:

代码随想录day39 动态规划7

打家劫舍 题目&#xff1a;198.打家劫舍 213.打家劫舍II 337.打家劫舍III 需要重做&#xff1a;全部 198.打家劫舍 思路&#xff1a;第i个房子偷与不偷&#xff0c;取决于第i-2个房子和第i-1个房子 注意&#xff1a;注意下标的一致性。现在的下标含义是房子的下标&#x…...

ESP32-S3模组上实现低功耗(5)

接前一篇文章:ESP32-S3模组上实现低功耗(4) 本文内容参考: 系统低功耗模式介绍 - ESP32-S3 - — ESP-IDF 编程指南 latest 文档 电源管理 - ESP32-S3 - — ESP-IDF 编程指南 latest 文档...

PDF转文本以及转图片:itextpdf

文章目录 &#x1f412;个人主页&#xff1a;信计2102罗铠威&#x1f3c5;JavaEE系列专栏&#x1f4d6;前言&#xff1a;&#x1f380; 1. itextpdf1.1导入itextpdf的maven依赖1.2 提取文本代码1.3 pdf转换成图片代码&#xff08;本地图片地址还是线上PDF的URL地址均支持&#…...

AnaConda下载PyTorch慢的解决办法

使用Conda下载比较慢&#xff0c;改为pip下载 复制下载链接到迅雷下载 激活虚拟环境&#xff0c;安装whl&#xff0c;即可安装成功 pip install D:\openai.wiki\ChatGLM2-6B\torch-2.4.1cu121-cp38-cp38-win_amd64.whl...

移动端自动化测试Appium-java

一、Appium的简介 移动端的自动化测试框架 模拟人的操作进行功能自动化常用于功能测试、兼容性测试 跨平台的自动化测试 二、Appium的原理 核心是web服务器&#xff0c;接受客户端的连接&#xff0c;接收客户端的命令&#xff0c;在手机设备上执行命令&#xff0c;收集命令…...

IO: 作业:Day1

思维导图 main.c #include"student.h" int main(int argc, const char *argv[]) { stuPtr hcreat(); int n0; add_node(h); add_node(h); add_node(h); show(h); save(h,"student.txt"); stuPtr ptrc…...

ue5 替换角色的骨骼网格体和动画蓝图

一开始动画蓝图&#xff0c;骨骼网格体都是用的女性角色 现在把它换成男性 编译 保存 运行 把动画类换成ABP_Manny 进入ABP_Manny中 进入到idle 找到这个拖进来 编译 就变成站着端枪 运行一下&#xff0c;没有问题...

el-cascader 树状选择-点击父级禁用子级

背景&#xff1a;项目上需要实现树状选择&#xff0c;点击父级禁用子级的功能&#xff0c;element组件本身没有该配置项说明&#xff1a;需要实现几个功能点&#xff1a;点击父级禁用子级&#xff1b;再次点击取消禁用&#xff1b;仅回填所选级&#xff1b;上下级不关联实现代码…...

AWS re:Invent 的创新技术

本月早些时候&#xff0c;Amazon 于 12 月 1 日至 5 日在内华达州拉斯维加斯举行了为期 5 天的 re&#xff1a;Invent 大会。如果您从未参加过 re&#xff1a;Invent 会议&#xff0c;那么最能描述它的词是“巨大”——不仅从与会者人数&#xff08;60,000 人&#xff09;来看&…...

PHP7和PHP8的最佳实践

php 7 和 php 8 的最佳实践包括&#xff1a;使用类型提示以避免运行时错误&#xff1b;利用命名空间组织代码并避免命名冲突&#xff1b;采用命名参数、联合类型等新特性增强可读性&#xff1b;用错误处理优雅地处理异常&#xff1b;关注性能优化&#xff0c;如避免全局变量和选…...

Debian、Ubuntu 22.04和ubuntu 24.04国内镜像源(包括 docker 源)

Debian 更换国内清华源 1、备份原文件mv /etc/apt/sources.list /etc/apt/sources.list.old 2、写入新源&#xff0c;以下是 Debian 11 的&#xff1a; cat > /etc/apt/sources.list << EOF deb https://mirrors.tuna.tsinghua.edu.cn/debian/ bullseye main contrib…...

点亮一个esp32 的led

最近入了一个ESP32 兄弟们&#xff0c;这玩意还可以&#xff0c;买来肯定是给它点亮啊对吧 我就是点灯侠&#x1f387; &#x1f62d;千万不要不接天线啊&#xff0c;不然你会一直找不到你的wifi 1.点灯第一步你得有IDE Arduino 就是这个绿东西 可是怎么下载安装呢&#xff…...

C++ shared_ptr进一步认知,为什么引用计数>2退出作用域都可以调用析构

1.使用智能指针需要#include <memeroy> 2.上代码&#xff1a; #include <memory> #include <iostream> using namespace std; struct lifePeriod {lifePeriod():a(1){cout << "无参构造&#xff01;" << endl;}virtual ~lifePeriod(…...

JavaScript代码片段二

见过不少人、经过不少事、也吃过不少苦&#xff0c;感悟世事无常、人心多变&#xff0c;靠着回忆将往事串珠成链&#xff0c;聊聊感情、谈谈发展&#xff0c;我慢慢写、你一点一点看...... JavaScript统计文字个数、特殊字符转义、动态插入js代码、身份证验证 统计文字个数 f…...

【计算机视觉】单目深度估计模型-Depth Anything-V2

概述 本篇将简单介绍Depth Anything V2单目深度估计模型&#xff0c;该模型旨在解决现有的深度估计模型在处理复杂场景、透明或反射物体时的性能限制。与前一代模型相比&#xff0c;V2版本通过采用合成图像训练、增加教师模型容量&#xff0c;并利用大规模伪标签现实数据进行学…...

Servlet 和 Spring MVC:区别与联系

前言 在 Java Web 开发中&#xff0c;Servlet 和 Spring MVC 是两个重要的技术。Servlet 是 Java Web 的基础组件&#xff0c;而 Spring MVC 是一个高级 Web 框架&#xff0c;建立在 Servlet 的基础之上&#xff0c;提供了强大的功能和易用性。这篇文章将从定义、原理、功能对…...

【期末复习】三、内存管理

1.物理内存管理 空闲内存管理方式主要分为:等长划分和不等长划分。 内存管理方式 单一连续分区 基本思想:一段时间内只有一个进程在内存。 特点:简单,内存利用率低, 有三种不同的布局: 固定分区 把内存空间分割成若干区域, 称为分区。 每个分区的大小可以相同也可…...

Microsoft Azure Cosmos DB:全球分布式、多模型数据库服务

目录 前言1. Azure Cosmos DB 简介1.1 什么是 Azure Cosmos DB&#xff1f;1.2 核心技术特点 2. 数据模型与 API 支持2.1 文档存储&#xff08;Document Store&#xff09;2.2 图数据库&#xff08;Graph DBMS&#xff09;2.3 键值存储&#xff08;Key-Value Store&#xff09;…...

【Docker】安装registry本地镜像库,开启Https功能

下载镜像 docker pull registry:2 需要启动https功能&#xff0c;就要生成服务端的自签名的证书和私钥&#xff0c;以及在docker客户端安装这个经过签名的证书。 第一步&#xff1a;生成公私钥信息&#xff0c;第二步&#xff0c;制作证书签名申请文件&#xff0c; 第三步&…...

JUC--线程池

线程池 七、线程池7.1线程池的概述7.2线程池的构建与参数ThreadPoolExecutor 的构造方法核心参数线程池的工作原理 Executors构造方法newFixedThreadPoolnewCachedThreadPoolnewSingleThreadExecutornewScheduledThreadPool(int corePoolSize) 为什么不推荐使用内置线程池&…...

Cursor实现用excel数据填充word模版的方法

cursor主页&#xff1a;https://www.cursor.com/ 任务目标&#xff1a;把excel格式的数据里的单元格&#xff0c;按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例&#xff0c;…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放

简介 前面两期文章我们介绍了I2S的读取和写入&#xff0c;一个是通过INMP441麦克风模块采集音频&#xff0c;一个是通过PCM5102A模块播放音频&#xff0c;那如果我们将两者结合起来&#xff0c;将麦克风采集到的音频通过PCM5102A播放&#xff0c;是不是就可以做一个扩音器了呢…...

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

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

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...

OPENCV形态学基础之二腐蚀

一.腐蚀的原理 (图1) 数学表达式&#xff1a;dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一&#xff0c;腐蚀跟膨胀属于反向操作&#xff0c;膨胀是把图像图像变大&#xff0c;而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...

Mobile ALOHA全身模仿学习

一、题目 Mobile ALOHA&#xff1a;通过低成本全身远程操作学习双手移动操作 传统模仿学习&#xff08;Imitation Learning&#xff09;缺点&#xff1a;聚焦与桌面操作&#xff0c;缺乏通用任务所需的移动性和灵活性 本论文优点&#xff1a;&#xff08;1&#xff09;在ALOHA…...

Python+ZeroMQ实战:智能车辆状态监控与模拟模式自动切换

目录 关键点 技术实现1 技术实现2 摘要&#xff1a; 本文将介绍如何利用Python和ZeroMQ消息队列构建一个智能车辆状态监控系统。系统能够根据时间策略自动切换驾驶模式&#xff08;自动驾驶、人工驾驶、远程驾驶、主动安全&#xff09;&#xff0c;并通过实时消息推送更新车…...

Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)

引言 在人工智能飞速发展的今天&#xff0c;大语言模型&#xff08;Large Language Models, LLMs&#xff09;已成为技术领域的焦点。从智能写作到代码生成&#xff0c;LLM 的应用场景不断扩展&#xff0c;深刻改变了我们的工作和生活方式。然而&#xff0c;理解这些模型的内部…...