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

保姆级教程:用Sigrity PowerSI提取5GHz内单端S参数(附DDR4仿真实例)

从零掌握Sigrity PowerSI&#xff1a;5GHz单端S参数提取与DDR4实战解析 在高速PCB设计中&#xff0c;信号完整性问题往往成为工程师的"隐形杀手"。当DDR4内存接口速率突破2400MHz时&#xff0c;传统时域分析方法已难以捕捉信号在传输过程中的微妙变化。散射参数&…...

收藏!小白程序员快速入行Agent开发:低门槛高薪风口已开启!

本文详细介绍了Agent开发领域的入门要求&#xff0c;强调Python工程能力、LLM API调用、RAG技术、Function Calling原理等核心技能。文章指出&#xff0c;虽然Agent开发对学历要求不高&#xff0c;但需掌握扎实的技术栈和具备实战项目经验&#xff0c;建议小白抓住当前低门槛窗…...

如何在Windows上轻松安装APK文件:告别模拟器的完整指南

如何在Windows上轻松安装APK文件&#xff1a;告别模拟器的完整指南 【免费下载链接】APK-Installer An Android Application Installer for Windows 项目地址: https://gitcode.com/GitHub_Trending/ap/APK-Installer 你是否曾经想要在Windows电脑上直接运行Android应用…...

企业AI成本为什么总是失控?Token计量与费用归因体系设计

一、问题背景随着企业大规模接入大模型能力&#xff0c;一个普遍现象正在浮现&#xff1a;AI成本正在失控。月初预算批了10万&#xff0c;月底账单来了20万。问财务&#xff1a;钱花哪了&#xff1f;财务说&#xff1a;只知道总额&#xff0c;不知道细节。问IT&#xff1a;哪个…...

【Arcgis实战技巧】巧用DOM目视解译,从DSM中精准“挖”出地面高程点

1. 为什么需要从DSM中提取地面高程点&#xff1f; 在测绘和地理信息领域&#xff0c;数字表面模型&#xff08;DSM&#xff09;记录了地表所有物体的顶部高程信息&#xff0c;包括建筑物、树木、电线杆等。但很多时候我们需要的是数字高程模型&#xff08;DEM&#xff09;&…...

避坑指南:SuperMap iServer 跨版本升级时,备份恢复配置文件必须注意的3个细节

SuperMap iServer跨版本升级&#xff1a;配置文件备份恢复的三大关键策略 当技术团队准备将SuperMap iServer从10i版本升级到11i时&#xff0c;最容易被忽视却最致命的环节莫过于配置文件的处理。许多工程师习惯性地将旧版本备份包直接恢复到新环境&#xff0c;结果遭遇服务启动…...

收藏!AI时代程序员是消失还是逆袭?小白程序员必看大模型逆袭指南

收藏&#xff01;AI时代程序员是消失还是逆袭&#xff1f;小白程序员必看大模型逆袭指南 文章探讨了AI对程序员行业的影响&#xff0c;指出AI抢走了程序员一半的饭碗&#xff0c;但也为另一半人打开了高阶职场的大门。初级岗位因AI工具普及而面临失业风险&#xff0c;但高级技术…...

LLM Wiki Bridge:将Markdown知识库编译为AI可操作的概念图谱

1. 项目概述&#xff1a;将你的知识库变成AI的“第二大脑” 如果你和我一样&#xff0c;是个重度笔记用户&#xff0c;大概率也经历过这样的场景&#xff1a;在Obsidian、Logseq或者任何你喜欢的Markdown编辑器里&#xff0c;日积月累了成百上千篇笔记。你清楚地记得自己写过某…...

前后端分离林业产品推荐系统系统|SpringBoot+Vue+MyBatis+MySQL完整源码+部署教程

摘要 随着信息技术的快速发展&#xff0c;林业产品的销售和推广方式逐渐从传统线下模式转向数字化和智能化。林业产品种类繁多&#xff0c;消费者在选购时往往面临信息不对称的问题&#xff0c;难以高效匹配自身需求。同时&#xff0c;林业企业也缺乏精准的用户画像和推荐机制&…...

哔哩下载姬DownKyi:B站视频下载的终极免费解决方案

哔哩下载姬DownKyi&#xff1a;B站视频下载的终极免费解决方案 【免费下载链接】downkyi 哔哩下载姬downkyi&#xff0c;哔哩哔哩网站视频下载工具&#xff0c;支持批量下载&#xff0c;支持8K、HDR、杜比视界&#xff0c;提供工具箱&#xff08;音视频提取、去水印等&#xff…...