当前位置: 首页 > 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;旨在通过…...

【Oracle APEX开发小技巧12】

有如下需求&#xff1a; 有一个问题反馈页面&#xff0c;要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据&#xff0c;方便管理员及时处理反馈。 我的方法&#xff1a;直接将逻辑写在SQL中&#xff0c;这样可以直接在页面展示 完整代码&#xff1a; SELECTSF.FE…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

前一阵子在百度 AI 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...

Java线上CPU飙高问题排查全指南

一、引言 在Java应用的线上运行环境中&#xff0c;CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时&#xff0c;通常会导致应用响应缓慢&#xff0c;甚至服务不可用&#xff0c;严重影响用户体验和业务运行。因此&#xff0c;掌握一套科学有效的CPU飙高问题排查方法&…...

Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?

在大数据处理领域&#xff0c;Hive 作为 Hadoop 生态中重要的数据仓库工具&#xff0c;其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式&#xff0c;很多开发者常常陷入选择困境。本文将从底…...

[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】

大家好&#xff0c;我是java1234_小锋老师&#xff0c;看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】&#xff0c;分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...

华为OD机考-机房布局

import java.util.*;public class DemoTest5 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseSystem.out.println(solve(in.nextLine()));}}priv…...

通过 Ansible 在 Windows 2022 上安装 IIS Web 服务器

拓扑结构 这是一个用于通过 Ansible 部署 IIS Web 服务器的实验室拓扑。 前提条件&#xff1a; 在被管理的节点上安装WinRm 准备一张自签名的证书 开放防火墙入站tcp 5985 5986端口 准备自签名证书 PS C:\Users\azureuser> $cert New-SelfSignedCertificate -DnsName &…...

Python竞赛环境搭建全攻略

Python环境搭建竞赛技术文章大纲 竞赛背景与意义 竞赛的目的与价值Python在竞赛中的应用场景环境搭建对竞赛效率的影响 竞赛环境需求分析 常见竞赛类型&#xff08;算法、数据分析、机器学习等&#xff09;不同竞赛对Python版本及库的要求硬件与操作系统的兼容性问题 Pyth…...

QT开发技术【ffmpeg + QAudioOutput】音乐播放器

一、 介绍 使用ffmpeg 4.2.2 在数字化浪潮席卷全球的当下&#xff0c;音视频内容犹如璀璨繁星&#xff0c;点亮了人们的生活与工作。从短视频平台上令人捧腹的搞笑视频&#xff0c;到在线课堂中知识渊博的专家授课&#xff0c;再到影视平台上扣人心弦的高清大片&#xff0c;音…...

Axure Rp 11 安装、汉化、授权

Axure Rp 11 安装、汉化、授权 1、前言2、汉化2.1、汉化文件下载2.2、windows汉化流程2.3、 macOs汉化流程 3、授权 1、前言 Axure Rp 11官方下载链接&#xff1a;https://www.axure.com/downloadthanks 2、汉化 2.1、汉化文件下载 链接: https://pan.baidu.com/s/18Clf…...