当前位置: 首页 > 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…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

MPNet:旋转机械轻量化故障诊断模型详解python代码复现

目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...

简易版抽奖活动的设计技术方案

1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

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

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

无法与IP建立连接,未能下载VSCode服务器

如题&#xff0c;在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈&#xff0c;发现是VSCode版本自动更新惹的祸&#xff01;&#xff01;&#xff01; 在VSCode的帮助->关于这里发现前几天VSCode自动更新了&#xff0c;我的版本号变成了1.100.3 才导致了远程连接出…...

AI编程--插件对比分析:CodeRider、GitHub Copilot及其他

AI编程插件对比分析&#xff1a;CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展&#xff0c;AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者&#xff0c;分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...

QT3D学习笔记——圆台、圆锥

类名作用Qt3DWindow3D渲染窗口容器QEntity场景中的实体&#xff08;对象或容器&#xff09;QCamera控制观察视角QPointLight点光源QConeMesh圆锥几何网格QTransform控制实体的位置/旋转/缩放QPhongMaterialPhong光照材质&#xff08;定义颜色、反光等&#xff09;QFirstPersonC…...

RSS 2025|从说明书学习复杂机器人操作任务:NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill

视觉语言模型&#xff08;Vision-Language Models, VLMs&#xff09;&#xff0c;为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展&#xff0c;机器人仍难以胜任复杂的长时程任务&#xff08;如家具装配&#xff09;&#xff0c;主要受限于人…...

深入浅出Diffusion模型:从原理到实践的全方位教程

I. 引言&#xff1a;生成式AI的黎明 – Diffusion模型是什么&#xff1f; 近年来&#xff0c;生成式人工智能&#xff08;Generative AI&#xff09;领域取得了爆炸性的进展&#xff0c;模型能够根据简单的文本提示创作出逼真的图像、连贯的文本&#xff0c;乃至更多令人惊叹的…...