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

Leetcode周赛370补题(3 / 3)

目录

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为根节点的健康子树中不操作节点的最小代价

     dfs(cur)=min\left \{ v[cur],cnt \right \}   其中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. 前言 图像着色指的是将黑白或灰度图像转换为彩色图像的过程&#xff0c;传统的图像处理技术通常基于直方图匹配和颜色传递的方法或基于用户交互的方法等完…...

InfiniBand 的前世今生

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

分享一下微信小程序里怎么添加社区团购功能

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

软考高项-IT部分

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

hugetlb核心组件

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

vscode配置环境变量

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

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 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 基于深度学习的视频多目标跟踪实现 …...

linux中各种最新网卡2.5G网卡驱动,不同型号的网卡需要不同的驱动,整合各种网卡驱动,包括有线网卡、无线网卡、Wi-Fi热点

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

asp.net上传文件

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

JavaEE平台技术——预备知识(Web、Sevlet、Tomcat)

JavaEE平台技术——预备知识&#xff08;Web、Sevlet、Tomcat&#xff09; 1. Web基础知识2. Servlet3. Tomcat并发原理 1. Web基础知识 &#x1f192;&#x1f192;上个CSDN我们讲的是JavaEE的这个渊源&#xff0c;实际上讲了两个小时的历史课&#xff0c;给大家梳理了一下&a…...

基础课23——设计客服机器人

根据调查数据显示&#xff0c;使用纯机器人完全替代客服的情况并不常见&#xff0c;人机结合模式的使用更为普遍。在这两种模式中&#xff0c;不满意用户的占比都非常低&#xff0c;不到1%。然而&#xff0c;在满意用户方面&#xff0c;人机结合模式的用户满意度明显高于其他模…...

mybatis在springboot当中的使用

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

如何处理前端本地存储和缓存

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

导轨式安装压力应变桥信号处理差分信号输入转换变送器0-10mV/0-20mV/0-±10mV/0-±20mV转0-5V/0-10V/4-20mA

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

人体姿态估计和手部姿态估计任务中神经网络的选择

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

odoo16 one2many字段的 domain

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

一份优秀测试用例的设计策略

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

自动驾驶行业观察之2023上海车展-----智驾供应链(3)

智驾解决方案商发展 华为&#xff1a;五项重磅技术更新&#xff0c;重点发布华为ADS 2.0和鸿蒙OS 3.0 1&#xff09;产品方案&#xff1a;五大解决方案都有了全面的升级&#xff0c;分别推出了ADS 2.0、鸿蒙OS 3.0、iDVP智能汽车数字平台、智能车云服务和华为车载光最新 产品…...

Python实现prophet 理论及参数优化

文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候&#xff0c;写过一篇简单实现&#xff0c;后期随着对该模型的深入研究&#xff0c;本次记录涉及到prophet 的公式以及参数调优&#xff0c;从公式可以更直观…...

苍穹外卖--缓存菜品

1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得&#xff0c;如果用户端访问量比较大&#xff0c;数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据&#xff0c;减少数据库查询操作。 缓存逻辑分析&#xff1a; ①每个分类下的菜品保持一份缓存数据…...

【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)

要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况&#xff0c;可以通过以下几种方式模拟或触发&#xff1a; 1. 增加CPU负载 运行大量计算密集型任务&#xff0c;例如&#xff1a; 使用多线程循环执行复杂计算&#xff08;如数学运算、加密解密等&#xff09;。运行图…...

Android15默认授权浮窗权限

我们经常有那种需求&#xff0c;客户需要定制的apk集成在ROM中&#xff0c;并且默认授予其【显示在其他应用的上层】权限&#xff0c;也就是我们常说的浮窗权限&#xff0c;那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...

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

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

python爬虫——气象数据爬取

一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用&#xff1a; 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests&#xff1a;发送 …...

基于stm32F10x 系列微控制器的智能电子琴(附完整项目源码、详细接线及讲解视频)

注&#xff1a;文章末尾网盘链接中自取成品使用演示视频、项目源码、项目文档 所用硬件&#xff1a;STM32F103C8T6、无源蜂鸣器、44矩阵键盘、flash存储模块、OLED显示屏、RGB三色灯、面包板、杜邦线、usb转ttl串口 stm32f103c8t6 面包板 …...

高抗扰度汽车光耦合器的特性

晶台光电推出的125℃光耦合器系列产品&#xff08;包括KL357NU、KL3H7U和KL817U&#xff09;&#xff0c;专为高温环境下的汽车应用设计&#xff0c;具备以下核心优势和技术特点&#xff1a; 一、技术特性分析 高温稳定性 采用先进的LED技术和优化的IC设计&#xff0c;确保在…...

ABAP设计模式之---“Tell, Don’t Ask原则”

“Tell, Don’t Ask”是一种重要的面向对象编程设计原则&#xff0c;它强调的是对象之间如何有效地交流和协作。 1. 什么是 Tell, Don’t Ask 原则&#xff1f; 这个原则的核心思想是&#xff1a; “告诉一个对象该做什么&#xff0c;而不是询问一个对象的状态再对它作出决策。…...

vue3 手动封装城市三级联动

要做的功能 示意图是这样的&#xff0c;因为后端给的数据结构 不足以使用ant-design组件 的联动查询组件 所以只能自己分装 组件 当然 这个数据后端给的不一样的情况下 可能组件内对应的 逻辑方式就不一样 毕竟是 三个 数组 省份 城市 区域 我直接粘贴组件代码了 <temp…...