2024.2.29力扣每日一题——统计可能的树根数目
2024.2.29
- 题目来源
- 我的题解
- 方法一 深度搜索(暴力) 超时
- 方法二 树形动态规划
题目来源
力扣每日一题;题序:2581
我的题解
方法一 深度搜索(暴力) 超时
- 以每个节点node为跟进行深度搜索,并在搜索过程中记录前驱节点,然后判断[前驱节点,当前节点]是否在guesses中出现。若出现,则表示Bob猜测对一次,并记录在count数组中。最后遍历count数组,看有多少满足count[i]>=k。该值就是可能成为树根的 节点数目
时间复杂度:O( n ( n + e ) n(n+e) n(n+e))。n表示树的节点数,e表示树的边数
空间复杂度:O(n)
class Solution {//为了快速判断[u,v]对是否存在,连接成字符串ListList<String> guess=new ArrayList<>();//记录以节点i为根,用户猜对的次数,当然由于在过程中进行了截断,所以最大值为kint[] count;public int rootCount(int[][] edges, int[][] guesses, int k) {int n=edges.length+1;count=new int[n];List<Integer>[] g=createGraph(n,edges);for(int[] t:guesses){int u = t[0];int v = t[1];guess.add(u+"-"+v);}for(int i=0;i<n;i++){dfs(i,i,g,-1,k);}int res=0;for(int i=0;i<n;i++){if(count[i]>=k)res++;}return res;}//深度优先搜索public void dfs(int root,int cur,List<Integer>[] g,int pre,int k){//根节点没有父节点if(pre!=-1){String t=pre+"-"+cur;//Bob猜测正确if(guess.contains(t))count[root]++;//截断,当已经正确的次数达到k,表明以root为根一定满足if(count[root]>=k)return;}for(int next:g[cur]){//防止循环遍历if(next!=pre){dfs(root,next,g,cur,k);}}}//构建树public List<Integer>[] createGraph(int n,int[][] edges){List<Integer>[] g=new ArrayList[n];for(int i=0;i<n;i++){g[i]=new ArrayList<>();}for(int[] t:edges){int from=t[0];int to = t[1];g[from].add(to);g[to].add(from);}return g;}
}
//优化版本,但是还是超时
// 利用了如下的结论进行优化。
//基于已经计算出以 x 为树根时猜对的次数,很容易就可以计算出以 y 为树根时猜对的次数:
//如果 (x,y) 存在于 guesses,猜对次数减一;
//如果 (y,x) 存在于 guesses,猜对次数加一。class Solution {List<String> guess=new ArrayList<>();int cnt=0;int res=0;public int rootCount(int[][] edges, int[][] guesses, int k) {int n=edges.length+1;// count=new int[n];List<Integer>[] g=createGraph(n,edges);for(int[] t:guesses){int u = t[0];int v = t[1];guess.add(u+"-"+v);}dfs(0,0,g,-1,k);rdfs(g,0,-1,k,cnt);return res;}public void rdfs(List<Integer>[] g,int x,int t,int k,int cnt){if(cnt>=k){res++;}for(int y:g[x]){if(t==y)continue;rdfs(g,y,x,k,cnt-(guess.contains(x+"-"+y)?1:0)+(guess.contains(y+"-"+x)?1:0));}}public void dfs(int root,int cur,List<Integer>[] g,int pre,int k){if(pre!=-1){String t=pre+"-"+cur;if(guess.contains(t))cnt++;}for(int next:g[cur]){if(next!=pre){dfs(root,next,g,cur,k);}}}public List<Integer>[] createGraph(int n,int[][] edges){List<Integer>[] g=new ArrayList[n];for(int i=0;i<n;i++){g[i]=new ArrayList<>();}for(int[] t:edges){int from=t[0];int to = t[1];g[from].add(to);g[to].add(from);}return g;}
}
方法二 树形动态规划
看官方题解吧,弄不明白
终于补完2月的每日一题了。😄
有任何问题,欢迎评论区交流,欢迎评论区提供其它解题思路(代码),也可以点个赞支持一下作者哈😄~
相关文章:
2024.2.29力扣每日一题——统计可能的树根数目
2024.2.29 题目来源我的题解方法一 深度搜索(暴力) 超时方法二 树形动态规划 题目来源 力扣每日一题;题序:2581 我的题解 方法一 深度搜索(暴力) 超时 以每个节点node为跟进行深度搜索,并在搜…...
同一个主机配置多个SSH key
使用git时,我们可能一个git客户端使用多个git服务器,比如github,自建gitlab,gitee,为了防止提交混乱,所以需要一一对应生成公私钥。 第一步: 使用ssh-keygen生成多对密钥对,比如&…...
SAP系统财务模块简介:实现财务管理的卓越之道
作为全球领先的企业管理软件提供商,SAP公司开发了一系列强大而全面的财务模块,帮助企业实现财务管理的高效运作与优化。SAP系统的财务模块涵盖了财务核算、成本管理、资金管理、资产会计等多个方面,为企业提供了完整的财务管理解决方案。本文…...
【pytest】功能特性及常用插件
pytest是一个功能强大的Python测试框架,它的语法简洁明了,易于学习和使用。同时,它提供了丰富的功能和插件,使得测试过程更加灵活和高效。 功能特性 pytest的主要功能特性包括: 参数化测试:允许使用不同…...
基于SpringBoot和Vue的房产销售系统的设计与实现
今天要和大家聊的是一款基于SpringBoot和Vue的房产销售系统的设计与实现 !!! 有需要的小伙伴可以通过文章末尾名片咨询我哦!!! 💕💕作者:李同学 💕…...
ROS2从入门到精通1-2:详解ROS2服务通信机制与自定义服务
目录 0 专栏介绍1 服务通信模型2 服务模型实现(C)3 服务模型实现(Python)4 自定义服务5 话题、服务通信的异同 0 专栏介绍 本专栏旨在通过对ROS2的系统学习,掌握ROS2底层基本分布式原理,并具有机器人建模和应用ROS2进行实际项目的开发和调试的工程能力。…...
vue两个特性和什么是MVVM
一、什么是vue 1.构建用户界面 用vue往html页面中填充数据,非常的方便 2.框架 框架是一套线成的解决方案 vue的指令、组件(是对ui结构的复用)、路由、vuex 二、vue的特性 1.数据驱动视图 2.双向数据绑定 1.数据驱动视图 数据的变化会驱动…...
CAD Plant3D 2023 下载地址及安装教程
CAD Plant3D是一款专业的三维工厂设计软件,用于在工业设备和管道设计领域进行建模和绘图。它是Autodesk公司旗下的AutoCAD系列产品之一,专门针对工艺、石油、化工、电力等行业的设计和工程项目。 CAD Plant3D提供了一套丰富的工具和功能,帮助…...
集成电路企业tapeout,如何保证机台数据准确、完整、高效地采集?
Tapeout即流片,集成电路行业中将CDS最终版电路图提交给半导体制造厂商进行物理生产的过程。在芯片设计与制造的流程中,Tapeout是非常重要的阶段,包括了布局(Layout)、连线(Routing)、分析&#…...
Nginx三大常用功能“反向代理,负载均衡,动静分离”
注意:以下案例在Windows系统计算机作为宿主机,Linux CentOS 作为虚拟机的环境中实现 一,Nginx配置实例-反向代理 1.反向代理 案例一 实现效果:使用nginx反向代理,访问 www.123.com 直接跳转到127.0.0.1:8080 准备工…...
类方法介绍、使用细节
...
Java SpringBoot中优雅地判断一个对象是否为空
在Java中,可以使用以下方法优雅地判断一个对象是否为空: 使用Objects.isNull()方法判断对象是否为空: import java.util.Objects;if (Objects.isNull(obj)) {// obj为空的处理逻辑 }使用Optional类优雅地处理可能为空的对象: impo…...
算法——矩阵:对于边界元素的处理
. - 力扣(LeetCode) 题目简述:扫雷,点击一个格子,返回整个地图的下一个状态。 对于边界元素,可以设置两个数组,index_row,index_col,遍历到一个格子需要搜索其周围格子…...
Git分支提交时自动大写 fatal: the remote end hung up unexpectedly
先说结论: 进入 .git/refs/heads目录,会看到Feature文件夹,重命名为feature即可。 表现: 通过终端命令创建的分支 git checkout -b feature/name 使用git push后自动变成了Feature/name 并且有时候在本地创建feature/1234567…...
隐私计算实训营第七讲-隐语SCQL的架构详细拆解
隐私计算实训营第七讲-隐语SCQL的架构详细拆解 文章目录 隐私计算实训营第七讲-隐语SCQL的架构详细拆解1.SCQL Overview1.1 多方数据分析场景1.2 多方数据分析技术路线1.2.1 TEE SQL方案1.2.2 MPC SQL方案 1.3 Secure Collaborative Query Language(SCQL)1.3.1 SCQL 系统组件1.…...
Android JNI开发定义全局变量
要在 C 文件中设置一个 string 类型的全局变量,让其他 C 文件都可以访问,并且可以通过 JNI 方法修改这个变量,可以按照以下步骤进行操作 定义全局变量: 在一个头文件(比如 common.h)中定义一个全局的 strin…...
docker容器部署gitlab的runner的shell模式注册下job中无法使用docker指令
引言 现需通过gitlab-runner来构建jar部署的镜像,发现在job中无法使用docker指令,解决的过程中出现一系列异常,在此做个问题解决的记录。 内容 通过docker-compose部署 name: java-env services:env-gitlab-runner:restart: alwaysimage: env/gitlab-runner-java:latest…...
【SpringCloud】Zuul网关中心 代码详细介绍
Zuul是Spring Cloud中的一个API网关组件,它负责处理服务路由、监控、弹性、安全等API网关的核心功能。Zuul在Spring Cloud Netflix套件中是一个重要的组件,但需要注意的是,随着Spring Cloud的不断发展,Zuul已经被Spring Cloud Gat…...
Delphi D12中实现安卓中文语音合成(中文朗读)不用第三方控件
Delphi开发一个可以朗读中文的APP就非常的简单。 本文给大家介绍使用Delphi开发基于安卓原生的TTS(中文语音合成),将文字转语音实现中文的朗读。APP运行后,需要手机上已安装语音引擎。如果您手机上已安装并设置了语音引擎…...
设计模式 - Provider 模式
在某些情况下,我们希望为应用程序中的许多(如果不是全部)组件提供数据。尽管我们可以使用 props 将数据传递给组件,但如果应用程序中的几乎所有组件都需要访问 prop 的值,这可能很难做到。 我们经常遇到所谓的属性钻探…...
PAN/FPN
import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...
面向无人机海岸带生态系统监测的语义分割基准数据集
描述:海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而,目前该领域仍面临一个挑战,即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...
解读《网络安全法》最新修订,把握网络安全新趋势
《网络安全法》自2017年施行以来,在维护网络空间安全方面发挥了重要作用。但随着网络环境的日益复杂,网络攻击、数据泄露等事件频发,现行法律已难以完全适应新的风险挑战。 2025年3月28日,国家网信办会同相关部门起草了《网络安全…...
c# 局部函数 定义、功能与示例
C# 局部函数:定义、功能与示例 1. 定义与功能 局部函数(Local Function)是嵌套在另一个方法内部的私有方法,仅在包含它的方法内可见。 • 作用:封装仅用于当前方法的逻辑,避免污染类作用域,提升…...
Linux 下 DMA 内存映射浅析
序 系统 I/O 设备驱动程序通常调用其特定子系统的接口为 DMA 分配内存,但最终会调到 DMA 子系统的dma_alloc_coherent()/dma_alloc_attrs() 等接口。 关于 dma_alloc_coherent 接口详细的代码讲解、调用流程,可以参考这篇文章,我觉得写的非常…...
从零手写Java版本的LSM Tree (一):LSM Tree 概述
🔥 推荐一个高质量的Java LSM Tree开源项目! https://github.com/brianxiadong/java-lsm-tree java-lsm-tree 是一个从零实现的Log-Structured Merge Tree,专为高并发写入场景设计。 核心亮点: ⚡ 极致性能:写入速度超…...
Android Framework预装traceroute执行文件到system/bin下
文章目录 Android SDK中寻找traceroute代码内置traceroute到SDK中traceroute参数说明-I 参数(使用 ICMP Echo 请求)-T 参数(使用 TCP SYN 包) 相关文章 Android SDK中寻找traceroute代码 设备使用的是Android 11,在/s…...
qt 双缓冲案例对比
双缓冲 1.双缓冲原理 单缓冲:在paintEvent中直接绘制到屏幕,绘制过程被用户看到 双缓冲:先在redrawBuffer绘制到缓冲区,然后一次性显示完整结果 代码结构 单缓冲:所有绘制逻辑在paintEvent中 双缓冲:绘制…...
python3GUI--基于PyQt5+DeepSort+YOLOv8智能人员入侵检测系统(详细图文介绍)
文章目录 一.前言二.技术介绍1.PyQt52.DeepSort3.卡尔曼滤波4.YOLOv85.SQLite36.多线程7.入侵人员检测8.ROI区域 三.核心功能1.登录注册1.登录2.注册 2.主界面1.主界面简介2.数据输入3.参数配置4.告警配置5.操作控制台6.核心内容显示区域7.检…...
Git 使用大全:从入门到精通
Git 是目前最流行的分布式版本控制系统,被广泛应用于软件开发中。本文将全面介绍 Git 的各种功能和使用方法,包含大量代码示例和实践建议。 文章目录 Git 基础概念版本控制系统Git 的特点Git 的三个区域Git 文件状态 Git 安装与配置安装 GitLinuxmacOSWi…...
