337. 打家劫舍 III
题目描述
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为 root 。
除了 root 之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ,房屋将自动报警。
给定二叉树的 root 。返回 在不触动警报的情况下 ,小偷能够盗取的最高金额 。
示例 1:

输入: root = [3,2,3,null,3,null,1]
输出: 7
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7
示例 2:

输入: root = [3,4,5,1,3,null,1]
输出: 9
解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9
提示:
- 树的节点数在
[1, 104]范围内 0 <= Node.val <= 104
解答
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:unordered_map<TreeNode*, int> sums; // key 是出发的节点, value是偷到的总金额int rob(TreeNode* root) {// case1: 对于一个以node为根节点的二叉树而言,若尝试偷 node节点// 那么一定不能偷取其左右子节点,只能尝试左右子节点的左右子节点(孙节点)// case2: 若不偷取node节点,只能尝试偷取其左右子节点// 比较两种方式的结果,取大者return tryRob(root);}int tryRob(TreeNode *root){if(root == nullptr) return 0;// 若已经计算过该节点出发能偷的最大金额就返回if(sums.count(root)) return sums[root];// 偷取该节点int res1 = 0;// 尝试偷取其左右子节点的左右子节点if(root->left) // 左边的孙子{res1 += (tryRob(root->left->left) + tryRob(root->left->right));}if(root->right){res1 += (tryRob(root->right->left) + tryRob(root->right->right));}res1 += root->val; // 偷取该节点加入计算结果// 不偷取root节点,只能尝试偷取其左右子节点int res2 = tryRob(root->left) + tryRob(root->right);sums[root] = max(res1, res2);return sums[root];}
};
相关文章:
337. 打家劫舍 III
题目描述 小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为 root 。 除了 root 之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两…...
tio-websocket-spring-boot-starter的最简单实例,看完你一定有所收获
前言 我最近一个月一直在寻找能够快速开发实时通讯的简单好用的模块,所以我就去寻找了一下相关的内容.在此之前我使用的是Spring原生的webSocket,她有个弊端就是设置组不容易设置,而且配置上也稍微复杂一点,需要配置拦截器和处理器,还需要把它放入到Springboot的启动容器里面,也…...
列出连通集
输入样例: 8 6 0 7 0 1 2 0 4 1 2 4 3 5 输出样例: { 0 1 4 2 7 } { 3 5 } { 6 } { 0 1 2 7 4 } { 3 5 } { 6 } solution #include <stdio.h> #include <string.h> int arcs[10][10]; int visited[10] {0}; void DFS(int n, int v); void BFS(int n , int i)…...
前端 富文本编辑器原理——从javascript、html、css开始入门
文章目录 ⭐前言⭐html的contenteditable属性💖 输入的光标位置(浏览器获取selection)⭐使用Selection.toString () 返回指定的文本⭐getRangeAt 获取指定索引范围 💖 修改光标位置💖 设置选取range ⭐总结⭐结束 ⭐前…...
堆--数据流中第K大元素
如果对于堆不是太认识,请点击:堆的初步认识-CSDN博客 数据流与上述堆--数组中第K大元素-CSDN博客的数组区别: 数据流的数据是动态变化的,数组是写死的 堆--数组中第K大元素-CSDN博客题的小顶堆加一个方法: class MinH…...
【算法|动态规划No.12】leetcode152. 乘积最大子数组
个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望…...
Covert Communication 与选择波束(毫米波,大规模MIMO,可重构全息表面)
Covert Communication for Spatially Sparse mmWave Massive MIMO Channels 2023 TOC abstract 隐蔽通信,也称为低检测概率通信,旨在为合法用户提供可靠的通信,并防止任何其他用户检测到合法通信的发生。出于下一代通信系统安全链路的强烈…...
计算机毕业设计 基于协调过滤算法的绿色食品推荐系统的设计与实现 Java实战项目 附源码+文档+视频讲解
博主介绍:✌从事软件开发10年之余,专注于Java技术领域、Python人工智能及数据挖掘、小程序项目开发和Android项目开发等。CSDN、掘金、华为云、InfoQ、阿里云等平台优质作者✌ 🍅文末获取源码联系🍅 👇🏻 精…...
华为云云耀云服务器L实例评测|部署在线影音媒体系统 Jellyfin
华为云云耀云服务器L实例评测|部署在线影音媒体系统 Jellyfin 一、云耀云服务器L实例介绍1.1 云服务器介绍1.2 产品规格1.3 应用场景1.4 支持镜像 二、云耀云服务器L实例配置2.1 重置密码2.2 服务器连接2.3 安全组配置 三、部署 Jellyfin3.1 Jellyfin 介绍3.2 Docke…...
GhostNet原理解析及pytorch实现
论文:https://arxiv.org/abs/1911.11907 源码:https://github.com/huawei-noah/ghostnet 简要论述GhostNet的核心内容。 Ghost Net 1、Introduction 在训练良好的深度神经网络的特征图中,丰富甚至冗余的信息通常保证了对输入数据的全面理…...
视频二维码的制作方法,支持内容修改编辑
现在学生经常会需要使用音视频二维码,比如外出打开、才艺展示、课文背诵等等。那么如何制作一个可以长期使用的二维码呢?下面来给大家分享一个二维码制作(免费在线二维码生成器-二维码在线制作-音视频二维码在线生成工具-机智熊二维码&#x…...
清华GLM部署记录
环境部署 首先安装anaconda(建议包管理比较方便)windows用户需手动配置一下环境变量,下面默认是在ubuntu环境说明创建python环境,conda create -n your_env_name python3.10 (注:官方是提供是python3.8,但…...
贪心算法+练习
正值国庆之际,祝愿祖国繁荣昌盛,祝愿朋友一生平安!终身学习,奋斗不息! 目录 1.贪心算法简介 2.贪心算法的特点 3.如何学习贪心算法 题目练习(持续更新) 1.柠檬水找零(easy&…...
使用华为eNSP组网试验⑷-OSPF多区域组网
今天进行了OSPF的多区域组网试验,本来这是个很简单的操作,折腾了好长时间,根本原因只是看了别人写的配置代码,没有真正弄明白里面对应的规则。 一般情况下,很多单位都使用OSPF进行多区域的组网,大体分为1个…...
P1843 奶牛晒衣服 【贪心】
P1843 奶牛晒衣服 【贪心】 题目背景 熊大妈决定给每个牛宝宝都穿上可爱的婴儿装 。但是由于衣服很湿,为牛宝宝晒衣服就成了很不爽的事情。于是,熊大妈请你(奶牛)帮助她完成这个重任。 题目描述 一件衣服在自然条件下用一秒的时间…...
91、Redis - 事务 与 订阅-发布 相关的命令 及 演示
★ 事务相关的命令 Redis事务保证事务内的多条命令会按顺序作为整体执行,其他客户端发出的请求绝不可能被插入到事务处理的中间, 这样可以保证事务内所有命令作为一个隔离操作被执行。 Redis事务同样具有原子性,事务内所有命令要么全部被执…...
GPU如何成为AI的加速器
0. 前言 按照国际惯例,首先声明:本文只是我自己学习的理解,虽然参考了他人的宝贵见解,但是内容可能存在不准确的地方。如果发现文中错误,希望批评指正,共同进步。 本文关键词:GPU、深度学习、GP…...
Map声明、元素访问及遍历、⼯⼚模式、实现 Set - GO语言从入门到实战
Map声明、元素访问及遍历 - GO语言从入门到实战 Map 声明的方式 m := map[string]int{"one": 1, "two": 2, "three": 3} //m初始化时就已经设置了3个键值对,所以它的初始长度len(m)是3。m1 := map[string]int{} //m1被初始化为一个空的m…...
机器人中的数值优化|【七】线性搜索牛顿共轭梯度法、可信域牛顿共轭梯度法
机器人中的数值优化|【七】线性搜索牛顿共轭梯度法、可信域牛顿共轭梯度法 Line Search Newton-CG, Trust Region Newton-CG 往期回顾 机器人中的数值优化|【一】数值优化基础 机器人中的数值优化|【二】最速下降法,可行牛顿法的python实现,以Rosenbro…...
websocket实现go(server)与c#(client)通讯
go 服务端 使用到github.com/gorilla/websocket package mainimport ("fmt""github.com/gorilla/websocket""log""net/http" )func main() {var upgrader websocket.Upgrader{ReadBufferSize: 1024,WriteBufferSize: 1024,CheckOr…...
使用xrdp实现Windows远程桌面无缝连接WSL2中的Ubuntu24.04
1. 为什么需要远程桌面连接WSL2? 很多开发者习惯在Windows系统上使用WSL2运行Ubuntu进行开发工作,但默认情况下WSL2只提供命令行界面。虽然大多数开发任务可以通过命令行完成,但有些场景下图形界面会更方便: 运行需要GUI的应用程…...
LeetCode 53. 最大子数组和 超详细题解(贪心+分治+动规)
LeetCode 53. 最大子数组和 超详细题解(贪心分治动规) 🏷️ 标签:动态规划、贪心算法、分治法、数组、经典面试题 📊 难度:简单 | 📝 题目编号:53 | 🗂️ 题型࿱…...
保姆级拆解:MIT-BEVFusion中Swin Transformer如何高效处理多相机图像(附代码逐行分析)
多相机BEV感知中的Swin Transformer实战:从原理到MIT-BEVFusion代码精要 在自动驾驶感知系统中,如何高效处理多相机输入并构建统一的鸟瞰视图(BEV)表征一直是核心挑战。本文将深入探讨Swin Transformer在多相机BEV感知中的创新应用…...
ROS2机械臂实战:ros2_control、MoveIt2与move_group核心问题排查指南
1. ROS2机械臂控制栈的核心组件解析 搞ROS2机械臂开发的朋友应该都熟悉这个经典组合:ros2_control负责硬件接口,MoveIt2处理运动规划,move_group作为执行层。这三个组件就像机械臂控制的"三驾马车",任何一个环节出问题都…...
web.py终极指南:开发者最关心的20个常见问题与解决方案
web.py终极指南:开发者最关心的20个常见问题与解决方案 【免费下载链接】webpy web.py is a web framework for python that is as simple as it is powerful. 项目地址: https://gitcode.com/gh_mirrors/we/webpy web.py是一个简单而强大的Python Web框架&…...
实战解析:基于防火墙与三层交换机的企业多业务VLAN安全组网
1. 企业多业务VLAN组网的核心价值 对于200-500人规模的中型企业来说,网络架构就像城市的交通系统。当办公区、研发中心、视频监控、服务器集群等业务单元都挤在同一个"马路"上时,网络拥堵和安全风险就会成为日常噩梦。我去年就遇到过一家制造…...
Word制表位全攻略:从菜鸟到高手,5分钟搞定专业文档排版
Word制表位全攻略:从菜鸟到高手,5分钟搞定专业文档排版 你是否曾经为了对齐文档中的文字而疯狂敲击空格键?或是花费大量时间调整表格边框却依然无法让数字完美对齐?这些困扰其实只需要掌握一个Word中的隐藏神器——制表位&#x…...
FineBI连接MySQL实战:手把手教你从零搭建第一个学生数据分析看板
FineBI连接MySQL实战:从零构建学生数据分析看板 当教务系统的学生信息沉睡在MySQL数据库中时,FineBI能像魔法师一样将它们唤醒为生动的可视化图表。我曾为某高校搭建第一个招生分析看板时,仅用三小时就让校领导看到了历年录取数据的立体画像—…...
ChatTTS合成速度优化实战:从音频流处理到并行计算
最近在项目中用到了ChatTTS进行语音合成,效果确实不错,但遇到一个很实际的问题:合成速度太慢,尤其是处理长文本时,等待时间让人有点抓狂。于是花了一些时间研究优化方案,把整个探索过程和最终落地的方案记录…...
全流程自动化知识图谱构建:从非结构化数据到智能决策支持
全流程自动化知识图谱构建:从非结构化数据到智能决策支持 【免费下载链接】llm-graph-builder Neo4j graph construction from unstructured data 项目地址: https://gitcode.com/GitHub_Trending/ll/llm-graph-builder 在信息爆炸的时代,企业如何…...
