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

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

题目描述 小偷又发现了一个新的可行窃的地区。这个地区只有一个入口&#xff0c;我们称之为 root 。 除了 root 之外&#xff0c;每栋房子有且只有一个“父“房子与之相连。一番侦察之后&#xff0c;聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两…...

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属性&#x1f496; 输入的光标位置&#xff08;浏览器获取selection&#xff09;⭐使用Selection.toString () 返回指定的文本⭐getRangeAt 获取指定索引范围 &#x1f496; 修改光标位置&#x1f496; 设置选取range ⭐总结⭐结束 ⭐前…...

堆--数据流中第K大元素

如果对于堆不是太认识&#xff0c;请点击&#xff1a;堆的初步认识-CSDN博客 数据流与上述堆--数组中第K大元素-CSDN博客的数组区别&#xff1a; 数据流的数据是动态变化的&#xff0c;数组是写死的 堆--数组中第K大元素-CSDN博客题的小顶堆加一个方法&#xff1a; class MinH…...

【算法|动态规划No.12】leetcode152. 乘积最大子数组

个人主页&#xff1a;兜里有颗棉花糖 欢迎 点赞&#x1f44d; 收藏✨ 留言✉ 加关注&#x1f493;本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 &#x1f354;本专栏旨在提高自己算法能力的同时&#xff0c;记录一下自己的学习过程&#xff0c;希望…...

Covert Communication 与选择波束(毫米波,大规模MIMO,可重构全息表面)

Covert Communication for Spatially Sparse mmWave Massive MIMO Channels 2023 TOC abstract 隐蔽通信&#xff0c;也称为低检测概率通信&#xff0c;旨在为合法用户提供可靠的通信&#xff0c;并防止任何其他用户检测到合法通信的发生。出于下一代通信系统安全链路的强烈…...

计算机毕业设计 基于协调过滤算法的绿色食品推荐系统的设计与实现 Java实战项目 附源码+文档+视频讲解

博主介绍&#xff1a;✌从事软件开发10年之余&#xff0c;专注于Java技术领域、Python人工智能及数据挖掘、小程序项目开发和Android项目开发等。CSDN、掘金、华为云、InfoQ、阿里云等平台优质作者✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精…...

华为云云耀云服务器L实例评测|部署在线影音媒体系统 Jellyfin

华为云云耀云服务器L实例评测&#xff5c;部署在线影音媒体系统 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实现

论文&#xff1a;https://arxiv.org/abs/1911.11907 源码&#xff1a;https://github.com/huawei-noah/ghostnet 简要论述GhostNet的核心内容。 Ghost Net 1、Introduction 在训练良好的深度神经网络的特征图中&#xff0c;丰富甚至冗余的信息通常保证了对输入数据的全面理…...

视频二维码的制作方法,支持内容修改编辑

现在学生经常会需要使用音视频二维码&#xff0c;比如外出打开、才艺展示、课文背诵等等。那么如何制作一个可以长期使用的二维码呢&#xff1f;下面来给大家分享一个二维码制作&#xff08;免费在线二维码生成器-二维码在线制作-音视频二维码在线生成工具-机智熊二维码&#x…...

清华GLM部署记录

环境部署 首先安装anaconda&#xff08;建议包管理比较方便&#xff09;windows用户需手动配置一下环境变量&#xff0c;下面默认是在ubuntu环境说明创建python环境&#xff0c;conda create -n your_env_name python3.10 (注&#xff1a;官方是提供是python3.8&#xff0c;但…...

贪心算法+练习

正值国庆之际&#xff0c;祝愿祖国繁荣昌盛&#xff0c;祝愿朋友一生平安&#xff01;终身学习&#xff0c;奋斗不息&#xff01; 目录 1.贪心算法简介 2.贪心算法的特点 3.如何学习贪心算法 题目练习&#xff08;持续更新&#xff09; 1.柠檬水找零&#xff08;easy&…...

使用华为eNSP组网试验⑷-OSPF多区域组网

今天进行了OSPF的多区域组网试验&#xff0c;本来这是个很简单的操作&#xff0c;折腾了好长时间&#xff0c;根本原因只是看了别人写的配置代码&#xff0c;没有真正弄明白里面对应的规则。 一般情况下&#xff0c;很多单位都使用OSPF进行多区域的组网&#xff0c;大体分为1个…...

P1843 奶牛晒衣服 【贪心】

P1843 奶牛晒衣服 【贪心】 题目背景 熊大妈决定给每个牛宝宝都穿上可爱的婴儿装 。但是由于衣服很湿&#xff0c;为牛宝宝晒衣服就成了很不爽的事情。于是&#xff0c;熊大妈请你&#xff08;奶牛&#xff09;帮助她完成这个重任。 题目描述 一件衣服在自然条件下用一秒的时间…...

91、Redis - 事务 与 订阅-发布 相关的命令 及 演示

★ 事务相关的命令 Redis事务保证事务内的多条命令会按顺序作为整体执行&#xff0c;其他客户端发出的请求绝不可能被插入到事务处理的中间&#xff0c; 这样可以保证事务内所有命令作为一个隔离操作被执行。 Redis事务同样具有原子性&#xff0c;事务内所有命令要么全部被执…...

GPU如何成为AI的加速器

0. 前言 按照国际惯例&#xff0c;首先声明&#xff1a;本文只是我自己学习的理解&#xff0c;虽然参考了他人的宝贵见解&#xff0c;但是内容可能存在不准确的地方。如果发现文中错误&#xff0c;希望批评指正&#xff0c;共同进步。 本文关键词&#xff1a;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 往期回顾 机器人中的数值优化|【一】数值优化基础 机器人中的数值优化|【二】最速下降法&#xff0c;可行牛顿法的python实现&#xff0c;以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…...

洛谷题目题解详细解答

洛谷是一个很不错的刷题软件&#xff0c;可是找不到合适的题解是个大麻烦&#xff0c;大家有啥可以私信问我&#xff0c;以下是我已经通过的题目。 你如果有哪一题不会&#xff08;最好是我通过过的&#xff0c;我没过的也没关系&#xff09;&#xff0c;可以私信我&#xff0…...

【C语言】八大排序算法

文章目录 一、冒泡排序1、定义2、思想及图解3、代码 二、快速排序1、hoare版本2、挖坑法3、前后指针法4、非递归快排5、快速排序优化1&#xff09;三数取中选key值2&#xff09;小区间优化 三、直接插入排序1、定义2、代码 四、希尔排序1、定义2、图解3、代码 五、选择排序1、排…...

2023年中国智能电视柜产量、需求量、市场规模及行业价格走势[图]

电视柜是随着电视机的发展和普及而演变出的家具种类&#xff0c;其主要作用是承载电视机&#xff0c;又称视听柜&#xff0c;随着生活水平的提高&#xff0c;与电视机相配套的电器设备也成为电视柜的收纳对象。 随着智能家具的发展&#xff0c;智能电视机柜的造型和风格都是有了…...

docker容器使用初体验

我们写程序时&#xff0c;都会搭建相关的环境&#xff0c;比如写了一个web&#xff0c;使用了tomcat、nginx等&#xff0c;现在想要把程序部署到云服务器或者在其他电脑上运行&#xff0c;就需要重新部署一遍环境&#xff0c;尤其是项目开源后&#xff0c;上手成本大。 docker…...

React Hooks ——性能优化Hooks

什么是Hooks Hooks从语法上来说是一些函数。这些函数可以用于在函数组件中引入状态管理和生命周期方法。 React Hooks的优点 简洁 从语法上来说&#xff0c;写的代码少了上手非常简单 基于函数式编程理念&#xff0c;只需要掌握一些JavaScript基础知识与生命周期相关的知识不…...

C#学习系列相关之多线程(一)----常用多线程方法总结

一、多线程的用途 在介绍多线程的方法之前首先应当知道什么是多线程&#xff0c; 在一个进程内部可以执行多个任务&#xff0c;而这每一个任务我们就可以看成是一个线程。是程序使用CPU的基本单位。进程是拥有资源的基本单位&#xff0c; 线程是CPU调度的基本单位。多线程的作用…...

Vscode爆红Delete `␍`eslintprettier/prettier

一、先看报错 文件中爆红&#xff0c;提示 Delete ␍eslintprettier/prettier 二、解决方案 项目根目录下&#xff0c;.prettierrc.js 文件中&#xff1a; endOfLine: auto,三、重启VsCode 此时不在爆红&#xff0c;问题完美解决...

Mac安装Ecplise产品报错:dose not contain the JNI_CreateJavaVM symbol

1. 絮絮叨叨 工作中需要借助Ecplise Memory Analyzer (MAT)分析dump文件&#xff0c;直接下载、安装、运行MAT报错 询问同事后&#xff0c;同事说可以先安装Ecplise&#xff0c;再以插件的形式安装MAT下载、安装好Eclipse&#xff0c;点击运行仍然报错&#xff0c;且错误信息一…...

如何使用大语言模型来绘制图画

请创作一张科技感十足的图片&#xff0c;包含siri和iphone两个元素&#xff0c;请帮我挑选合适的style和background 好的&#xff0c;我会为你创作一张科技感十足的图片&#xff0c;包含siri和iphone两个元素。我会根据你的要求&#xff0c;选择一种适合的风格和背景。请稍等一…...

代码随想录算法训练营第23期day11 | 20. 有效的括号、1047. 删除字符串中的所有相邻重复项 、150. 逆波兰表达式求值

目录 一、&#xff08;leetcode 20&#xff09;有效的括号 二、&#xff08;leetcode 1047&#xff09;删除字符串中的所有相邻重复项 用栈存放 将字符串直接当成栈 三、&#xff08;leetcode 150&#xff09;逆波兰表达式求值 一、&#xff08;leetcode 20&#xff09;…...

网站制作专业/百度网站登录

运算符 算数运算符 1.四则运算 - * / 2.取模 % &#xff08;只要整数除法&#xff0c;取模运算符在有意义&#xff09; 注意 1.一旦运算中&#xff0c;有不同类型的数据&#xff0c;那么结果将会是数据范围大的那种。 double result1 2 2.5//4.52.’‘有2种用法 A 加法 (…...

做网站每月收入/网络公司网络营销推广方案

什么是Buffer&#xff1f; 缓冲区Buffer是暂时存放输入输出数据的一段内存。Buffer是十六进制。JS语言没有二进制数据类型&#xff0c;而在处理TCP和文件流的时候&#xff0c;必须要处理二进制数据。所以&#xff0c;其实我们的node是把数据从二进制转换成了十六进制NodeJS提供…...

东莞建站模板公司/谷歌搜索引擎网址

Dlink所出品的家庭网关类产品&#xff08;DI-5xx、DI-6xx、DI-7xx、DI-8xx系列&#xff0c;以及新推出的DIR系列&#xff0c;但DI-60xLB/LB/HB系列除外&#xff09;在使用PPPoE设置中&#xff0c;均有“联机方式”&#xff08;共有三种可选&#xff1a;自动联机/手动联机/有流量…...

github wordpress ios/武汉seo引擎优化

端口号标识了一个主机上进行通信的不同的应用程序。1.HTTP协议代理服务器常用端口号&#xff1a;80/8080/3128/8081/90982.SOCKS代理协议服务器常用端口号&#xff1a;10803.FTP&#xff08;文件传输&#xff09;协议代理服务器常用端口号&#xff1a;214.Telnet&#xff08;远…...

做网站要哪些技术/黑马培训机构可靠吗

滑块区间组件 功能需求&#xff1a; 最小值为0&#xff0c;按照给定的最大值&#xff0c;生成区间范围&#xff1b;拖动滑块移动时&#xff0c;显示相应的范围区间&#xff0c;滑块条显示对应的状态&#xff1b;点击时&#xff0c;使最近的滑块移动到鼠标点击的位置。 默认效…...

微信小程序和网页哪个开发难/搜索引擎优化方法案例

收到设计&#xff0c;需要检查内容是否完整。 1.拓扑&#xff1a;设备数量&#xff0c;特别是本次所涉及的新增设备的类型与数量。&#xff08;新增设备、利旧设备&#xff1b;板块数&#xff0c;刀片数&#xff09; 设备连接关系&#xff0c;是否标明各个设备之间的连接的线缆…...