牛客 2024 【牛客赛文X】春招冲刺 ONT73 体育课测验(二) 【中等 图/拓扑排序 Java,Go,PHP】

本文主要是介绍牛客 2024 【牛客赛文X】春招冲刺 ONT73 体育课测验(二) 【中等 图/拓扑排序 Java,Go,PHP】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目

在这里插入图片描述题目链接:
https://www.nowcoder.com/practice/64a4c026b2aa4411984f560deec36323

思路

图,BFS,队列

参考答案Java

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可*** @param numProject int整型* @param groups int整型ArrayList<ArrayList<>>* @return int整型ArrayList*/public ArrayList<Integer> findOrder (int numProject,ArrayList<ArrayList<Integer>> groups) {//map表示图Map<Integer, Gnode> graph = new HashMap<>();for (int i = 0; i < numProject ; i++) {graph.put(i, new Gnode(i));}for (ArrayList<Integer> group :groups) { //xxxf代表 开始节点  xxxt代表  f的邻居int vf = group.get(1);int vt = group.get(0);Gnode nodef = graph.get(vf);Gnode nodet = graph.get(vt);nodet.in++;nodef.nexts.add(nodet);}Queue<Gnode> q0 = new LinkedList<>();Set<Integer> set = new HashSet<>();for (Integer v : graph.keySet()) {if (graph.get(v).in == 0) {q0.add(graph.get(v));set.add(v);}}ArrayList<Integer> ll = new ArrayList<>();while (!q0.isEmpty()) {int size = q0.size();for (int i = 0; i < size ; i++) {Gnode cur = q0.poll();ll.add(cur.data);for (Gnode next : cur.nexts) {if (set.contains(next.data)) {return new ArrayList<>();//出现环了,直接返回空的ArrayList}if (--next.in == 0) {q0.add(next);set.add(next.data);}}}}return ll.size() == numProject ? ll : new ArrayList<>();}static class Gnode {int in;int data;List<Gnode> nexts;public Gnode(int d) {data = d;in = 0;nexts =  new ArrayList<>();}}
}

参考答案Go

package main/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可*** @param numProject int整型* @param groups int整型二维数组* @return int整型一维数组*/
func findOrder(numProject int, groups [][]int) []int {// map表示图graph := map[int]*Gnode{}for i := 0; i < numProject; i++ {graph[i] = &Gnode{i, 0, []*Gnode{}}}for _, gp := range groups {vf := gp[1] //出发vt := gp[0] //到达nodef := graph[vf]nodet := graph[vt]nodef.nexts = append(nodef.nexts, nodet) //增加邻居nodet.in++                               //入度+1}q0 := []*Gnode{} //Go中队列用切片来表示set := map[int]bool{}for _, v1 := range graph {if v1.in == 0 {q0 = append(q0, v1)set[v1.data] = true}}ll := []int{}for len(q0) > 0 {size := len(q0)q0bak := []*Gnode{}for i := 0; i < size; i++ {cur := q0[i]//_,ok:=set[cur.data]ll = append(ll, cur.data)for _, next := range cur.nexts {next.in--if next.in == 0 {_, ok := set[next.data]if ok {return []int{}}q0bak = append(q0bak, next)set[next.data] = true}}}q0 = q0bak}if len(ll) == numProject {return ll}return []int{}
}type Gnode struct { //图的节点data  intin    intnexts []*Gnode
}

参考答案PHP

<?php/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** * @param numProject int整型 * @param groups int整型二维数组 * @return int整型一维数组*/
function findOrder( $numProject ,  $groups )
{// 图用map表示,PHP中数组是万能,数组也是java中的map,set,list$graph = array();for($i=0;$i<$numProject;$i++){$graph[$i] =  new Gnode($i);}foreach ($groups as $v){$vt= $v[0];$vf =$v[1];$nodet = $graph[$vt]; //出发节点$nodef = $graph[$vf]; //到达节点,也就是出发节点的邻居$nodet->in++;array_push( $nodef->nexts,$nodet);}//BFS$q0 = [];$set =[];foreach ($graph as $node){if($node -> in ==0){$q0[count($q0)] = $node; //放进入度为0的队列$set[$node->data] = $node->data; //访问过该节点了}}$ll = [];while (count($q0) >0){$size = count($q0);$q0bak = [];for($i=0;$i<$size;$i++){$cur =$q0[$i];$ll[count($ll)] = $cur->data;foreach ($cur->nexts as $next){$next->in--;if($next->in ==0){if(isset($set[$next->data])){return []; //出现环了}$q0bak[count($q0bak)] = $next;$set[$next->data] = $next->data;}}}$q0 =$q0bak;}if(count($ll) == $numProject){return $ll;}return [];
}class Gnode{public $in;public $data;public $nexts;public function __construct($d){$this->data = $d;$this->in =0;$this->nexts = [];}}

这篇关于牛客 2024 【牛客赛文X】春招冲刺 ONT73 体育课测验(二) 【中等 图/拓扑排序 Java,Go,PHP】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Java学习手册之Filter和Listener使用方法

《Java学习手册之Filter和Listener使用方法》:本文主要介绍Java学习手册之Filter和Listener使用方法的相关资料,Filter是一种拦截器,可以在请求到达Servl... 目录一、Filter(过滤器)1. Filter 的工作原理2. Filter 的配置与使用二、Listen

Spring Boot中JSON数值溢出问题从报错到优雅解决办法

《SpringBoot中JSON数值溢出问题从报错到优雅解决办法》:本文主要介绍SpringBoot中JSON数值溢出问题从报错到优雅的解决办法,通过修改字段类型为Long、添加全局异常处理和... 目录一、问题背景:为什么我的接口突然报错了?二、为什么会发生这个错误?1. Java 数据类型的“容量”限制

Java对象转换的实现方式汇总

《Java对象转换的实现方式汇总》:本文主要介绍Java对象转换的多种实现方式,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录Java对象转换的多种实现方式1. 手动映射(Manual Mapping)2. Builder模式3. 工具类辅助映

SpringBoot请求参数接收控制指南分享

《SpringBoot请求参数接收控制指南分享》:本文主要介绍SpringBoot请求参数接收控制指南,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring Boot 请求参数接收控制指南1. 概述2. 有注解时参数接收方式对比3. 无注解时接收参数默认位置

Go语言开发实现查询IP信息的MCP服务器

《Go语言开发实现查询IP信息的MCP服务器》随着MCP的快速普及和广泛应用,MCP服务器也层出不穷,本文将详细介绍如何在Go语言中使用go-mcp库来开发一个查询IP信息的MCP... 目录前言mcp-ip-geo 服务器目录结构说明查询 IP 信息功能实现工具实现工具管理查询单个 IP 信息工具的实现服

SpringBoot基于配置实现短信服务策略的动态切换

《SpringBoot基于配置实现短信服务策略的动态切换》这篇文章主要为大家详细介绍了SpringBoot在接入多个短信服务商(如阿里云、腾讯云、华为云)后,如何根据配置或环境切换使用不同的服务商,需... 目录目标功能示例配置(application.yml)配置类绑定短信发送策略接口示例:阿里云 & 腾

SpringBoot项目中报错The field screenShot exceeds its maximum permitted size of 1048576 bytes.的问题及解决

《SpringBoot项目中报错ThefieldscreenShotexceedsitsmaximumpermittedsizeof1048576bytes.的问题及解决》这篇文章... 目录项目场景问题描述原因分析解决方案总结项目场景javascript提示:项目相关背景:项目场景:基于Spring

Spring Boot 整合 SSE的高级实践(Server-Sent Events)

《SpringBoot整合SSE的高级实践(Server-SentEvents)》SSE(Server-SentEvents)是一种基于HTTP协议的单向通信机制,允许服务器向浏览器持续发送实... 目录1、简述2、Spring Boot 中的SSE实现2.1 添加依赖2.2 实现后端接口2.3 配置超时时

Spring Boot读取配置文件的五种方式小结

《SpringBoot读取配置文件的五种方式小结》SpringBoot提供了灵活多样的方式来读取配置文件,这篇文章为大家介绍了5种常见的读取方式,文中的示例代码简洁易懂,大家可以根据自己的需要进... 目录1. 配置文件位置与加载顺序2. 读取配置文件的方式汇总方式一:使用 @Value 注解读取配置方式二

一文详解Java异常处理你都了解哪些知识

《一文详解Java异常处理你都了解哪些知识》:本文主要介绍Java异常处理的相关资料,包括异常的分类、捕获和处理异常的语法、常见的异常类型以及自定义异常的实现,文中通过代码介绍的非常详细,需要的朋... 目录前言一、什么是异常二、异常的分类2.1 受检异常2.2 非受检异常三、异常处理的语法3.1 try-