【教3妹学编程-算法题】2924. 找到冠军 II

2023-11-08 09:20

本文主要是介绍【教3妹学编程-算法题】2924. 找到冠军 II,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

好冷啊

3妹:2哥快看,我黑龙江的闺蜜给我发了一个她在打雪仗的视频,好大的雪啊,好欢乐。
2哥:什么,东北不是暴雪吗, 还可以打雪仗。
3妹 :是啊,可是雪停了就可以打雪仗了啊。
2哥:你们这些南方人,没见过雪。 雪有什么稀罕的啊

注意保暖
3妹:你不懂,因为小时候没见过啊。 2哥真真是个无趣的人。
2哥:好好,我无趣,这么冷的天我才懒的出去呢。 我还是做我的算法题吧。

题目:

一场比赛中共有 n 支队伍,按从 0 到 n - 1 编号。每支队伍也是 有向无环图(DAG) 上的一个节点。

给你一个整数 n 和一个下标从 0 开始、长度为 m 的二维整数数组 edges 表示这个有向无环图,其中 edges[i] = [ui, vi] 表示图中存在一条从 ui 队到 vi 队的有向边。

从 a 队到 b 队的有向边意味着 a 队比 b 队 强 ,也就是 b 队比 a 队 弱 。

在这场比赛中,如果不存在某支强于 a 队的队伍,则认为 a 队将会是 冠军 。

如果这场比赛存在 唯一 一个冠军,则返回将会成为冠军的队伍。否则,返回 -1 。

注意

环 是形如 a1, a2, …, an, an+1 的一个序列,且满足:节点 a1 与节点 an+1 是同一个节点;节点 a1, a2, …, an 互不相同;对于范围 [1, n] 中的每个 i ,均存在一条从节点 ai 到节点 ai+1 的有向边。
有向无环图 是不存在任何环的有向图。

示例 1:
image.png
输入:n = 3, edges = [[0,1],[1,2]]
输出:0
解释:1 队比 0 队弱。2 队比 1 队弱。所以冠军是 0 队。

示例 2:
image.png
输入:n = 4, edges = [[0,2],[1,3],[1,2]]
输出:-1
解释:2 队比 0 队和 1 队弱。3 队比 1 队弱。但是 1 队和 0 队之间不存在强弱对比。所以答案是 -1 。

提示:

1 <= n <= 100
m == edges.length
0 <= m <= n * (n - 1) / 2
edges[i].length == 2
0 <= edge[i][j] <= n - 1
edges[i][0] != edges[i][1]
生成的输入满足:如果 a 队比 b 队强,就不存在 b 队比 a 队强
生成的输入满足:如果 a 队比 b 队强,b 队比 c 队强,那么 a 队比 c 队强

思路:

思考
本质上是看是否恰好有一个入度为 0 的点。

对每个节点,判断它是否出现在 edges[i][1] 中。

如果恰好有一个节点没有出现,说明没有可以击败它的队伍,返回这个节点的编号。否则返回 −1

java代码:

class Solution {public int findChampion(int n, int[][] edges) {boolean[] weak = new boolean[n];for (int[] e : edges) {weak[e[1]] = true;}int ans = -1;for (int i = 0; i < n; i++) {if (!weak[i]) {if (ans != -1) {return -1;}ans = i;}}return ans;}
}

这篇关于【教3妹学编程-算法题】2924. 找到冠军 II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/368991

相关文章

揭秘Python Socket网络编程的7种硬核用法

《揭秘PythonSocket网络编程的7种硬核用法》Socket不仅能做聊天室,还能干一大堆硬核操作,这篇文章就带大家看看Python网络编程的7种超实用玩法,感兴趣的小伙伴可以跟随小编一起... 目录1.端口扫描器:探测开放端口2.简易 HTTP 服务器:10 秒搭个网页3.局域网游戏:多人联机对战4.

Java并发编程必备之Synchronized关键字深入解析

《Java并发编程必备之Synchronized关键字深入解析》本文我们深入探索了Java中的Synchronized关键字,包括其互斥性和可重入性的特性,文章详细介绍了Synchronized的三种... 目录一、前言二、Synchronized关键字2.1 Synchronized的特性1. 互斥2.

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Python异步编程中asyncio.gather的并发控制详解

《Python异步编程中asyncio.gather的并发控制详解》在Python异步编程生态中,asyncio.gather是并发任务调度的核心工具,本文将通过实际场景和代码示例,展示如何结合信号量... 目录一、asyncio.gather的原始行为解析二、信号量控制法:给并发装上"节流阀"三、进阶控制

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

C#多线程编程中导致死锁的常见陷阱和避免方法

《C#多线程编程中导致死锁的常见陷阱和避免方法》在C#多线程编程中,死锁(Deadlock)是一种常见的、令人头疼的错误,死锁通常发生在多个线程试图获取多个资源的锁时,导致相互等待对方释放资源,最终形... 目录引言1. 什么是死锁?死锁的典型条件:2. 导致死锁的常见原因2.1 锁的顺序问题错误示例:不同

PyCharm接入DeepSeek实现AI编程的操作流程

《PyCharm接入DeepSeek实现AI编程的操作流程》DeepSeek是一家专注于人工智能技术研发的公司,致力于开发高性能、低成本的AI模型,接下来,我们把DeepSeek接入到PyCharm中... 目录引言效果演示创建API key在PyCharm中下载Continue插件配置Continue引言