5月7日监控二叉树+斐波那契数
968.监控二叉树
给定一个二叉树,我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。
示例 1:
输入:[0,0,null,0,0] 输出:1 解释:如图所示,一台摄像头足以监控所有节点。
示例 2:
输入:[0,0,null,0,null,0,null,null,0] 输出:2 解释:需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。
提示:
- 给定树的节点数的范围是
[1, 1000]
。 - 每个节点的值都是 0。
思路
想半天想不出来然后去看了各路大神的题解,对比之下发现官方题解的说法完全是在冒充人类。
首先我们先要确定从二叉树的下面往上看,为什么不自顶向下呢?因为头节点放不放摄像头也就省下一个摄像头,但是叶子节点放不放摄像头省下的是指数级的摄像头。
那么从下往上看我们首先想到的是二叉树的后序遍历法(左-右-中),所以本题我们使用递归法来解。
并且,如果要达成局部最优的话,我们一定是在叶子节点的父节点安装摄像头,让所用摄像头最少,达成全局最优。
所以,大体思路就是从低向上遍历二叉树,先给叶子节点父节点放摄像头,然后隔两个节点放一个摄像头,直到到根节点。
但是怎样隔两个节点放一个摄像头呢?此时我们就需要状态转移的公式来记录每个节点的状态。每个节点可能有三种状态:
0:该节点无覆盖
1:该节点有摄像头
2:该节点有覆盖
空节点一律视为有覆盖的情况,因为若把空节点视为无覆盖,那么空节点的父节点——叶子节点就必须放置一个摄像头,这与本意冲突;若把空节点视为有摄像头,那么叶子节点就为有覆盖,那么隔两个节点才会放一个摄像头,实际上没有监控到叶子节点,所以空节点只能视为有覆盖。
那么,对于每个节点的处理逻辑我们可以分为四类情况:
1、左右节点都有覆盖:该节点一定无覆盖
2、左右节点至少有一个无覆盖:该节点一定放摄像头
3、左右节点至少有一个摄像头:该节点一定有覆盖
4、头节点无覆盖:头节点再加一个摄像头。
代码
class Solution {int res=0;public int minCameraCover(TreeNode root) {return dfs(root)==0?res+1:res;}private int dfs(TreeNode node){if(node==null){return 2;}int left=dfs(node.left);int right=dfs(node.right);if(left==0||right==0){res++;return 1;}if(left==1||right==1){return 2;}return 0;}}
灵茶山艾府的思路我没理解,二刷的时候再研究。
509.斐波那契数
斐波那契数 (通常用 F(n)
表示)形成的序列称为 斐波那契数列 。该数列由 0
和 1
开始,后面的每一项数字都是前面两项数字的和。也就是:
F(0) = 0,F(1) = 1 F(n) = F(n - 1) + F(n - 2),其中 n > 1
给定 n
,请计算 F(n)
。
示例 1:
输入:n = 2 输出:1 解释:F(2) = F(1) + F(0) = 1 + 0 = 1
示例 2:
输入:n = 3 输出:2 解释:F(3) = F(2) + F(1) = 1 + 1 = 2
示例 3:
输入:n = 4 输出:3 解释:F(4) = F(3) + F(2) = 2 + 1 = 3
提示:
0 <= n <= 30
思路
经典递归解法:
class Solution {public int fib(int n) {if(n==1){return 1;}else if(n==0){return 0;}else {return fib(n-1)+fib(n-2);}}}
dp解法:
确定dp数组含义
dp[i]的定义为:第i个数的斐波那契数值为dp[i]
递推公式:dp[i] = dp[i - 1] + dp[i - 2];
初始化:dp[0]=0,dp[1]=1
代码
class Solution {public int fib(int n) {if (n <= 1) return n; int[] dp = new int[n + 1];dp[0] = 0;dp[1] = 1;for (int index = 2; index <= n; index++){dp[index] = dp[index - 1] + dp[index - 2];}return dp[n];}
}
空间复杂度可以进一步优化,因为不用维护整个dp数组:
class Solution {public int fib(int n) {if (n < 2) return n;int a = 0, b = 1, c = 0;for (int i = 1; i < n; i++) {c = a + b;a = b;b = c;}return c;}
}
相关文章:
5月7日监控二叉树+斐波那契数
968.监控二叉树 给定一个二叉树,我们在树的节点上安装摄像头。 节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。 计算监控树的所有节点所需的最小摄像头数量。 示例 1: 输入:[0,0,null,0,0] 输出:1 解释ÿ…...
C++类的设计编程示例
一、银行账户类 【问题描述】 定义银行账户BankAccount类。 私有数据成员:余额balance(整型)。 公有成员方法: 无参构造方法BankAccount():将账户余额初始化为0; 带参构造方法BankAccount(int m)࿱…...
YOLOv5 V7.0 - rknn模型的验证 输出精度(P)、召回率(R)、mAP50、mAP50-95
1.简介 RKNN官方没有提供YOLOv5模型的验证工具,而YOLOv5自带的验证工具只能验证pytorch、ONNX等常见格式的模型性能,无法运行rknn格式。考虑到YOLOv5模型转换为rknn会有一定的精度损失,但是需要具体数值才能进行评估,所以需要一个…...
CUDA、CUDNN、Pytorch三者之间的关系
这个东西嘛,我一开始真的是一头雾水,安装起来真是麻烦死了。但是随着要复现的项目越来越多,我也不得不去学会他们是什么,以及他们之间的关系。 首先,一台电脑里面允许有多种版本的cuda存在,然后cuda分为run…...
vue-cli2,vue-cli3,vite 生产环境去掉console.log
console.log一般都是在开发环境下使用的,在生产环境下需要去除 ,如果手动删除未免也太累了,我们可以用插件对于具体环境全局处理。 vue-cli2 项目build 下面webpack.prod.config.js 文件中: plugins: [new webpack.DefinePlugin({process.en…...
Docker-Compose编排LNMP并部署WordPress
前言 随着云计算和容器化技术的快速发展,使用 Docker Compose 编排 LNMP 环境已经成为快速部署 Web 应用程序的一种流行方式。LNMP 环境由 Linux、Nginx、MySQL 和 PHP 组成,为运行 Web 应用提供了稳定的基础。本文将介绍如何通过 Docker Compose 编排 …...
附录C:招聘流程
< 回到目录 附录C:招聘流程 _xxx_公司的招聘 使命 只雇佣顶级人才。 他们是能够胜任工作,并与 _(你的公司名称)_ 的企业文化相匹配的超级明星。 方法 记分卡。招聘经理创建一份文件,详细描述此职位的工作内容…...
1688快速获取整店铺列表 采集接口php Python
在电子商务的浪潮中,1688平台作为中国领先的批发交易平台,为广大商家提供了一个展示和销售商品的广阔舞台;然而,要在众多店铺中脱颖而出,快速获取商品列表并进行有效营销是关键。 竞争对手分析 价格比较:…...
CTF-WEB(MISC)
安全攻防知识——CTF之MISC - 知乎 CTF之MISC杂项从入门到放弃_ctf杂项 你的名字-CSDN博客 CTF MICS笔记总结_archpr 掩码攻击-CSDN博客 一、图片隐写 CTF杂项---文件类型识别、分离、合并、隐写_ctf图片分离-CSDN博客 EXIF(Exchangeable Image File)是…...
Ubuntu如何更换 PyTorch 版本
环境: Ubuntu22.04 WLS2 问题描述: Ubuntu如何更换 PyTorch 版本考虑安装一个为 CUDA 11.5 编译的 PyTorch 版本。如何安装旧版本 解决方案: 决定不升级CUDA版本,而是使用一个与CUDA 11.5兼容的PyTorch版本,您可…...
python flask css样式无效
解释: Flask是一个Python的轻量级Web框架,它没有为CSS提供任何内置的支持。如果你在Flask项目中引入了CSS文件,但是这个CSS没有生效,可能的原因有: 路径不正确:你的CSS文件没有放在正确的目录下࿰…...
大数据学习笔记14-Hive基础2
一、数据字段类型 数据类型 :LanguageManual Types - Apache Hive - Apache Software Foundation 基本数据类型 数值相关类型 整数 tinyint smallint int bigint 小数 float double decimal 精度最高 日期类型 date 日期 timestamps 日期时间 字符串类型 s…...
vue3 下载图片(包括多图片下载)
单图片下载 //使用 download(https://img1.baidu.com/it/u1493209339,2544178769&fm253&app138&sizew931&n0&fJPEG&fmtauto?sec1715101200&t854f3434686cfd2cba9d6a528597d15c)//下载逻辑 const download async (modelUrl) > {const respons…...
LabVIEW如何通过子VI更改主VI控件属性?
在LabVIEW中,可以通过使用Local Variable或Property Node来实现主VI控件属性的更改。这些方法可以在主VI和子VI之间传递数据和控件属性。 Local Variable: 使用Local Variable可以在子VI中直接访问并修改主VI中的控件属性。在子VI中创建Local Variable,并…...
关于MS-DOS时代的回忆
目录 一、MS-DOS是什么? 二、MS-DOS的主要功能有哪些? 三、MS-DOS的怎么运行的? 四、微软开源MS-DOS源代码 五、高手与漂亮女同学 一、MS-DOS是什么? MS-DOS(Microsoft Disk Operating System)是微软公…...
数据库索引(Mysql)
简述:数据库索引是加速数据检索,提高查询效率的一种数据结构 语法规则 创建索引 --通用语法规则 --[内容] 可选参数 --UNIQUE: 可选关键字,用于创建唯一索引,确保索引列的值是唯一的 CREATE [UNIQUE] INDEX 索引名 ON 表名(字段名,...) [ASC | DESC];…...
异常-Exception
异常介绍 基本概念 Java语言中,将程序执行中发生的不正常情况称为“异常”。(开发过程中的语法错误和逻辑错误不是异常)执行过程中所发生的异常事件可分为两大类 1,Error(错误):Java虚拟机无法…...
ctfshow——SQL注入
文章目录 SQL注入基本流程普通SQL注入布尔盲注时间盲注报错注入——extractvalue()报错注入——updataxml()Sqlmap的用法 web 171——正常联合查询web 172——查看源代码、联合查询web 173——查看源代码、联合查询web 174——布尔盲注web 176web 177——过滤空格web 178——过…...
第十三章 计算机网络
这里写目录标题 1.网络设备2.协议簇2.1电子邮件(传输层)2.2地址解析(网际层)2.3DHCP(动态主动配置协议)2.4URL(统一资源定位器)2.5IP地址和子网掩码 1.网络设备 物理层:中继器,集线器(多路中继器) 数据链路层:网桥,交换机(多端口…...
商品详情 API 返回值说明
商品详情API接口在多个领域和场景中都有广泛的应用,以下是一些常见的应用场景: 竞品分析:企业可以利用商品详情API接口获取竞品的所有详细信息,如价格、发货地、上架时间、销售量等。通过分析这些竞品信息,企业可以更…...
层级实例化静态网格体组件:开启大量模型处理之门
前言 在数字孪生的世界里,我们常常需要构建大量的模型来呈现真实而丰富的场景。然而,当使用静态网格体 (StaticMesh )构建大量模型时,可能会遇到卡顿的问题,这给我们带来了不小的困扰😣。那么&…...
【网络知识】光猫、路由器 和 交换机 的作用和区别?
数字信号:是指自变量是离散的、因变量也是离散的信号,这种信号的自变量用整数表示,因变量用有限数字中的一个数字来表示。在计算机中,数字信号的大小常用有限位的二进制数表示。 模拟信号:模拟信号是指用连续变化的物…...
初识Electron,创建桌面应用
历史小剧场 呜呼!古有匈奴犯汉,晋室不纲,铁木夺宋,虏清入关,神舟陆沉二百年有余,中国之见灭于满清初非满人能灭之,能有之也因有汉奸以作虎怅,残同胞媚异种,始有吴三桂洪承…...
AI编码时代到来?实现编程梦想的利器—Baidu Comate测评
文章目录 Comate智能编码是什么?Comate支持的环境 Comate应用安装实际操作对话式生成代码生成代码注释智能单测项目测试调优功能 总结 Comate智能编码是什么? 在如今这个拥抱AI的时代,市面上已经产出了很多Ai代码助手,如果你还没…...
去中心化自治组织(DAO)
文章目录 一、DAO (Decentralized Autonomous Organization) 去中心化自治组织 二、举例说明 1、例子1 2、例子2 总结 一、DAO (Decentralized Autonomous Organization) 去中心化自治组织 DAO是一种基于区块链平台上的组织结构,它通过智能合约来实现组织的…...
MySQL之多表查询
1. 前言 多表查询,也称为关联查询.指两个或两个以上的表一起完成查询操作.前提条件 : 这些一起查询的表之间是有关系的(一对一/一对多).他们之间一定是有关联字段,这个关联字段可能建立了外键,也可能没有建立外键. 2. 笛卡尔积现象(交叉连接…...
极端天气频发,我们普通人如何保全自己
随着全球气候变暖的加剧,极端天气事件如同一位不请自来的“不速之客”,频繁地闯入我们的生活。暴风雨、暴风雪、台风、干旱、热浪等极端天气现象,不仅给人们的生命和财产安全带来了前所未有的挑战,更对社会的正常秩序构成了严重威…...
直面市场乱价,品牌商家该如何解决?
在当今的商业世界中,品牌商面临着一系列严峻挑战,其中如何有效管理经销商价格是一个关键难题。经销商随意调整价格的行为,不仅会损害品牌的信誉与形象,还可能导致市场秩序混乱,使品牌利润大幅缩水。因此,采…...
Spring中的Bean相关理解
在Spring框架中,Bean是一个由Spring IoC容器实例化、配置和管理的对象。Bean是一个被Spring框架管理并且被应用程序各个部分所使用的对象。Spring IoC容器负责Bean的创建、初始化、依赖注入以及销毁等生命周期管理。 注:喜欢的朋友可以关注公众号“JAVA学…...
操作系统实战(二)(linux+C语言)
实验内容 通过Linux 系统中管道通信机制,加深对于进程通信概念的理解,观察和体验并发进程间的通信和协作的效果 ,练习利用无名管道进行进程通信的编程和调试技术。 管道pipe是进程间通信最基本的一种机制,两个进程可以通过管道一个在管道一…...
哪些情况下会触发MySQL的预读机制?
MySQL的预读机制主要与其底层存储引擎的实现有关,尤其是InnoDB存储引擎。预读(Pre-reading)或预取(Prefetching)是一种性能优化技术,其中数据库系统主动读取可能很快就会被查询到的数据页到缓冲池ÿ…...
react使用谷歌人机验证
在项目中,需要对请求验证,防止被爆破,这里使用的是谷歌的recaptcha-v3。 1.申请谷歌人机验证的api 申请链接,申请完后需要将两个谷歌颁发的key分别写入前,后端的配置环境中,后面会使用. 2.前端部分 前端使用的是viteC…...
java JMH 学习
JMH 是什么? JMH(Java Microbenchmark Harness)是一款专用于代码微基准测试的工具集,其主要聚焦于方法层面的基准测试,精度可达纳秒级别。此工具由 Oracle 内部负责实现 JIT 的杰出人士编写,他们对 JIT 及…...
本地运行AI大模型简单示例
一、引言 大模型LLM英文全称是Large Language Model,是指包含超大规模参数(通常在十亿个以上)的神经网络模型。2022年11月底,人工智能对话聊天机器人ChatGPT一经推出,人们利用ChatGPT这样的大模型帮助解决很多事情&am…...
图像处理:时域、空域、频率的滤波介绍
首先要搞清楚为什么会呈现出不同域的维度,来理解和处理图像,原因是图像的构成有多个维度的信息特点。比如一段视频从时间顺序来看,相邻的2个图像帧绝大部分信息是相同的,这就构成了前向预测的理论基础;比如一帧图像从空…...
TC8002D 是一颗带关断模式的音频功放IC
一、一般概述 TC8002D是一颗带关断模式的音频功放IC。在5V输入电压下工作时,负载(3Ω)上的平均功率 为3 W,且失真度不超过10%。而对于手提设备而言,当VDD作用于关断端时,TC8002D将会进入关断模式,此时的功耗极…...
深度学习之基于Vgg19预训练卷积神经网络图像风格迁移系统
欢迎大家点赞、收藏、关注、评论啦 ,由于篇幅有限,只展示了部分核心代码。 文章目录 一项目简介 二、功能三、系统四. 总结 一项目简介 一、项目背景 在数字艺术和图像处理领域,图像风格迁移技术一直备受关注。该技术可以将一幅图像的内容和…...
MySQL:多表查询练习
#1.出版社信息 与 图书信息 交叉连接 select * from 出版社信息 cross join 图书信息; #2.从“客户信息”和“订单信息”两张数据表中查询购买了商品的客户信息,要求查询结果显示客户姓名、订单编号、订单状态。 select 客户信息.客户姓名,订单信息.订单编号,订单…...
# 从浅入深 学习 SpringCloud 微服务架构(八)Sentinel(1)
从浅入深 学习 SpringCloud 微服务架构(八)Sentinel(1) 一、sentinel:概述 1、前言 – 服务熔断 Hystrix 的替换方案。 1)2018年底 Netflix 官方宣布 Hystrix 已经足够稳定,不再积极开发 Hys…...
[微信小程序] 入门笔记2-自定义一个显示组件
[微信小程序] 入门笔记2-自定义一个显示组件 0. 准备工程 新建一个工程,删除清空app的内容和其余文件夹.然后自己新建pages和components创建1个空组件和1个空页面. 设定 view 组件的默认样式,使其自动居中靠上,符合习惯.在app.wxss内定义,作用做个工程. /**app.wxss**/ /* 所…...
YOLO代码复现
睿智的目标检测66——Pytorch搭建YoloV8目标检测平台_pytorch_quantization yolov8-CSDN博客 Mask rcnn代码实现_pytorch版_适用30系列显卡_mask rcnn 30显卡-CSDN博客 完整且详细的Yolov8复现训练自己的数据集-CSDN博客...
使用fitten code插件(vscode),替换通义千问,识别需求中的输入输出
今天我们介绍一个工具,具体介绍可以参考我的这篇文章的介绍,支持vs code 插件,Fitten Code是一款由非十科技开发的AI代码助手,旨在通过大模型驱动来提升编程效率和体验-免费神器-CSDN博客https://blog.csdn.net/lijigang100/article/details/137833223?spm=1001.2014.3001…...
vue使用pdfjs-dist在电脑上展示PDF文件
安装 安装的时候一定要带上版本号,这里采用的是2.0.943(因为这个版本对于我目前的项目比较合适可以正常使用,其他版本大概率会报错),当前项目使用的是vue2,vue的版本是2.5.10 npm install pdfjs-dist@2.0.943 查看版本发现这玩意版本非常之多 使用 在使用pdfjs-dist库…...
【网站项目】戒烟网站
🙊作者简介:拥有多年开发工作经验,分享技术代码帮助学生学习,独立完成自己的项目或者毕业设计。 代码可以私聊博主获取。🌹赠送计算机毕业设计600个选题excel文件,帮助大学选题。赠送开题报告模板ÿ…...
慢性软组织疼痛如何使用DMS深层肌肉刺激仪进行治疗?
使用DMS深层肌肉刺激仪治疗慢性软组织疼痛,可以遵循以下步骤: 准备工作:首先,确保DMS设备已经充电或插上电源,并根据需要调整振动强度和频率。DMS深层肌肉刺激仪是通过快速连续的振动和打击来刺激深层肌肉的设备&#…...
自动化测试常用工具
自动化测试工具是非常重要的。自动化测试工具可以帮助程序员提高工作效率,减少重复劳动和人为错误,提高产品质量。下面我将介绍几个常用的自动化测试工具。 Selenium:Selenium是一个开源的自动化测试框架,用于Web应用程序的自动化…...
【Osek网络管理测试】[TG4_TC4]tWaitBusSleep
🙋♂️ 【Osek网络管理测试】系列💁♂️点击跳转 文章目录 1.环境搭建2.测试目的3.测试步骤4.预期结果5.测试结果1.环境搭建 硬件:VN1630 软件:CANoe 2.测试目的 验证DUT的tWBS时间参数是否符合NM标准 本处规定tWBS在[1350ms,1650ms]范围内符合要求 3.测试步骤…...
java08基础(值传递和引用传递 类和对象)
目录 一. 值传递和引用传递 1. 值传递 2. 引用传递 二. 面向对象思想 三. 类和对象 1. 类 2. 对象 2.1 使用 2.2 成员变量和局部变量区别 2.3 操作成员方法 2.4 this关键字(初识) 2.5 构造方法 (见java09) 一. 值传递和引用传递 1. 值传递 值传递是指在调用函数时将…...
高级数据结构与算法习题(9)
一、判断题 1、Let S be the set of activities in Activity Selection Problem. Then the earliest finish activity am must be included in all the maximum-size subset of mutually compatible activities of S. T F 解析:F。设S是活动选择问题中的一…...
Linux的vim下制作进度条
目录 前言: 回车和换行有区别吗? 回车和换行的区别展示(这个我在Linux下演示) 为什么会消失呢? 回车和换行的区别 为什么\r和\n产生的效果不同? 打印进度条: (1)打印字符串 …...