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

【代码随想录】day48

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档

文章目录

  • 一、198打家劫舍
  • 二、213打家劫舍II
  • 三、337打家劫舍III


一、198打家劫舍

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

二、213打家劫舍II

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

三、337打家劫舍III

class Solution {
public:unordered_map<TreeNode*, int> umap;int rob(TreeNode* root) {if (root == nullptr) {return 0;}if (root->left == nullptr && root->right == nullptr) {return root->val;}if (umap[root]) {return umap[root];}int val1 = root->val;if (root->left) {val1 += rob(root->left->left) + rob(root->left->right);}if (root->right) {val1 += rob(root->right->left) + rob(root->right->right);}int val2 = rob(root->left) + rob(root->right);umap[root] = max(val1, val2);return max(val1, val2);        }
};

优化版:

class Solution {
public:vector<int> robTree(TreeNode* cur) {if (cur == nullptr) {return vector<int>(2, 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};}int rob(TreeNode* root) {vector<int> dp = robTree(root);return max(dp[0], dp[1]);}
};

相关文章:

【代码随想录】day48

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 一、198打家劫舍二、213打家劫舍II三、337打家劫舍III 一、198打家劫舍 class Solution { public:int rob(vector<int>& nums) {vector<int> dp(n…...

【补充】1-auth的使用、扩写auth的user表、django支持缓存

1 Auth的使用 1.1 扩写auth的user表 2 缓存 1 Auth的使用 # django 的一个app---》用户的登录&#xff0c;退出&#xff0c;注册。。。# 配置文件中配置&#xff1a;---》表会被迁移INSTALLED_APPS [django.contrib.auth,]# auth有哪些表---权限控制&#xff1a;-Permission&a…...

力扣-21. 合并两个有序链表-js实现

/*** Definition for singly-linked list.* function ListNode(val, next) {* this.val (valundefined ? 0 : val)* this.next (nextundefined ? null : next)* }*/ /*** param {ListNode} list1* param {ListNode} list2* return {ListNode}*/ const mergeTwoList…...

tensorflow报错

参考 TensorFlow binary is optimized to use available CPU instructions in performance-critical operations._this tensorflow binary is optimized to use availab-CSDN博客 解决Python中cuBLAS插件无法注册问题_unable to register cudnn factory: attempting to re-CS…...

企业数字化转型走向平台化运营会经历哪些阶段?

蚓链实践总结企业数字化转型走向平台化运营通常会经历以下几个阶段&#xff1a; 1. 规划与准备阶段&#xff1a;明确转型目标和战略&#xff0c;评估现有业务和技术状况&#xff0c;制定转型计划。 2. 基础建设阶段&#xff1a;搭建数字化基础设施&#xff0c;包括云平台、数…...

最新AI实景自动无人直播软件教你实现24小时不下播带货;智能化引领直播新时代

随着互联网的快速发展&#xff0c;直播行业已经成为商家品牌推广和商品销售的热门方式。而如今&#xff0c;一款令人惊叹的AI实景自动无人直播软件正在让直播变得更加智能化和便捷化&#xff0c;为商家带来全新的直播体验。 AI实景自动无人直播软件的一大优势是其智能讲解功能。…...

《二十一》QT QML编程基础

QML概述 QML&#xff08;Qt Meta-Object Language&#xff09;是一种声明性语言&#xff0c;它被用于描述Qt框架中用户界面的结构和行为。QML提供了一种简洁、灵活的方式来创建动态和交互式的界面。 QML基于JavaScript语法&#xff0c;通过使用QML类型和属性来定义界面的元素…...

免费的发票查验接口平台 PHP开发示例

信息爆炸的时代&#xff0c;发票管理工作也在不断走向数字化管理。传统手动录入的方式不仅耗时长&#xff0c;繁琐低效&#xff0c;且容易出现人为错漏的风险&#xff0c;让财务工作者头疼不已。人工智能时代&#xff0c;翔云推出了发票识别发票查验接口&#xff0c;以此来助力…...

10、算数运算符(以 ‘/’、‘%’、‘++’为主去讲解)(Java超详细版本)

算数运算符 一、算数运算符二、“ / ”的使用三、“ % ”的使用四、“ ”的使用⭐ 一、算数运算符 算数运算符是对数值类型的变量进行运算的&#xff0c;在Java程序中使用的非常多的。 二、“ / ”的使用 1、Java中 “ / ” 的运算结果是省略小数部分的整数&#xff0c;不存…...

向量数据库:PGVector

一、PGVector 介绍 PGVector 是一个基于 PostgreSQL 的扩展插件&#xff0c;为用户提供了一套强大的向量存储和查询的功能&#xff1a; 精确和近似最近邻搜索单精度&#xff08;Single-precision&#xff09;、半精度&#xff08;Half-precision&#xff09;、二进制&#xff…...

redux实现原理

Redux 是一个用于 JavaScript 应用程序状态管理的库。它被设计用来管理整个应用程序的状态&#xff0c;并且与 React 结合使用时非常流行。Redux 的实现原理可以简要概括为以下几个关键概念&#xff1a; 单一数据源 (Single Source of Truth)&#xff1a;Redux 应用程序的所有状…...

【go项目01_学习记录04】

学习记录 1 集成 Gorilla Mux1.1 为什么不选择 HttpRouter&#xff1f;1.2 安装 gorilla/mux1.3 使用 gorilla/mux1.4 迁移到 Gorilla Mux1.4.1 新增 homeHandler1.4.2 指定 Methods () 来区分请求方法1.4.3 请求路径参数和正则匹配1.4.4 命名路由与链接生成 1 集成 Gorilla Mu…...

HCIP第二节

OSPF&#xff1a;开放式最短路径协议&#xff08;属于IGP-内部网关路由协议&#xff09; 优点&#xff1a;相比与静态可以实时收敛 更新方式&#xff1a;触发更新&#xff1a;224.0.0.5/6 周期更新&#xff1a;30min 在华为设备欸中&#xff0c;默认ospf优先级是10&#…...

Ubuntu MATE系统下WPS显示错位

系统&#xff1a;Ubuntu MATE 22.04和24.04&#xff0c;在显示器设置200%放大的情况下&#xff0c;显示错位。 显示器配置&#xff1a; WPS显示错位&#xff1a; 这个问题当前没有找到好的解决方式。 因为4K显示屏设置4K分辨率&#xff0c;图标&#xff0c;字体太小&#xff…...

Mysql进阶-索引篇

Mysql进阶 存储引擎前言特点对比 索引介绍常见的索引结构索引分类索引语法sql分析索引使用原则索引失效的几种情况sql提示覆盖索引前缀索引索引设计原则 存储引擎 前言 Mysql的体系结构&#xff1a; 连接层 最上层是一些客户端和链接服务&#xff0c;主要完成一些类似于连接…...

【算法系列】哈希表

目录 哈希表总结 leetcode题目 一、两数之和 二、判定是否互为字符重排 三、存在重复元素 四、存在重复元素 II 五、字母异位词分组 六、在长度2N的数组中找出重复N次的元素 七、两个数组的交集 八、两个数组的交集 II 九、两句话中的不常见单词 哈希表总结 1.存储数…...

Git推送本地项目到gitee远程仓库

Git 是一个功能强大的分布式版本控制系统&#xff0c;它允许多人协作开发项目&#xff0c;同时有效管理代码的历史版本。开发者可以克隆一个公共仓库到本地&#xff0c;进行更改后将更新推送回服务器&#xff0c;或从服务器拉取他人更改&#xff0c;实现代码的同步和版本控制。…...

一键复制:基于vue实现的tab切换效果

需求&#xff1a;顶部栏有切换功能&#xff0c;内容区域随顶部切换而变化 目录 实现效果实现代码使用示例在线预览 实现效果 如下 实现代码 组件代码 MoTab.vue <template><div class"mo-tab"><divv-for"item in options"class"m…...

新手做抖音小店,卖什么最容易出单?抖音必爆类目来了!

哈喽&#xff01;我是电商月月 新手做抖音小店没有经验&#xff0c;也不了解市场需求&#xff0c;最好奇的就是&#xff1a;卖什么商品最容易出单&#xff0c;还在犹豫的朋友可以看看这五种类目&#xff0c;在2024年下半年必定火爆一次 一&#xff0e;生活电器类 天气炎热&a…...

男人圣经 10

男人圣经 10 行业基因 你在对行业、客户群体、事情、核心优势上的高感知力 行业基因 你在对行业、客户群体、事情、核心优势上的高感知力 灵性&#xff0c;我感觉是对人、对事情、对行业的感知力&#xff0c;这就是你的天赋程度。 比如情圣&#xff0c;他比女人更懂自己&am…...

ClawdOS:为AI Agent构建可视化操作系统的全栈实践

1. 项目概述&#xff1a;为你的AI大脑装上眼睛和手如果你和我一样&#xff0c;是OpenClaw&#xff08;前身是Moltbot/Clawdbot&#xff09;的早期用户&#xff0c;那你一定经历过这种场景&#xff1a;在终端里&#xff0c;你的AI助手聪明绝顶&#xff0c;能写代码、查资料、分析…...

告别公网IP焦虑:用SakuraFrp免费隧道,5分钟搞定Linux服务器的SSH远程访问

5分钟实现无公网IP的Linux服务器远程访问&#xff1a;SakuraFrp实战指南 当你需要在外紧急处理家中或办公室的Linux服务器时&#xff0c;却发现没有公网IP无法远程连接&#xff0c;这种焦虑我深有体会。去年深夜的一次线上故障让我深刻认识到内网穿透工具的重要性——当时我正…...

ServerPackCreator终极指南:3分钟自动化创建Minecraft服务器包 [特殊字符]

ServerPackCreator终极指南&#xff1a;3分钟自动化创建Minecraft服务器包 &#x1f680; 【免费下载链接】ServerPackCreator Create a server pack from a Minecraft Forge, NeoForge, Fabric, LegacyFabric or Quilt modpack! 项目地址: https://gitcode.com/gh_mirrors/s…...

从AlexNet到R-CNN:我是如何用迁移学习在VOC数据集上实现目标检测精度翻倍的

从AlexNet到R-CNN&#xff1a;迁移学习在目标检测中的工程实践与精度突破 当我们在2012年第一次看到AlexNet在ImageNet竞赛中碾压传统方法时&#xff0c;很少有人能预见这个突破会如何彻底改变计算机视觉的格局。但就在一年后&#xff0c;R-CNN的诞生将这一变革延伸到了目标检测…...

从零搭建自动化任务中心:mgks/automation-hub部署与实战指南

1. 项目概述&#xff1a;自动化工作流的“中央厨房”如果你和我一样&#xff0c;在开发、运维或者日常工作中&#xff0c;经常需要重复执行一系列命令、脚本或者任务&#xff0c;那么你肯定对“自动化”这个词有着深刻的渴望。从简单的文件备份、日志清理&#xff0c;到复杂的C…...

Lie群方法在机器人状态估计中的创新应用

1. 状态估计技术演进与Lie群方法的核心价值在机器人导航与定位领域&#xff0c;状态估计技术扮演着大脑的角色。想象一下&#xff0c;当你在陌生城市使用手机导航时&#xff0c;系统需要实时融合GPS、陀螺仪和加速度计的数据来确定你的位置——这正是状态估计的典型应用场景。传…...

避开这些坑!在Colab上运行AlphaFold2时,参数、路径和依赖库的常见错误排查指南

避开这些坑&#xff01;在Colab上运行AlphaFold2时&#xff0c;参数、路径和依赖库的常见错误排查指南 在Google Colab上运行AlphaFold2看似简单&#xff0c;但实际操作中90%的用户都会遇到各种"诡异"报错。上周一位结构生物学博士向我吐槽&#xff1a;"明明按照…...

从空洞卷积到多尺度感知:图解PyTorch中ASPP的设计哲学与实现细节(附可运行代码)

从空洞卷积到多尺度感知&#xff1a;图解PyTorch中ASPP的设计哲学与实现细节&#xff08;附可运行代码&#xff09; 当我们观察一幅画时&#xff0c;眼睛会自然地聚焦在不同尺度的细节上——从整体构图到局部纹理&#xff0c;这种多尺度感知能力是人类视觉系统的核心优势。计算…...

从手机5G到智能声呐:LMS自适应波束形成算法在真实场景里是怎么用的?

从手机5G到智能声呐&#xff1a;LMS自适应波束形成算法的工程实践 当你在嘈杂的会议室里对着智能音箱说话时&#xff0c;它为何能精准捕捉你的声音而忽略背景噪音&#xff1f;当5G基站需要同时服务数百个移动设备时&#xff0c;又是如何避免信号相互干扰&#xff1f;这些看似毫…...

LT8650S双通道同步降压稳压器设计与汽车电子应用

1. LT8650S双通道同步降压稳压器设计解析在汽车电子和工业设备领域&#xff0c;电源管理系统的设计往往面临严苛挑战。LT8650S作为一款42V输入、双通道4A输出的同步降压稳压器&#xff0c;其Silent Switcher 2架构和6.2μA超低静态电流特性&#xff0c;为工程师提供了高性价比的…...