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

2024.2.29力扣每日一题——统计可能的树根数目

2024.2.29

      • 题目来源
      • 我的题解
        • 方法一 深度搜索(暴力) 超时
        • 方法二 树形动态规划

题目来源

力扣每日一题;题序:2581

我的题解

方法一 深度搜索(暴力) 超时
  1. 以每个节点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 题目来源我的题解方法一 深度搜索&#xff08;暴力&#xff09; 超时方法二 树形动态规划 题目来源 力扣每日一题&#xff1b;题序&#xff1a;2581 我的题解 方法一 深度搜索&#xff08;暴力&#xff09; 超时 以每个节点node为跟进行深度搜索&#xff0c;并在搜…...

同一个主机配置多个SSH key

使用git时&#xff0c;我们可能一个git客户端使用多个git服务器&#xff0c;比如github&#xff0c;自建gitlab&#xff0c;gitee&#xff0c;为了防止提交混乱&#xff0c;所以需要一一对应生成公私钥。 第一步&#xff1a; 使用ssh-keygen生成多对密钥对&#xff0c;比如&…...

SAP系统财务模块简介:实现财务管理的卓越之道

作为全球领先的企业管理软件提供商&#xff0c;SAP公司开发了一系列强大而全面的财务模块&#xff0c;帮助企业实现财务管理的高效运作与优化。SAP系统的财务模块涵盖了财务核算、成本管理、资金管理、资产会计等多个方面&#xff0c;为企业提供了完整的财务管理解决方案。本文…...

【pytest】功能特性及常用插件

pytest是一个功能强大的Python测试框架&#xff0c;它的语法简洁明了&#xff0c;易于学习和使用。同时&#xff0c;它提供了丰富的功能和插件&#xff0c;使得测试过程更加灵活和高效。 功能特性 pytest的主要功能特性包括&#xff1a; 参数化测试&#xff1a;允许使用不同…...

基于SpringBoot和Vue的房产销售系统的设计与实现

今天要和大家聊的是一款基于SpringBoot和Vue的房产销售系统的设计与实现 &#xff01;&#xff01;&#xff01; 有需要的小伙伴可以通过文章末尾名片咨询我哦&#xff01;&#xff01;&#xff01; &#x1f495;&#x1f495;作者&#xff1a;李同学 &#x1f495;&#x1f…...

ROS2从入门到精通1-2:详解ROS2服务通信机制与自定义服务

目录 0 专栏介绍1 服务通信模型2 服务模型实现(C)3 服务模型实现(Python)4 自定义服务5 话题、服务通信的异同 0 专栏介绍 本专栏旨在通过对ROS2的系统学习&#xff0c;掌握ROS2底层基本分布式原理&#xff0c;并具有机器人建模和应用ROS2进行实际项目的开发和调试的工程能力。…...

vue两个特性和什么是MVVM

一、什么是vue 1.构建用户界面 用vue往html页面中填充数据&#xff0c;非常的方便 2.框架 框架是一套线成的解决方案 vue的指令、组件&#xff08;是对ui结构的复用&#xff09;、路由、vuex 二、vue的特性 1.数据驱动视图 2.双向数据绑定 1.数据驱动视图 数据的变化会驱动…...

CAD Plant3D 2023 下载地址及安装教程

CAD Plant3D是一款专业的三维工厂设计软件&#xff0c;用于在工业设备和管道设计领域进行建模和绘图。它是Autodesk公司旗下的AutoCAD系列产品之一&#xff0c;专门针对工艺、石油、化工、电力等行业的设计和工程项目。 CAD Plant3D提供了一套丰富的工具和功能&#xff0c;帮助…...

集成电路企业tapeout,如何保证机台数据准确、完整、高效地采集?

Tapeout即流片&#xff0c;集成电路行业中将CDS最终版电路图提交给半导体制造厂商进行物理生产的过程。在芯片设计与制造的流程中&#xff0c;Tapeout是非常重要的阶段&#xff0c;包括了布局&#xff08;Layout&#xff09;、连线&#xff08;Routing&#xff09;、分析&#…...

Nginx三大常用功能“反向代理,负载均衡,动静分离”

注意&#xff1a;以下案例在Windows系统计算机作为宿主机&#xff0c;Linux CentOS 作为虚拟机的环境中实现 一&#xff0c;Nginx配置实例-反向代理 1.反向代理 案例一 实现效果&#xff1a;使用nginx反向代理&#xff0c;访问 www.123.com 直接跳转到127.0.0.1:8080 准备工…...

类方法介绍、使用细节

...

Java SpringBoot中优雅地判断一个对象是否为空

在Java中&#xff0c;可以使用以下方法优雅地判断一个对象是否为空&#xff1a; 使用Objects.isNull()方法判断对象是否为空&#xff1a; import java.util.Objects;if (Objects.isNull(obj)) {// obj为空的处理逻辑 }使用Optional类优雅地处理可能为空的对象&#xff1a; impo…...

算法——矩阵:对于边界元素的处理

. - 力扣&#xff08;LeetCode&#xff09; 题目简述&#xff1a;扫雷&#xff0c;点击一个格子&#xff0c;返回整个地图的下一个状态。 对于边界元素&#xff0c;可以设置两个数组&#xff0c;index_row&#xff0c;index_col&#xff0c;遍历到一个格子需要搜索其周围格子…...

Git分支提交时自动大写 fatal: the remote end hung up unexpectedly

先说结论&#xff1a; 进入 .git/refs/heads目录&#xff0c;会看到Feature文件夹&#xff0c;重命名为feature即可。 表现&#xff1a; 通过终端命令创建的分支 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 类型的全局变量&#xff0c;让其他 C 文件都可以访问&#xff0c;并且可以通过 JNI 方法修改这个变量&#xff0c;可以按照以下步骤进行操作 定义全局变量&#xff1a; 在一个头文件&#xff08;比如 common.h&#xff09;中定义一个全局的 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网关组件&#xff0c;它负责处理服务路由、监控、弹性、安全等API网关的核心功能。Zuul在Spring Cloud Netflix套件中是一个重要的组件&#xff0c;但需要注意的是&#xff0c;随着Spring Cloud的不断发展&#xff0c;Zuul已经被Spring Cloud Gat…...

Delphi D12中实现安卓中文语音合成(中文朗读)不用第三方控件

Delphi开发一个可以朗读中文的APP就非常的简单。 本文给大家介绍使用Delphi开发基于安卓原生的TTS&#xff08;中文语音合成&#xff09;&#xff0c;将文字转语音实现中文的朗读。APP运行后&#xff0c;需要手机上已安装语音引擎。如果您手机上已安装并设置了语音引擎&#xf…...

设计模式 - Provider 模式

在某些情况下&#xff0c;我们希望为应用程序中的许多&#xff08;如果不是全部&#xff09;组件提供数据。尽管我们可以使用 props 将数据传递给组件&#xff0c;但如果应用程序中的几乎所有组件都需要访问 prop 的值&#xff0c;这可能很难做到。 我们经常遇到所谓的属性钻探…...

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式&#xff0c;可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?

在建筑行业&#xff0c;项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升&#xff0c;传统的管理模式已经难以满足现代工程的需求。过去&#xff0c;许多企业依赖手工记录、口头沟通和分散的信息管理&#xff0c;导致效率低下、成本失控、风险频发。例如&#…...

根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:

根据万维钢精英日课6的内容&#xff0c;使用AI&#xff08;2025&#xff09;可以参考以下方法&#xff1a; 四个洞见 模型已经比人聪明&#xff1a;以ChatGPT o3为代表的AI非常强大&#xff0c;能运用高级理论解释道理、引用最新学术论文&#xff0c;生成对顶尖科学家都有用的…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

佰力博科技与您探讨热释电测量的几种方法

热释电的测量主要涉及热释电系数的测定&#xff0c;这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中&#xff0c;积分电荷法最为常用&#xff0c;其原理是通过测量在电容器上积累的热释电电荷&#xff0c;从而确定热释电系数…...

FFmpeg:Windows系统小白安装及其使用

一、安装 1.访问官网 Download FFmpeg 2.点击版本目录 3.选择版本点击安装 注意这里选择的是【release buids】&#xff0c;注意左上角标题 例如我安装在目录 F:\FFmpeg 4.解压 5.添加环境变量 把你解压后的bin目录&#xff08;即exe所在文件夹&#xff09;加入系统变量…...

tomcat指定使用的jdk版本

说明 有时候需要对tomcat配置指定的jdk版本号&#xff0c;此时&#xff0c;我们可以通过以下方式进行配置 设置方式 找到tomcat的bin目录中的setclasspath.bat。如果是linux系统则是setclasspath.sh set JAVA_HOMEC:\Program Files\Java\jdk8 set JRE_HOMEC:\Program Files…...

6个月Python学习计划 Day 16 - 面向对象编程(OOP)基础

第三周 Day 3 &#x1f3af; 今日目标 理解类&#xff08;class&#xff09;和对象&#xff08;object&#xff09;的关系学会定义类的属性、方法和构造函数&#xff08;init&#xff09;掌握对象的创建与使用初识封装、继承和多态的基本概念&#xff08;预告&#xff09; &a…...

【HarmonyOS 5】鸿蒙中Stage模型与FA模型详解

一、前言 在HarmonyOS 5的应用开发模型中&#xff0c;featureAbility是旧版FA模型&#xff08;Feature Ability&#xff09;的用法&#xff0c;Stage模型已采用全新的应用架构&#xff0c;推荐使用组件化的上下文获取方式&#xff0c;而非依赖featureAbility。 FA大概是API7之…...

CppCon 2015 学习:Time Programming Fundamentals

Civil Time 公历时间 特点&#xff1a; 共 6 个字段&#xff1a; Year&#xff08;年&#xff09;Month&#xff08;月&#xff09;Day&#xff08;日&#xff09;Hour&#xff08;小时&#xff09;Minute&#xff08;分钟&#xff09;Second&#xff08;秒&#xff09; 表示…...