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

【代码随想录算法训练营第37期 第四十五天 | LeetCode198.打家劫舍、213.打家劫舍II、337.打家劫舍III】

代码随想录算法训练营第37期 第四十五天 | LeetCode198.打家劫舍、213.打家劫舍II、337.打家劫舍III


一、198.打家劫舍

解题代码C++:

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

题目链接/文章讲解/视频讲解:
https://programmercarl.com/0198.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8D.html



二、213.打家劫舍II

解题代码C++:

class Solution {
public:int rob(vector<int>& nums) {if (nums.size() == 0) return 0;if (nums.size() == 1) return nums[0];int result1 = robRange(nums, 0, nums.size() - 2); // 情况二int result2 = robRange(nums, 1, nums.size() - 1); // 情况三return max(result1, result2);}// 198.打家劫舍的逻辑int robRange(vector<int>& nums, int start, int end) {if (end == start) return nums[start];vector<int> dp(nums.size());dp[start] = nums[start];dp[start + 1] = max(nums[start], nums[start + 1]);for (int i = start + 2; i <= end; i++) {dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);}return dp[end];}
};

题目链接/文章讲解/视频讲解:
https://programmercarl.com/0213.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8DII.html



三、337.打家劫舍III

解题代码C++:

class Solution {
public:unordered_map<TreeNode* , int> umap; // 记录计算过的结果int rob(TreeNode* root) {if (root == NULL) return 0;if (root->left == NULL && root->right == NULL) return root->val;if (umap[root]) return umap[root]; // 如果umap里已经有记录则直接返回// 偷父节点int val1 = root->val;if (root->left) val1 += rob(root->left->left) + rob(root->left->right); // 跳过root->leftif (root->right) val1 += rob(root->right->left) + rob(root->right->right); // 跳过root->right// 不偷父节点int val2 = rob(root->left) + rob(root->right); // 考虑root的左右孩子umap[root] = max(val1, val2); // umap记录一下结果return max(val1, val2);}
};

题目链接/文章讲解/视频讲解:
https://programmercarl.com/0337.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8DIII.html

相关文章:

【代码随想录算法训练营第37期 第四十五天 | LeetCode198.打家劫舍、213.打家劫舍II、337.打家劫舍III】

代码随想录算法训练营第37期 第四十五天 | LeetCode198.打家劫舍、213.打家劫舍II、337.打家劫舍III 一、198.打家劫舍 解题代码C&#xff1a; class Solution { public:int rob(vector<int>& nums) {if (nums.size() 0) return 0;if (nums.size() 1) return num…...

Elasticsearch查询上下文和_source

查询上下文 {"took": 1,"timed_out": false,"_shards": {"total": 1,"successful": 1,"skipped": 0,"failed": 0},"hits": {"total": {"value": 1,"relation"…...

golang实现网卡流量监控

获取当前时刻一分钟前的网卡流量排序 package mainimport ("fmt""github.com/mackerelio/go-osstat/network""log""net/http""sort""strconv""time" )var arr []map[string]int var arr2 []map[string]…...

技术分享:直播平台如何开发并接入美颜SDK

本篇文章&#xff0c;笔者将分享直播平台如何开发并接入美颜SDK的技术细节与步骤。 一、选择合适的美颜SDK 首先&#xff0c;选择一款适合的美颜SDK非常重要。市面上有很多优秀的美颜SDK供应商&#xff0c;选择时应考虑以下因素&#xff1a; 功能丰富性&#xff1a;支持美白…...

左耳听风_114_113_Go编程模式修饰器

你好&#xff0c;我是陈浩&#xff0c;我名多尔多house.之前呢我写过一篇文章叫做python修饰器的函数式编程。 那这种模式呢可以很轻松的把一些函数啊装配到另外一些函数上。 让你的代码呢更加简单&#xff0c;也可以让一些小功能性的代码复用性更高。 让代码中的函数呢可以…...

Java实习手册(小白也看得懂)

秃狼说 距离俺发布的学习路线已经六个月了&#xff0c;那我给小伙伴的学习周期是四五个月左右&#xff0c;我相信大多的小伙伴已经学习的差不多了。正好赶上暑期实习的阶段&#xff0c;在暑期找到实习就成为暑期的头等大事。 实习经验在校招的起到决定性的作用&#xff0c;所…...

Elasticsearch 分析器(Analyzer)的作用和配置

在Elasticsearch中&#xff0c;分析器&#xff08;Analyzer&#xff09;是文本处理的核心组件&#xff0c;它负责将输入的文本转换为可用于搜索和索引的词项&#xff08;tokens&#xff09;。这一过程涉及多个步骤&#xff0c;包括字符过滤、分词和标记过滤&#xff0c;共同决定…...

SpringBoot(一)创建一个简单的SpringBoot工程

Spring框架常用注解简单介绍 SpringMVC常用注解简单介绍 SpringBoot&#xff08;一&#xff09;创建一个简单的SpringBoot工程 SpringBoot&#xff08;二&#xff09;SpringBoot多环境配置 SpringBoot&#xff08;三&#xff09;SpringBoot整合MyBatis SpringBoot&#xff08;四…...

简述Vue中的数据双向绑定原理

Vue中的数据双向绑定原理是Vue框架的核心特性之一&#xff0c;它通过数据劫持结合发布者-订阅者模式来实现。下面将详细阐述Vue中数据双向绑定的原理&#xff0c;并尽量按照清晰的结构进行归纳&#xff1a; 一、数据劫持 使用Object.defineProperty()&#xff1a; Vue在组件…...

C++STL函数对象的应用

STL函数对象 文章目录 STL函数对象1.基本概念2.使用方法1. 简单函数对象示例2. 函数对象作为算法参数3. Lambda表达式作为函数对象 2.一元谓词和二元谓词1.一元谓词2.二元谓词3.总结 3.算术仿函数1.使用示例2.Lambda表达式的替代 4.关系仿函数5.逻辑仿函数 C中的函数对象&#…...

AJAX-day1:

注&#xff1a;文件布局&#xff1a; 一、AJAX的概念&#xff1a; AJAX是浏览器与服务器进行数据通信的技术 >把数据变活 二、AJAX的使用&#xff1a; 使用axios库&#xff0c;与服务器进行数据通信 基于XMLHttpRequest封装&#xff0c;代码简单 Vue,React项目使用 学习…...

昆虫学(书籍学习资料)

包括昆虫分类&#xff08;上下册&#xff09;、昆虫生态大图鉴等书籍资料。...

springboot + mybatis 多数据源切换

参考的b站博主写的 配置文件: spring:datasource:db1:jdbc-url: jdbc:mysql://localhost:3306/interview_database?useUnicodetrue&characterEncodingutf-8&useSSLfalseusername: rootpassword: 12345driver-class-name: com.mysql.cj.jdbc.Driverdb2:jdbc-url: jdbc…...

windows电脑网络重置后wifi列表消失怎么办?

我们的电脑网络偶尔会出现异常&#xff0c;我们通常会下意识选择网络诊断&#xff0c;运行完诊断后一般会让我们选择重置网络&#xff0c;然而&#xff0c;重置后wifi列表突然消失&#xff0c;无法愉快地上网了&#xff0c;找了一圈&#xff0c;都说是更改适配器选项&#xff0…...

Python + 在线 + 文生音,音转文(中文文本转为英文语音,语音转为中文文本)

开源模型 平台&#xff1a;https://huggingface.co/ars-语言转文本: pipeline("automatic-speech-recognition", model"openai/whisper-large-v3", device0 ) hf: https://huggingface.co/openai/whisper-large-v3 github: https://github.com/openai/wh…...

哏号分治,CF103D - Time to Raid Cowavans

一、题目 1、题目描述 2、输入输出 2.1输入 2.2输出 3、原题链接 103D - Time to Raid Cowavans 二、解题报告 1、思路分析 想了半天数据结构最终选择根号分治 我们考虑 大于 550 的公差直接暴力 小于550 的公差的所有询问&#xff0c;我们直接计算该公差后缀和&#xf…...

基于深度学习的图像背景剔除

在过去几年的机器学习领域&#xff0c;我一直想打造真正的机器学习产品。 几个月前&#xff0c;在参加了精彩的 Fast.AI 深度学习课程后&#xff0c;似乎一切皆有可能&#xff0c;我有机会&#xff1a;深度学习技术的进步使许多以前不可能实现的事情成为可能&#xff0c;而且开…...

Python使用(...)连接字符串

Python 字符串连接的灵活性。 使用括号来组织多行字符串时的自动拼接。 e e var_str g*3connect_str (fa{e}bcvar_strh )print(connect_str) print(type(connect_str)) 运行结果&#xff1a; aebcgggh <class str> 解释&#xff1a; 定义变量&#xff1a; e e:…...

鸿蒙:1.入门

概述 简介 鸿蒙操作系统&#xff08;HarmonyOS&#xff09;是华为公司发布的一款智能终端系统&#xff0c;是基于微内核的面向全场景的分布式操作系统。它致力于提供更加安全、高效、低延迟、低功耗的操作体验&#xff0c;可通过技术手段对应用程序和设备进行智能协同&#xf…...

【matlab】智能优化算法——求解目标函数

智能优化算法在求解目标函数方面发挥着重要作用&#xff0c;它通过迭代、筛选等方法来寻找目标函数的最优值&#xff08;极值&#xff09;。以下是关于智能优化算法求解目标函数的详细介绍&#xff1a; 一、智能优化算法概述 智能优化算法是一种搜索算法&#xff0c;旨在通过…...

IDEA运行Tomcat出现乱码问题解决汇总

最近正值期末周&#xff0c;有很多同学在写期末Java web作业时&#xff0c;运行tomcat出现乱码问题&#xff0c;经过多次解决与研究&#xff0c;我做了如下整理&#xff1a; 原因&#xff1a; IDEA本身编码与tomcat的编码与Windows编码不同导致&#xff0c;Windows 系统控制台…...

19c补丁后oracle属主变化,导致不能识别磁盘组

补丁后服务器重启&#xff0c;数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后&#xff0c;存在与用户组权限相关的问题。具体表现为&#xff0c;Oracle 实例的运行用户&#xff08;oracle&#xff09;和集…...

ssc377d修改flash分区大小

1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

力扣-35.搜索插入位置

题目描述 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...

【从零学习JVM|第三篇】类的生命周期(高频面试题)

前言&#xff1a; 在Java编程中&#xff0c;类的生命周期是指类从被加载到内存中开始&#xff0c;到被卸载出内存为止的整个过程。了解类的生命周期对于理解Java程序的运行机制以及性能优化非常重要。本文会深入探寻类的生命周期&#xff0c;让读者对此有深刻印象。 目录 ​…...

水泥厂自动化升级利器:Devicenet转Modbus rtu协议转换网关

在水泥厂的生产流程中&#xff0c;工业自动化网关起着至关重要的作用&#xff0c;尤其是JH-DVN-RTU疆鸿智能Devicenet转Modbus rtu协议转换网关&#xff0c;为水泥厂实现高效生产与精准控制提供了有力支持。 水泥厂设备众多&#xff0c;其中不少设备采用Devicenet协议。Devicen…...

【无标题】湖北理元理律师事务所:债务优化中的生活保障与法律平衡之道

文/法律实务观察组 在债务重组领域&#xff0c;专业机构的核心价值不仅在于减轻债务数字&#xff0c;更在于帮助债务人在履行义务的同时维持基本生活尊严。湖北理元理律师事务所的服务实践表明&#xff0c;合法债务优化需同步实现三重平衡&#xff1a; 法律刚性&#xff08;债…...

Java详解LeetCode 热题 100(26):LeetCode 142. 环形链表 II(Linked List Cycle II)详解

文章目录 1. 题目描述1.1 链表节点定义 2. 理解题目2.1 问题可视化2.2 核心挑战 3. 解法一&#xff1a;HashSet 标记访问法3.1 算法思路3.2 Java代码实现3.3 详细执行过程演示3.4 执行结果示例3.5 复杂度分析3.6 优缺点分析 4. 解法二&#xff1a;Floyd 快慢指针法&#xff08;…...

今日行情明日机会——20250609

上证指数放量上涨&#xff0c;接近3400点&#xff0c;个股涨多跌少。 深证放量上涨&#xff0c;但有个小上影线&#xff0c;相对上证走势更弱。 2025年6月9日涨停股主要行业方向分析&#xff08;基于最新图片数据&#xff09; 1. 医药&#xff08;11家涨停&#xff09; 代表标…...