当前位置: 首页 > 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;这可能很难做到。 我们经常遇到所谓的属性钻探…...

JavaSec-RCE

简介 RCE(Remote Code Execution)&#xff0c;可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景&#xff1a;Groovy代码注入 Groovy是一种基于JVM的动态语言&#xff0c;语法简洁&#xff0c;支持闭包、动态类型和Java互操作性&#xff0c…...

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...

spring:实例工厂方法获取bean

spring处理使用静态工厂方法获取bean实例&#xff0c;也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下&#xff1a; 定义实例工厂类&#xff08;Java代码&#xff09;&#xff0c;定义实例工厂&#xff08;xml&#xff09;&#xff0c;定义调用实例工厂&#xff…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

服务器--宝塔命令

一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行&#xff01; sudo su - 1. CentOS 系统&#xff1a; yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...

Java毕业设计:WML信息查询与后端信息发布系统开发

JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发&#xff0c;实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构&#xff0c;服务器端使用Java Servlet处理请求&#xff0c;数据库采用MySQL存储信息&#xff0…...

腾讯云V3签名

想要接入腾讯云的Api&#xff0c;必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口&#xff0c;但总是卡在签名这一步&#xff0c;最后放弃选择SDK&#xff0c;这次终于自己代码实现。 可能腾讯云翻新了接口文档&#xff0c;现在阅读起来&#xff0c;清晰了很多&…...

使用SSE解决获取状态不一致问题

使用SSE解决获取状态不一致问题 1. 问题描述2. SSE介绍2.1 SSE 的工作原理2.2 SSE 的事件格式规范2.3 SSE与其他技术对比2.4 SSE 的优缺点 3. 实战代码 1. 问题描述 目前做的一个功能是上传多个文件&#xff0c;这个上传文件是整体功能的一部分&#xff0c;文件在上传的过程中…...

Kubernetes 节点自动伸缩(Cluster Autoscaler)原理与实践

在 Kubernetes 集群中&#xff0c;如何在保障应用高可用的同时有效地管理资源&#xff0c;一直是运维人员和开发者关注的重点。随着微服务架构的普及&#xff0c;集群内各个服务的负载波动日趋明显&#xff0c;传统的手动扩缩容方式已无法满足实时性和弹性需求。 Cluster Auto…...

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

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