网站公司后台/在百度怎么免费发布广告
目录
1、找到冠军 Ⅰ- 暴力
2、找到冠军 Ⅱ - 寻找入度为0的点
3、在树上执行操作以后得到的最大分数 - dfs树 + 逆向思考
1、找到冠军 Ⅰ- 暴力
100115. 找到冠军 I
class Solution {public int findChampion(int[][] g) {int n=g.length;for(int i=0;i<n;i++){int cnt=0;for(int j=0;j<n;j++)if(g[i][j]==1) cnt++;if(cnt==n-1) return i;}return 1;}
}
2、找到冠军 Ⅱ - 寻找入度为0的点
100116. 找到冠军 II
思路:
我们通过样例发现冠军点的入度肯定为0,假设有多个入度为0的点,是否能判断出谁是冠军?我们画几种情况看看
我们发现如果有多个入度为0的点,则无法判断出冠军,因为冠军并不是由战胜队伍的数量来衡量的,因此我们只需要找入度为0的点,如果有多个则返回-1
简化代码可以标记入度为0的点,然后遍历找出入度为0的点,如果出现多个则返回-1
class Solution {public int findChampion(int n, int[][] edges) {int[] st=new int[n];for(int[] e:edges)st[e[1]]=1; //将入度不为0的点标记int res=-1;for(int i=0;i<n;i++){if(st[i]==0){if(res!=-1) return -1; //如果入度为0且有多个则无法判断冠军res=i;}}return res;}
}
3、在树上执行操作以后得到的最大分数 - dfs树 + 逆向思考
100118. 在树上执行操作以后得到的最大分数
思路:
要保证这棵树是健康的,且要保证得分最大,即保证每条分支至少保留一个节点不操作(保证该路径和不为0)
所以问题转换为找出每个分支满足健康情况下的【代价和最小】的不操作点
则操作点最大代价和 = 总代价 - 不操作点最小代价和
如下图,选2,5,6为不操作点,则能保证每条分支代价和均不为0,且价值最大
我们设dfs(x)为以x为根节点的健康子树中不操作节点的最小代价
其中cnt为以cur为根节点的子树的最小代价和
则答案=总value - dfs(0) 【整棵健康数中不操作节点的最小代价】
- 在dfs函数中,遍历cur节点的子节点,求出子节点的最小代价和cnt
- 返回 min(cur的价值,以cur为根节点的子树的最小代价cnt)
- 如果cur为叶子节点,则dfs值为val[cur]
为什么需要st[ ]数组标记,建双向边?
因为题目声明根节点为0,从0开始,且为无向树,因此需要双向建边
如果单向建边就会出现下面的这种错误样例
class Solution {public long dfs(int cur,int[] v,List<Integer>[] g,int[] st ){long cnt=0;for(int x:g[cur]) if(st[x]==0){st[x]=1;cnt+=dfs(x,v,g,st);}//cnt=0表示该节点为叶子节点//说白了就是看:是选某子树的根节点值or根节点下子树代价和最小值return cnt==0? v[cur]:Math.min((long)v[cur],cnt);} public long maximumScoreAfterOperations(int[][] edges, int[] values) {int n=values.length;List<Integer>[] g=new ArrayList[n+1];for(int i=0;i<n;i++) g[i]=new ArrayList<>();int[] st=new int[n+1];long res=0;for(int x:values) res+=x;//建树for(int[] e:edges){g[e[0]].add(e[1]);g[e[1]].add(e[0]);}st[0]=1;return res-dfs(0,values,g,st); //dfs(x)表示以x为根节点的健康子树中不操作节点的最小代价//最大代价 = 总代价 - 不操作节点的最小代价和}
}
相关文章:

Leetcode周赛370补题(3 / 3)
目录 1、找到冠军 Ⅰ- 暴力 2、找到冠军 Ⅱ - 寻找入度为0的点 3、在树上执行操作以后得到的最大分数 - dfs树 逆向思考 1、找到冠军 Ⅰ- 暴力 100115. 找到冠军 I class Solution {public int findChampion(int[][] g) {int ng.length;for(int i0;i<n;i){int cnt0;for…...

PyTorch深度学习实战——图像着色
PyTorch深度学习实战——图像着色 0. 前言1. 模型与数据集分析1.1 数据集介绍1.2 模型策略 2. 实现图像着色相关链接 0. 前言 图像着色指的是将黑白或灰度图像转换为彩色图像的过程,传统的图像处理技术通常基于直方图匹配和颜色传递的方法或基于用户交互的方法等完…...

InfiniBand 的前世今生
今年,以 ChatGPT 为代表的 AI 大模型强势崛起,而 ChatGPT 所使用的网络,正是 InfiniBand,这也让 InfiniBand 大火了起来。那么,到底什么是 InfiniBand 呢?下面,我们就来带你深入了解 InfiniBand…...

分享一下微信小程序里怎么添加社区团购功能
随着互联网的快速发展,线上购物已经成为我们日常生活的一部分。而在这个数字化时代,微信小程序作为一种便捷的电商渠道,正逐渐成为新的趋势。其中,社区团购功能更是受到广大用户的热烈欢迎。本文将探讨如何在微信小程序中添加社区…...

软考高项-IT部分
信息化体系 信息化技术应用:龙头 信息资源:核心任务 信息网络:应用基础 信息技术和产业:建设基础 信息化人才:成功之本 信息化法规:保障 信息化趋势 产业信息化、产品信息化、社会生活信息化、国民经济信息化 新型基础设施建设 2018年召开的中央经济工作会议,首…...

hugetlb核心组件
1 概述 hugetlb机制是一种使用大页的方法,与THP(transparent huge page)是两种完全不同的机制,它需要: 管理员通过系统接口reserve一定量的大页,用户通过hugetlbfs申请使用大页, 核心组件如下图: 围绕着…...

vscode配置环境变量
首先点击下面这个链接。 sMinGW-w64 - for 32 and 64 bit Windows - Browse Files at SourceForge.net 然后选择Files这个选项 向下移选择下载这个文件 解压完成之后,找到这个文件的bin目录复制路径后,添加到环境变量中 依次点击后打开cmd࿰…...

react:封装组件
封装 /components/Pagination.tsx import React from react import { Pagination } from antdconst PaginationWarp ({ total, paramsInfo, setParamsInfo }) > {return (<Paginationtotal{total}current{paramsInfo.page}showSizeChangershowQuickJumperdefaultPageSi…...

基于深度学习的视频多目标跟踪实现 计算机竞赛
文章目录 1 前言2 先上成果3 多目标跟踪的两种方法3.1 方法13.2 方法2 4 Tracking By Detecting的跟踪过程4.1 存在的问题4.2 基于轨迹预测的跟踪方式 5 训练代码6 最后 1 前言 🔥 优质竞赛项目系列,今天要分享的是 基于深度学习的视频多目标跟踪实现 …...

linux中各种最新网卡2.5G网卡驱动,不同型号的网卡需要不同的驱动,整合各种网卡驱动,包括有线网卡、无线网卡、Wi-Fi热点
linux中各种最新网卡2.5G网卡驱动,不同型号的网卡需要不同的驱动,整合各种网卡驱动,包括有线网卡、无线网卡、自动安装Wi-Fi热点。 最近在做路由器二次开发,现在市面上卖的新设备,大多数都采用了2.5G网卡,…...

asp.net上传文件
第一种方法 前端: <div> 单文件上传 <form enctype"multipart/form-data" method"post" action"upload.aspx"> <input type"file" name"files" /> …...

JavaEE平台技术——预备知识(Web、Sevlet、Tomcat)
JavaEE平台技术——预备知识(Web、Sevlet、Tomcat) 1. Web基础知识2. Servlet3. Tomcat并发原理 1. Web基础知识 🆒🆒上个CSDN我们讲的是JavaEE的这个渊源,实际上讲了两个小时的历史课,给大家梳理了一下&a…...
基础课23——设计客服机器人
根据调查数据显示,使用纯机器人完全替代客服的情况并不常见,人机结合模式的使用更为普遍。在这两种模式中,不满意用户的占比都非常低,不到1%。然而,在满意用户方面,人机结合模式的用户满意度明显高于其他模…...

mybatis在springboot当中的使用
1.当使用Mybatis实现数据访问时,主要: - 编写数据访问的抽象方法 - 配置抽象方法对应的SQL语句 关于抽象方法: - 必须定义在某个接口中,这样的接口通常使用Mapper作为名称的后缀,例如AdminMapper - Mybatis框架底…...

如何处理前端本地存储和缓存
前端本地存储和缓存的处理是一种重要的技术,它可以帮助改善应用程序的性能和用户体验。下面是一些处理前端本地存储和缓存的常用方法: 1. 使用Web Storage API: 这是一种在浏览器中存储数据的方法,包括两种类型:loca…...

导轨式安装压力应变桥信号处理差分信号输入转换变送器0-10mV/0-20mV/0-±10mV/0-±20mV转0-5V/0-10V/4-20mA
主要特性 DIN11 IPO 压力应变桥信号处理系列隔离放大器是一种将差分输入信号隔离放大、转换成按比例输出的直流信号导轨安装变送模块。产品广泛应用在电力、远程监控、仪器仪表、医疗设备、工业自控等行业。此系列模块内部嵌入了一个高效微功率的电源,向输入端和输…...

人体姿态估计和手部姿态估计任务中神经网络的选择
一、人体姿态估计任务适合使用卷积神经网络(CNN)来解决。 人体姿态估计任务的目标是从给定的图像或视频中推断出人体的关节位置和姿势。这是一个具有挑战性的计算机视觉任务,而CNN在处理图像数据方面表现出色。 使用CNN进行人体姿态估计的一种…...

odoo16 one2many字段的 domain
最近在odoo project模块的基础上做二开,给task表加了一个版本字段version_id,然后重写了 project表的Task_ids, 并且增加了一个domain,结果折腾了大半天才搞定 写法1 这也是最初的写法: version_id fields.Many2one("hx.p…...

一份优秀测试用例的设计策略
日常工作中最为基础核心的内容就是设计测试用例,什么样的测试用例是好的测试用例?我们一般会认为数量越少、发现缺陷越多的用例就是好的用例。那么我们如何才能设计出好的测试用例呢?一份好的用例是设计出来的,是测试人员思路和方法的集合&a…...

自动驾驶行业观察之2023上海车展-----智驾供应链(3)
智驾解决方案商发展 华为:五项重磅技术更新,重点发布华为ADS 2.0和鸿蒙OS 3.0 1)产品方案:五大解决方案都有了全面的升级,分别推出了ADS 2.0、鸿蒙OS 3.0、iDVP智能汽车数字平台、智能车云服务和华为车载光最新 产品…...

倒计时丨3天后,我们直播间见!
倒计时3天,RestCloud 零代码集成自动化平台重磅发布 ⏰11 月 9 日 14:00,期待您的参与! 点击报名:http://c.nxw.so/dfaJ9...

c语言经典算法—二分查找,冒泡,选择,插入,归并,快排,堆排
一、二分查找 1、前提条件:数据有序,随机访问; 2、实现:递归实现,非递归实现 3、注意事项: 循环退出条件:low <high,low high.说明还有一个元素,该元素还要与key进行比较 mid的取值…...

网站SSL证书有什么用
在当今,网站安全对于企业和个人来说至关重要。其中,SSL证书在保护网站和用户数据方面发挥着关键作用。 1,数据加密保护:SSL证书通过使用加密技术,将网站与访问者之间的通信进行加密。这意味着通过SSL保护的网站上的数据…...

ubuntu 20.04 server安装
ubuntu 20.04 server安装 ubuntu-20.04.6-live-server-amd64.iso 安装 安装ubuntu20.04 TLS系统后,开机卡在“A start job is running for wait for network to be Configured”等待连接两分多钟。 cd /etc/systemd/system/network-online.target.wants/在[Servi…...

造数工具调研
开源项目 语言 地址 描述 备注 Faker Python https://github.com/joke2k/faker 一个Python库,可以生成各种各样的假数据,包括SQL语句。它支持多种数据库,包括MySQL、PostgreSQL、Oracle等。Faker可以生成各种类型的数据,如…...

Linux文件系统目录结构
典型的Linux文件系统目录结构的列表 典型的Linux文件系统目录结构的列表。每个目录都有其特定的用途: /bin: 存放系统引导和修复所需的二进制可执行文件,如ls,cp,mv等命令。 /boot: 存放操作系统引导文件,例如内核和…...

CANoe新建XML自动化Test Modules
文章目录 1.打开Test Modules2.新建Environment3.新建XML Test Modules4.新建.can文件5.打开XML Test Modules6.新建xml脚本并保存7.编译8.在.can文件写个测试用例9.修改报告格式为HTML10.运行查看报告后面介绍的文章会重复用到这部分,这里单独介绍下,后面不做重复介绍。 1.…...

国内某发动机制造工厂RFID智能制造应用解决方案
一、工厂布局和装备 国内某发动机制造工厂的装配车间布局合理,设备先进,在这个5万平方米的生产区域内,各个工位之间流程紧密,工厂采用了柔性设备,占比达到了67%,数控化率超过90%,自动化率达到了…...

【SpringCloud Alibaba -- Nacos】Linux 搭建 Nacos 集群
搭建 Nacos 集群 架构 centos安装docker https://docs.docker.com/engine/install/centos/ 详细配置过程 MySql8 mysql数据库配置 数据库脚本 nacos/conf/nacos-mysql.sql Nacos2 application.properties 修改为mysql spring.datasource.platformmysqldb.num1 db.url…...

程序员使用 ChatGPT的 10 种最佳方式
自2022年11月30日发布以来,ChatGPT持续爆火,它在各个方面都产生了巨大的影响力,在软件开发行业,ChatGPT 有潜力彻底改变我们思考和处理软件开发的方式。 ChatGPT 正在改变软件开发流程,它理解自然语言和生成类人文本的…...